Taqsimlangan algoritmlar va tizimlar

Ustma-ust keladigan muammolar

Subproblem maydoni kichik bo'lishi kerak. Ya'ni, muammoni echadigan har qanday rekursiv algoritm yangi pastki muammolarni yaratish o'rniga bir xil subprolemalarni qayta-qayta hal qilishi kerak bo'ladi.
Masalan, Fibonachchi seriyasini yaratish uchun biz ushbu rekursiv formulani ko'rib chiqamiz: Fn = F (n - 1) + F (n - 2), asosiy holat sifatida F1 = F2 = 1 ni qabul qilamiz. F32 + F31 va F32 = F31 + F30.
Ko'rib turganingizdek, F31 F33 va F32 ning rekursiv subtritalarida hal qilinmoqda. Subproblemlarning umumiy soni chindan ham oz bo'lsa ham, agar siz bu kabi rekursiv echimni qabul qilsangiz, bir xil muammolarni qayta-qayta hal qilasiz.
Bu dinamik dasturlash bilan hisobga olinadi, shuning uchun u har bir kichik muammoni faqat bir marta hal qiladi. Bunga ikki yo'l bilan erishish mumkin:

Yuqoridan pastga yondashish

Agar biron-bir muammoning echimi uning pastki muammolari echimi yordamida rekursiv ravishda tuzilishi mumkin bo'lsa va agar bu kichik muammolar bir-biriga to'g'ri keladigan bo'lsa, unda pastki muammolarni echimlari osongina yodda saqlanishi yoki jadvalda saqlanishi mumkin.
Har safar yangi subproblem echimi izlanganda jadval ilgari echilgan-qilinmaganligi tekshiriladi. Agar eritma saqlansa, uni qayta hisoblash o'rniga ishlatiladi. Aks holda, jadvaldagi yechimni saqlab, pastki muammo hal qilinadi.

Pastdan yuqoriga qarab yondashish

Muammoning echimi uning pastki muammolari nuqtai nazaridan rekursiv ravishda shakllantirilgandan so'ng, muammoni ko'tarilgan usulda qayta shakllantirishga urinish mumkin: birinchidan, u kichik muammolarni echishga va ularning echimlaridan foydalanib, kattaroq kichik muammolarga echim topishga harakat qiladi.
Bu, odatda, jadval shaklida ham amalga oshiriladi, kichikroq kichik muammolarga echimlar yordamida takroriy ravishda katta va kattaroq kichik muammolarga echimlar hosil qiladi. Masalan, F31 va F30 qiymatlari allaqachon ma'lum bo'lsa, F32 qiymatini to'g'ridan-to'g'ri hisoblash mumkin.