Dinamik dasturlash nima?
Dinamik dasturlash (Dynamic Programming — DP) — bu kompyuter dasturlashida ustma-ust tushuvchi qism-masalalar (overlapping subproblems) va optimal qism-tuzilma (optimal substructure) xususiyatlariga ega bo'lgan murakkab masalalarni samarali yechishga yordam beruvchi kuchli algoritmlash usulidir.
Agar biror masala qism-masalalarga, ular esa o'z navbatida yanada kichikroq qism-masalalarga bo'linishi mumkin bo'lsa va bu qism-masalalar bir-birini takrorlasa (ustma-ust tushsa), u holda hisoblangan qism-masalalar yechimini kelgusida qayta foydalanish uchun xotirada saqlab qo'yish mumkin. Shu yo'l bilan protsessor (CPU) sarflaydigan vaqtni keskin tejash va samaradorlikni oshirish mumkin. Yechimni bunday saqlab borish orqali masalani hal qilish usuli dinamik dasturlash deb ataladi.
Bunday masalalar optimal yechimni topish uchun bir xil qism-masalalar qiymatini qayta-qayta hisoblashni talab etadi. Dinamik dasturlash aynan shu takroriy hisoblashlarni yo'qotadi.
Keling, Fibonachchi ketma-ketligining 5-hadini hisoblash misolini ko'rib chiqamiz. Fibonachchi ketma-ketligi — bu har bir son o'zidan oldingi ikkita sonning yig'indisiga teng bo'lgan sonlar qatoridir: 0, 1, 1, 2, 3, 5, ...
Algoritm:
Faraz qilaylik, n — hisoblanishi kerak bo'lgan hadning tartib raqami.
n = 0 bo'lsa, 0 qaytariladi.n = 1 bo'lsa, 1 qaytariladi.fib(n-1) + fib(n-2) qaytariladi.Ketma-ketlikning 5-hadini bosqichma-bosqich hisoblaymiz:
0.1.0 + 1 = 1.1 + 1 = 2.2 + 1 = 3.Shunday qilib, biz 0, 1, 1, 2, 3 ketma-ketligini hosil qildik. Bu yerda biz quyida ko'rsatilganidek, oldingi qadamlar natijalaridan to'g'ridan-to'g'ri foydalandik:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0)
F(3) = F(2) + F(1)
F(4) = F(3) + F(2)
Bu dinamik dasturlash yondashuvi deb ataladi.
Dinamik dasturlash qism-masalalarning natijalarini maxsus jadvalda (massiv yoki xesh-jadval) saqlash orqali ishlaydi. Qachonki ushbu qism-masalaning yechimi yana kerak bo'lib qolsa, u qaytadan hisoblanmaydi, balki tayyor holda xotiradan olinadi.
Qism-masalalar qiymatini xotirada saqlab borish texnikasi memoizatsiya (memoization) deyiladi. Qiymatlarni massivda saqlash orqali biz allaqachon duch kelgan qism-masalalarni qayta hisoblash vaqtini tejaymiz.
Dinamik dasturlashning ikkita asosiy yondashuvi mavjud:
Yuqoridan-pastga yondashuv (Memoizatsiya):
Bu usulda dastur kattaroq masaladan boshlab rekursiv chaqiriladi va har bir qism-masala yechimi birinchi hisoblanganda keshga (lug'at yoki massivga) saqlab ketiladi:
var m = map(0 -> 0, 1 -> 1)
function fib(n)
if key n is not in map m
m[n] = fib(n - 1) + fib(n - 2)
return m[n]
Pastdan-yuqoriga yondashuv (Tabulyatsiya):
Algoritm ishlash yo'nalishini teskarisiga o'zgartirish, ya'ni eng asosiy boshlang'ich holatdan (base case) boshlab to'liq yechimgacha qadamma-qadam massivni to'ldirib borish orqali dinamik dasturlashni pastdan-yuqoriga amalga oshirish mumkin:
function fib(n)
if n = 0
return 0
else
var prevFib = 0, currFib = 1
repeat n - 1 times
var newFib = prevFib + currFib
prevFib = currFib
currFib = newFib
return currFib
Dinamik dasturlash ko'pincha rekursiv algoritmlarga tatbiq qilinadi. Bu tasodif emas: ko'pchilik optimallashtirish masalalari rekursiyani talab qiladi va dinamik dasturlash aynan optimallashtirish uchun xizmat qiladi.
Biroq, rekursiyadan foydalanadigan har qanday masalani ham dinamik dasturlash bilan yechib bo'lmaydi. Masalada Fibonachchi ketma-ketligidagidek ustma-ust tushuvchi qism-masalalar (overlapping subproblems) mavjud bo'lmasa, rekursiya yechimga faqat bo'lib ol va boshqar (divide and conquer) usuli orqali erishishi mumkin.
Shu sababli, Merge Sort (Birlashtirib saralash) kabi rekursiv algoritmlar dinamik dasturlashdan foydalana olmaydi, chunki uning qism-masalalari bir-birini takrorlamaydi va mutlaqo mustaqildir.
Greedy (ochko'z) algoritmlar va dinamik dasturlash bir-biriga o'xshaydi, chunki ikkalasi ham optimallashtirish vositasidir.
Biroq, ochko'z algoritmlar global optimumga erishish umidida har bir qadamda lokal optimal yechimni (ochko'z tanlovni) tanlaydi. Shu sababli, ochko'z algoritmlar ayni paytda eng yaxshi ko'ringan, biroq kelgusida qimmatga tushadigan va global optimal natijani kafolatlamaydigan tanlovlarni amalga oshirib qo'yishi mumkin.
Dinamik dasturlash esa barcha qism-masalalarning optimal yechimlarini topadi va shundan so'ng eng maqbul umumiy yechimni hosil qilish uchun ushbu natijalarni oqilona birlashtiradi.
package main
import "fmt"
// 1. Top-down yondashuv (Memoizatsiya)
func fibMemo(n int, memo map[int]int) int {
if n <= 1 {
return n
}
if val, ok := memo[n]; ok {
return val
}
memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo)
return memo[n]
}
// 2. Bottom-up yondashuv (Tabulyatsiya)
func fibTab(n int) int {
if n <= 1 {
return n
}
prev2, prev1 := 0, 1
for i := 2; i <= n; i++ {
curr := prev1 + prev2
prev2 = prev1
prev1 = curr
}
return prev1
}
func main() {
n := 5
memo := make(map[int]int)
fmt.Printf("Fibonacci (%d-had) - Memoizatsiya: %d\n", n, fibMemo(n, memo))
fmt.Printf("Fibonacci (%d-had) - Tabulyatsiya: %d\n", n, fibTab(n))
}