Sverxu dinamik dasturlash usuli shunchaki keyinchalik takrorlanishi
mumkin bo'lgan sub-vazifalarni hal qilish natijalarini saqlashdir. Dinamik
dasturlash murakkab vazifani sodda taglavhalarning
rekursiv ketma-ketligi
shaklida qayta o'zgartirishni ham o'z ichiga oladi.
"Dinamik dasturlash" iborasi birinchi marta 1940 yillarda Richard Bellman
tomonidan muammoning echimini topish jarayonini tasvirlash uchun ishlatilgan
bo'lib, unda bitta muammoga javob faqat "oldingi" muammoni hal qilganidan
keyingina olish mumkin. 1953 yilda u ushbu ta'rifni zamonaviyga aniqlab berdi.
Dastlab, ushbu soha IEEE tomonidan tan olingan tizimlarni tahlil qilish va
muhandislik sifatida tashkil etilgan. Bellmanning dinamik dasturlashdagi hissasi
dinamik dasturlash nazariyasining markaziy natijasi bo'lgan Bellman tenglamasi
nomi
bilan abadiylashtirildi, bu esa optimizatsiyalash muammosini rekursiv
shaklda isloh qiladi.
"Dinamk dasturlash" jumlasidagi "dasturlash" so'zi aslida "an'anaviy"
dasturlash (yozuv kodi) bilan hech qanday aloqasi yo'q va "optimallashtirish"
so'ziga sinonim bo'lgan "matematik dasturlash" iborasidagi kabi ma'noga ega.
Shuning uchun ushbu dasturda "dastur" so'zi muammoni hal qilish uchun maqbul
harakatlar ketma-ketligini anglatadi. Masalan, ko'rgazmadagi tadbirlar jadvaliga
ba'zan dastur deyiladi. Bu holda dastur deganda voqealar ketma-ketligi
tushuniladi.
Dinamik dasturlashda maqbul pastki tuzilma asl muammoni hal qilish uchun
kichik kichik vazifalarni maqbul echimini qo'llash mumkinligini anglatadi.
Masalan, bitta verteksdan ikkinchisiga (s bilan belgilanadigan) grafikdagi eng
qisqa yo'lni quyidagicha topish mumkin: birinchi navbatda s-dan t -gacha ulashgan
barcha vertikallardan eng qisqa yo'lni ko'rib chiqing, so'ngra ularni bog'laydigan
qirralarning og'irligini hisobga oling. qo'shni uchlari bilan t ga eng yaxshi yo'lni
tanlang (qaysi tepadan o'tish yaxshidir).
Umumiy holda, maqbul pastki tuzilma
mavjud bo'lgan muammoni quyidagi uchta amalni bajarish orqali hal qilishimiz
mumkin.
Vazifani kichikroq pastki qismlarga bo'lish.
Subtastrlarning eng maqbul echimini topish uch bosqichli algoritmni
bajarish bilan rekursivdir.
Olingan pastki chizmalarning echimini asl muammoning echimini yaratish
uchun ishlatish.
Subproblemlar doimiy ravishda echilishi mumkin bo'lgan muammoning
arzimas holatiga kelgunga qadar, ularni kichikroq hajmdagi kichik dasturlarga va
hokazolarga bo'lish orqali hal qilinadi (javob darhol aytilishi mumkin). Masalan,
agar biz n ni topishga muhtoj bo'lsak, unda arzimas vazifa 1 bo'ladi! = 1 (yoki 0! =
1).
Dinamik dasturlashda bir-birini to'ldirib turadigan
pastki qavatlar deganda
kattaroq o'lchamdagi bir qator muammolarni (bitta emas) hal qilish uchun
foydalaniladigan pastki tagliklar tushuniladi (ya'ni biz bir xil ishni bir necha bor
qilamiz). Fibonachchi ketma-ketligini hisoblash, {\ displaystyle F_ {3} = F_ {2} +
F_ {1}} F_ {3} = F_ {2} + F_ {1} va {\ displaystyle F_ {4} = F_ { 3} + F_ {2}}
F_ {4} = F_ {3} + F_ {2} - hatto ikkita Fibonachchi sonini hisoblashning
ahamiyatsiz bo'lmagan taqdirda ham, biz {\ displaystyle F_ {2}} F_ {2} ni ikki
marta sanadik. Agar biz oldinga borsak va {\ displaystyle F_ {5}} F_ {5} ni
hisoblasak, {\ displaystyle F_ {2}} F_ {2}
yana ikki marta sanaladi, chunki {\
displaystyle F_ {5}} F_ { 5} yana {{displaystyle F_ {3}} F_ {3} va {\
displaystyle F_ {4}} F_ {4} uchun yana kerak bo'ladi. Bu quyidagicha ko'rinadi:
oddiy rekursiv yondashuv, u allaqachon hal qilgan muammolar uchun echimni
hisoblash uchun vaqt sarflaydi.
Hodisalarning bunday holatiga yo'l qo'ymaslik uchun biz allaqachon hal
qilgan pastki qismlarning echimlarini saqlab qolamiz va yana biz yana hisob-kitob
qilishning o'rniga, pastki qism echimini talab qilsak, shunchaki uni xotiradan
o'chirib tashlaymiz. Ushbu yondashuv eslab qolish deb nomlanadi.
Keyinchalik
optimallashtirishni amalga oshirishingiz mumkin - masalan, agar biz pastki qismni
echishga endi ehtiyoj qolmasligiga amin bo'lsak, uni xotiradan o'chirib, boshqa
ehtiyojlar uchun bo'shatib qo'yamiz yoki protsessor bo'sh bo'lsa va biz hali
hisoblanmagan pastki qismlarga echim topilishini bilsak, kelajakda bizga kerak
bo'ladi, biz ularni oldindan hal qilishimiz mumkin.
Yuqoridagilardan xulosa qilib aytish mumkinki,
dinamik dasturlash
muammoning quyidagi xususiyatlaridan foydalanadi.
bir-birini to'ldiruvchi pastki satrlar;
maqbul pastki tuzilma;
tez-tez uchraydigan pastki qismlarga echimlarni yodlash qobiliyati.
Dinamik dasturlash odatda muammolarni echishda ikkita yondashuvga amal
qiladi:
pastga qarab dinamik dasturlash: vazifa kichik pastki qismlarga bo'linadi,
ular hal qilinadi va keyin asl muammoni hal qilish uchun birlashtiriladi. Xotiralash
allaqachon echilgan pastki qismlarni echish uchun ishlatiladi.
upstream dinamik dasturlash: keyinchalik asl muammoni hal qilish uchun
kerak bo'lgan barcha quyi chiziqlar oldindan hisoblab chiqiladi va keyinchalik asl
muammoning echimini yaratishda foydalaniladi. Ushbu usul kerakli stack hajmi va
funktsiyalar soni bo'yicha nuqtai nazaridan yuqoridan-pastga dasturlashdan
afzaldir, lekin ba'zida kelajakda qaysi pastki satrlarni hal qilishimiz kerakligini
oldindan aniqlash oson emas.
Do'stlaringiz bilan baham: 
