Bulutli hisoblash nima? Agar biz kontseptsiya haqida gapiradigan bo'lsak

Dinamik dasturlash xususiyatlari

Dinamik dasturlashni amalga oshirishdan oldin quyidagi muhim xususiyatlarga duch kelishingiz kerak:

Optimal pastki tuzilish

Ushbu xususiyat optimallashtirish masalasini, uni o'z ichiga olgan ikkilamchi muammolarning optimal echimlarini birlashtirib hal qilish mumkinligini bildiradi. Ushbu maqbul pastki tuzilmalar rekursiya bilan tavsiflanadi.
Masalan, grafada s tepalikdan t tepalikka boradigan eng qisqa r yo'lda optimal pastki tuzilma taqdim etiladi:
Ya'ni, bu eng qisqa yo'lda r har qanday oraliq tepalikni olish mumkin. Agar r haqiqatan ham eng qisqa marshrut bo'lsa, uni r1 (s dan i gacha) va r2 (i dan t gacha) pastki marshrutlarga bo'lish mumkin, shunday qilib ular tegishli tepaliklar orasidagi eng qisqa marshrutlardir.
Shuning uchun eng qisqa yo'llarni topish uchun echimni rekursiv tarzda osonlikcha shakllantirish mumkin, bu Floyd-Uorshall algoritmi tomonidan amalga oshiriladi

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.