10-Ma’ruza. Dinamik dasturlash algoritmlari Reja

Kombinatorika vazifalari
Masalan: Graflar va daraxtlar
Muayyan miqdordagi barglari bo'lgan qancha daraxt mavjudligini aniqlash vazifasi; yoki bunday vazifani hal qilish uchun qancha grafik mavjud va hokazo.
Misol: tangalarni almashtirish vazifasi yoki o'zgarishni qaytarish usullari soni
Har xil nomdagi tangalar mavjud bo'lib, ular yordamida siz o'zgarishni qaytarishingiz mumkin.
1. Dinamik dasturlash quyi qismlarining maqbulligini norasmiy tushuntirish.
Diagramma yordamida subkastrlarning maqbulligi xususiyati to'g'risida norasmiy tushuntirishni namoyish etish mumkin:

2-rasm. Quyi qismlarning maqbulligi xususiyati haqida norasmiy tushuntirish
Biz Dinamik dasturlash yordamida yechish uchun masala tanlab oling va uning yechimi uchun biron bir reja toping. Aytaylik, bu muammo juda murakkab va uni darhol hal qila olmaymiz. Biz kichik subtaskani olamiz va avval uni (for) x_1 yechamiz. Keyin x_1 bu kichik yechimdan foydalanamiz va ushbu eritmaning tarkibini o'zgartirmasdan x_1 va x_2 bilan quyidagi muammoni hal qilamiz.
Mebel fabrikasini misol qilib oling. Foydani ko'paytirish maqsadiga erishish uchun ko'plab kichik vazifalarni hal qilish kerak:

• 
  qancha stul ishlab chiqarishi mumkin - o'zgaruvchan X1,
  
• 
  qancha jadval ishlab chiqarish kerak - o'zgaruvchan X2,
  
• 
  ishchilarni qancha yollash kerak - o'zgaruvchan X3,
  
• 
  …Хn.
  

Ko'p sonli quyi satrlarda bunday muammoni qanday hal qilishni tushunish qiyin. Qoida tariqasida bitta kichik muammoni hal qilish kichiklardan iborat bo'lgan katta muammoni hal qilishdan osonroqdir.
Shuning uchun dinamik dasturlash quyidagilarni taklif qiladi:
• biz X1 o'zgaruvchisi bilan bitta subtaskani olamiz, qolgan quyi satrlarni unutamiz.
Masalan, fabrika faqat stullar ishlab chiqaradi. Direktorga stullarni sotishdan tushgan daromadni ko'paytirish vazifasi qo'yilgan.
• Birinchi subtask uchun eng maqbul echimni topganimizdan so'ng, X1 va X2 ikkita o'zgaruvchisi uchun subtitrni oling va birinchi subtask uchun topilgan echimdan foydalanib, uni hal qiling.
• X1 va X2 o'zgaruvchilar paydo bo'ladigan kattaroq quyi qism uchun biz allaqachon echim topamiz. Keyin olingan echimdan foydalanib, biz X1, X2 va X3-ni qamrab oladigan quyi qismlarni olamiz.
• Shunday qilib, biz butun umumiy muammoni hal qilgunimizcha davom etamiz.
Muhim: Bu erda asosiy nuqta keyingi bosqichni hal qilishda tugallangan echimni kichik quyi qism uchun ishlatishdir - kattaroq subkask

5. Dinamik dasturlash yordamida muammolarni yechishga misol

Dinamik dasturlash yordamida muammoning echimini ko'rib chiqing.
Masalan: n sonlarining yig'indisini hisoblash kerak: 1 + 2 + 3 + ... + n

Ushbu vazifaning "murakkabligi" nimada: darhol ko'p sonli raqamlarni olish va javob olish kerak.

Keling, Dinamik dasturlash g'oyasini muammoga qo'llashga harakat qilamiz va uni oddiy quyi qismlarga ajratib, uni hal qilamiz.
(dinamik dasturlashdada har doim birinchi shartlarni yoki holatni aniqlash kerak)
• Biz bitta birinchi elementning yig'indisidan boshlaymiz, ya'ni faqat birinchi elementni oling:
F (1) = 1
• endi birinchi element uchun echimdan foydalangan holda biz hal qilamiz
F (2) = F (1) + 2 = 1 + 2 = 3, ya'ni. siz birinchi elementning yig'indisini olib, unga ikkinchi elementni qo'shishingiz kerak
• F (3) = F (2) + 3 = 6
• analogiya bo'yicha, biz davom etamiz va ob'ektiv funktsiyani olamiz:
F (n) = F (n-1) + An

Shunday qilib, biz nima qildik: tartibni aniqlang va quyi qismlarni ajratib oling, so'ngra har birini avvalgisining echimiga asoslanib hal qiling. Dinamik dasturlash asossiz (sun'iy ravishda) ishlatilgan oddiy misol, Dinamik dasturlash g'oyalari printsipini namoyish etadi.
Masalan: n bosqichli zinapoyalar bor, ularning oldida bir qadamda keyingi pog'onaga ko'tarilish yoki bir pog'ona yuqoriga sakrash mumkin.
Savol: oxirgi bosqichga qancha yo'l bilan borishi mumkin?

Qaror:
Eng oddiy variantlarni ko'rib chiqing (quyi chiziqlar):
1. Agar narvon 1 bosqichdan iborat bo'lsa:

f(a₁) = 1

2. 
   2 bosqichdan
   

f(a₂) = 2

2.