DSA dinamik dasturlash

Dinamik dasturlash

Dinamik dasturlash — algoritmlarni loyihalash usuli.

Dinamik dasturlash yordamida loyihalangan algoritm masalani qism masalalarga ajratadi, qism masalalarning yechimlarini topadi va ularni biz yechmoqchi bo‘lgan masalaning to‘liq yechimini hosil qilish uchun birlashtiradi.

Biz ushbu darslikda dinamik dasturlashni memoizatsiya va tabulyatsiya usullarida, shuningdek 0/1 ryukzak masalasi kabi masalalarni yechishda yoki Bellman-Ford algoritmi yordamida eng qisqa yo‘lni topishda ko‘rgan edik.

Dinamik dasturlash yordamida \(n\)-Fibonachchi sonini topish

Aytaylik, bizga \(n\)-Fibonachchi sonini topadigan algoritm kerak. Biz hali \(n\)-Fibonachchi sonini qanday topishni bilmaymiz, faqat algoritmni loyihalash uchun dinamik dasturlashdan foydalanmoqchi ekanimizni bilamiz.

Xo‘sh, \(n\)-Fibonachchi sonini topadigan algoritmni loyihalash uchun dinamik dasturlashdan qanday foydalanishimiz mumkin?

Dinamik dasturlash yordamida algoritmni qanday loyihalash haqida aniq qoida yo‘q, ammo ko‘p hollarda ish beradigan taklif quyidagicha:

1. Masala "ustma-ust tushuvchi qism masalalar" va "optimal qism tuzilma"ga ega ekanini tekshiring.
2. Eng oddiy qism masalalarni yeching.
3. Yangi qism masalalarning yechimlarini hosil qilish uchun qism masalalar yechimlarini birlashtirish usulini toping.
4. Algoritmni yozing (bosqichma-bosqich tartibni).
5. Algoritmni amalga oshiring (ishlashini sinab ko‘ring).

Keling, buni bajaramiz.

1-qadam: Masala "ustma-ust tushuvchi qism masalalar" va "optimal qism tuzilma"ga ega ekanini tekshirish.

Dinamik dasturlash yordamida algoritm topishga urinishdan oldin, avval masala "ustma-ust tushuvchi qism masalalar" va "optimal qism tuzilma" degan ikki xususiyatga ega ekanini tekshirishimiz kerak.

Ustma-ust tushuvchi qism masalalar?

Ha. \(6\)-Fibonachchi soni \(5\)- va \(4\)-Fibonachchi sonlarining birikmasidir: \(8=5+3\). Bu qoida boshqa barcha Fibonachchi sonlari uchun ham o‘rinli. Bu \(n\)-Fibonachchi sonini topish masalasini qism masalalarga ajratish mumkinligini ko‘rsatadi.

Shuningdek, qism masalalar ustma-ust tushadi, chunki \(F(5)\) \(F(4)\) va \(F(3)\) ga asoslanadi, \(F(6)\) esa \(F(5)\) va \(F(4)\) ga asoslanadi.

\[ \begin{equation} \begin{aligned} F(5) {} & =\underline{F(4)}+F(3) \\ 5 & =\underline{3}+2 \\\\ & va \\\\ F(6) & =F(5)+\underline{F(4)} \\ 8 & =5+\underline{3} \end{aligned} \end{equation} \]

Ko‘rdingizmi? \(F(5)\) va \(F(6)\) qism masalalarining ikkala yechimi ham \(F(4)\) yechimidan foydalanib hosil qilinadi va bunday holatlar ko‘p, demak, qism masalalar ustma-ust ham tushadi.

Optimal qism tuzilma?

Ha, Fibonachchi sonlari ketma-ketligi juda aniq tuzilmaga ega, chunki keyingi Fibonachchi sonini hosil qilish uchun oldingi ikki son qo‘shiladi va bu dastlabki ikkitasidan tashqari barcha Fibonachchi sonlari uchun o‘rinli. Bu qism masalalar yechimlarini birlashtirib, yechimni qanday (how) tuzishni bilishimizni anglatadi.

Xulosa qilishimiz mumkinki, \(n\)-Fibonachchi sonini topish masalasi ikkala talabni qanoatlantiradi, demak, masalani yechadigan algoritmni topish uchun dinamik dasturlashdan foydalanishimiz mumkin.

2-qadam: Eng oddiy qism masalalarni yechish.

Endi dinamik dasturlash yordamida algoritm topishga kirishishimiz mumkin.

Algoritm qanday ishlashi kerakligi haqida tasavvurga ega bo‘lish uchun avval eng oddiy qism masalalarni yechish yaxshi boshlanish nuqtasidir.

\(n\)-Fibonachchi sonini topish masalamizda eng oddiy qism masalalarni topish unchalik qiyin emas, chunki biz allaqachon bilamizki

\[ F(0)=0 \\ F(1)=1 \\ F(2)=1 \\ F(3)=2 \\ F(4)=3 \\ F(5)=5 \\ F(6)=8 \\ ... \]

3-qadam: Yangi qism masalalarning yechimlarini hosil qilish uchun qism masalalar yechimlarini birlashtirish usulini topish.

Bu qadamda, bizning masalamiz uchun qism masalalarning qanday birlashtirilishi ancha oddiy: keyingisini topish uchun oldingi ikki Fibonachchi sonini qo‘shishimiz kifoya.

Masalan, \(2\)-Fibonachchi soni oldingi ikki sonni qo‘shish orqali hosil qilinadi: \(F(2)=F(1)+F(0)\), va yuqorida aytilganidek, umumiy qoida ham shunday: \(F(n)=F(n-1)+F(n-2)\).

4-qadam: Algoritmni yozish (bosqichma-bosqich tartibni).

Algoritm matnini darhol yozish o‘rniga, avval aniq bir masalani, masalan, \(6\)-Fibonachchi sonini topishni yechish tartibini yozib ko‘rish oqilona bo‘lishi mumkin.

Ma’lumot uchun, dastlabki 8 ta Fibonachchi soni: \(0,\; 1,\; 1,\; 2,\; 3,\; 5,\; \underline{8},\; 13\).

\(6\)-Fibonachchi sonini topish uchun ketma-ketlikning 0- va 1-o‘rinlarida turgan dastlabki ikki son \(0\) va \(1\) dan boshlab, ularni massivning 0- va 1-indekslariga joylashimiz mumkin. So‘ngra keyingi sonni hosil qilish uchun massivdagi dastlabki ikki sonni qo‘shib, bu yangi sonni massivga yangi element sifatida qo‘shishimiz mumkin. Massiv uzunligi 7 ta elementga yetguncha shu tarzda davom etsak, to‘xtab, F[6] ni qaytaramiz. Bu ishlaydi, to‘g‘rimi?

Yuqoridagi aniq masalani yechganimizdan so‘ng endi haqiqiy algoritmni yozish osonroq.

Dinamik dasturlashni loyihalash usuli sifatida qo‘llab, \(n\)-Fibonachchi sonini topish algoritmini quyidagicha tavsiflash mumkin:

5-qadam: Algoritmni amalga oshirish (ishlashini sinab ko‘rish).

Yuqoridagi algoritmni amalga oshirish uchun funksiyaga beriladigan n argumenti musbat son (\(n\)-Fibonachchi soni) deb faraz qilamiz, yangi Fibonachchi sonlarini hosil qilish uchun for siklidan foydalanamiz, agar funksiya argument sifatida 0 yoki 1 bilan chaqirilsa, F[0] va F[1] bazaviy holatlarini darhol qaytaramiz.

Algoritmni amalga oshirish, shuningdek, uning ishlashini tekshira olishimizni ham anglatadi.

def nth_fibo(n):
    if n==0: return 0
    if n==1: return 1

    F = [None] * (n + 1)
    F[0] = 0
    F[1] = 1

    for i in range(2, n + 1):
        F[i] = F[i - 1] + F[i - 2]

    return F[n]

n = 6
result = nth_fibo(n)
print(f"The {n}th Fibonacci number is {result}")

Mana!

Biz \(n\)-Fibonachchi sonini topadigan algoritm yaratish uchun dinamik dasturlashdan loyihalash usuli sifatida foydalandik.

Shuningdek, algoritm ishlashini ko‘rsatish uchun uni amalga oshirdik va bunda beixtiyor dinamik dasturlashdagi tabulyatsiya deb ataladigan, yaxshi o‘rganilgan usuldan foydalandik — unda yechim qandaydir jadval yordamida qism masalalarni pastdan yuqoriga yechish orqali topiladi.

Bundan tashqari, bir xil ustma-ust tushuvchi qism masalalarni, masalan, F[3] ni ko‘p marta hisoblashdan qochdik — aks holda, aytaylik, brute force rekursiv yondashuvidan foydalanganimizda shunday qilib qo‘yishimiz mumkin edi.

Dinamik dasturlashda qo‘llaniladigan yana bir usul memoizatsiya deb ataladi. Bu holatda memoizatsiyadan foydalanish, mohiyatan, masalani brute force bilan rekursiv yechadi, ammo bir xil hisob-kitoblarni bir necha marta bajarmaslik uchun algoritm ishlashi davomida qism masalalar yechimlarini keyinchalik foydalanish uchun saqlab boradi.

Dinamik dasturlashda qo‘llaniladigan usullar

Dinamik dasturlash yordamida algoritm loyihalash qiyin bo‘lishi mumkin, ammo dinamik dasturlash tushunchasining o‘zi aslida unchalik qiyin emas: masalani yeching, lekin qism masalalar ustma-ust tushgani uchun buni aqlli tarzda bajaring, shunda har bir aniq qism masala faqat bir marta yechilishi kerak bo‘ladi.

Dinamik dasturlashda oldin yechilgan qism masalalar yechimlaridan foydalana olish uchun oldin topilgan yechimlar qandaydir tarzda saqlanishi kerak va buni memoizatsiya yoki tabulyatsiya yordamida amalga oshirish mumkin.

Memoizatsiya — dinamik dasturlashda qo‘llaniladigan usul bo‘lib, unda yechim rekursiv tarzda topiladi. Algoritm ishlashi davomida qism masalalar yechimlari saqlanadi va qism masala yechimini hisoblashga urinishdan oldin, bir xil hisob-kitobni bir necha marta bajarmaslik uchun, avval bu yechim allaqachon hisoblanganmi-yo‘qligi tekshiriladi.

Memoizatsiya usuli "yuqoridan pastga" deb ataladi, chunki dastlabki funksiya chaqiruvi asosiy masala uchun bo‘ladi va u tobora kichikroq qism masalalarni yechish uchun yangi funksiya chaqiruvlariga olib keladi.

Tabulyatsiya — dinamik dasturlashda qo‘llaniladigan usul bo‘lib, unda ustma-ust tushuvchi qism masalalar yechimlari eng oddiy qism masalalardan boshlab jadvalda (massivda) saqlanadi.

Tabulyatsiya usuli rekursiv emas va u "pastdan yuqoriga" deb ataladi, chunki yakuniy yechim avval eng oddiy qism masalalarni yechish orqali quriladi. Eng oddiy qism masalalar yechimlari jadvalda birinchi saqlangani uchun keyinroq oldingi qism masalalarga tayanadigan qism masalani yechishda algoritm bu yechimlarni to‘g‘ridan-to‘g‘ri jadvaldan olishi mumkin, ularni qayta hisoblash shart emas.

Memoizatsiya qanday ishlashi va nima uchun "yuqoridan pastga" deb hisoblanishini, tabulyatsiya qanday ishlashi va nima uchun "pastdan yuqoriga" ekanini yaxshiroq tushunish uchun quyidagi ikki rasmga qarang.

Yuqoridagi rasmlarda ko‘rib turganingizdek, tabulyatsiya yondashuvi pastdan boshlab, avval F(0) ni yechadi, memoizatsiya yondashuvi esa yuqoridan, F(10) dan boshlaydi va u yerdan uni tobora kichikroq qism masalalarga ajratadi.