10-Ma’ruza. Dinamik dasturlash algoritmlari Reja

3 bosqichdan:


f(a₃) = 3 (1 - birinchi qadam, 2 - birinchi va ikkinchi - pog'ona, 3 - barcha 3 bosqichda).
i-.bosqichlariga misolni ko'rib chiqing
Qanday qilib men i bosqichga o'tamiz:
1. i-1 bosqichidan va i-1 bosqichidan biz usullar bilan ai-1 olishimiz mumkin
2. i-2 va i-2 bosqichlaridan biz ai-2 usullarini olishimiz mumkin
Masalan, 4-bosqichga qanday o'tish mumkin:
1. Bizda ikkinchi bosqichga qadamlarning misoli bor, har bir usuliga biz ikki bosqichdan to'liq qadam qo'shamiz.

ya’ni. f(a_i) = 5 …
2. Uchinchi bosqichga o'tishning uchta usuli bor, agar har biriga bir qadam yuqoriroq bo'lgan kichik qadam qo'shsak, 4-bosqichga 3 ta usulni olamiz.

ya’ni f(a_i) = 8
Shunday qilib, i bosqichga o'tishning umumiy soni:f(a_i) = f(a_i-1) + f(a_i-2)
Muammoni hal qilishni boshlash uchun boshlang'ich qiymatlarni aniqlang.
Agar siz 1dan boshlasangiz, unda formulalar Fibonachchi raqamlarining ketma-ketligini topishga mos keladi.f(a₁) = 1
Ammo biz 0 ni, ya'ni 0 dan boshlab hisoblashimiz mumkin. nol bosqichdan nolga o'tish - 1-usul, shunchaki turing.a₀ = 1
Ko'rmoqdamizki, vazifa asosan kombinatorikdir (ya'ni biror narsa qilish usullari soni) ba'zi takroriy ketma-ketlikni hisoblash uchun qisqartirilgan.

1-topshiriq: birinchi o'nta bosqichga misol (amalda Fibonachchi seriyasining dastlabki 10 raqami) rekursiondan foydalaning.

Ko'rib chiqilgan misollarda ikkita quyi qavat yechildi (n = 1, n = 2) va takrorlanish formulalari olingan.
Dinamik dasturlash usulining mohiyati nimada? Dinamik dasturlash usulining echimi uchun uni qo'llash mumkinligi to'g'risida aniq bir narsa deyish mumkinmi, degan savol tug'iladi.
Dinamik dasturlash yordamida aniq bir masalani hal qilish imkoniyati uchun aniq zarur va etarli shart-sharoitlar shakllantirilmagan. Bundan kelib chiqadiki, har bir aniq misolda biz ushbu dinamik dasturlash muammosini hal qilish imkoniyatini izlashimiz kerak.
Usulning umumiy formulasi hech qanday yangilikni o'z ichiga olmaydi. Subtasklarga bo'linish to'g'risidagi bayonotda, keyin quyi qism - keyingi quyi darajaga va hokazo. Bu erda tubdan yangi narsa yo'q.
Ma'lum bir struktura ichida quyi qismlarni echish natijalarini eslab qolish va har bir quyi qismni faqat bir marta echish (ro'yxatga olishdan asosiy farq) albatta ajoyib.
Yuqorida ko'rib chiqilgan vazifalar har qanday bo'linishning har qanday quyi qismlarini o'z ichiga oladi va albatta bitta "topologiya" mavjud. Katta to'p, undan kichikroq to'p va hatto undan ham kichkina - allaqachon to'p, ammo ular bitta topologiyaga ega.
Shunday qilib, agar vazifani bir xil «topologiya» bilan quyi qismlarga bo'lish mumkin bo'lsa, u holda dinamik dasturlash usuli bilan echiladi.
Mustaqil ishlash uchun savollar
1. “Dinamik dasturlash” tushunchasi birinchi marta kim tomonidan va qachon ishlatilgan?
2. Dinamik dasturlash asoschisi kim?
3. Dinamik dasturlash nimani anglatadi?
4. Pastga qarab dinamik dasturlash nimani anglatadi?
5. Yuqori oqim dinamik dasturlash nimani anglatadi?
6. Dinamik dasturlashda qanday klassik muammolar echiladi?
7. Dinamik dasturlashning rasmiy g'oyasi nima?
8. Dinamik dasturlashda qanday vazifalar hal qilinadi?
9. Dinamik dasturlash quyi satrlarining optimalligi qanday izohlanadi?
10. Dinamik dasturlash usulining mohiyati nimada?