Algoritmlardı bahalaw kriteriyalari

Dinamikalıq programmalastırıwdıń ulıwma wazıypasın qanday ornatıw kerek?
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.
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.
Boshqa texnikalar bilan taqqoslash
Dinamik dasturlash bilan echilishi mumkin bo'lgan muammoning muhim xususiyati shundaki, uning pastki muammolari bir-biriga mos kelishi kerak. Bu eng oddiy qiymatlarni saqlash shart bo'lmagan holda dinamik dasturlashni bo'linish va zabt etish texnikasidan ajratib turadi.
Bu rekursiyaga o'xshaydi, chunki asosiy holatlarni hisoblashda yakuniy qiymat induktiv tarzda aniqlanishi mumkin. Ushbu pastdan yuqoriga yondashuv yangi qiymat faqat oldindan hisoblangan qiymatlarga bog'liq bo'lganda yaxshi ishlaydi.