Dinamik dasturlash kichik muammolarning natijasini saqlash orqali ishlaydi, shunda ularning yechimlari zarur bo'lganda, ular hozir bo'ladi va biz ularni qayta hisoblashimiz shart emas

Download 394.27 Kb.
bet	4/6
Sana	17.05.2023
Hajmi	394.27 Kb.
	#61083

1 2 3 4 5 6

Bog'liq
4-amaliy Abduqahorov R. Taqsimlangan
4aouLxYxNuuVApyO5uymXDuR5l4wDvxrGkrCXPHB, 1, 6-modul. Buralish deformatsiyasi, article for Sukhrob, 1-amaliy ish Risklarni baholash usullari Ishdan maqsad, MSM, rivojlanishi, 1-topshiriq 511-512-531-532-533, 28-03 03-16, 5 20 guruh talabasi Toshpolotov shahzod optoelektronika fanidan (1), 41uHnjgpJSayA50P8nEHxTVvPwPTV8x8QTy4OkzW, genomika REFARAT, ingliz tili 2, 9

Dinamik dasturlash kichik muammolarning natijasini saqlash orqali ishlaydi, shunda ularning yechimlari zarur bo'lganda, ular hozir bo'ladi va biz ularni qayta hisoblashimiz shart emas.

Kichik muammolarning qiymatini saqlashning bunday usuli memoizatsiya deb ataladi. Massivdagi qiymatlarni saqlash orqali biz allaqachon duch kelgan kichik muammolarni hisoblash uchun vaqtni tejaymiz.
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]
Yodlash orqali dinamik dasturlash dinamik dasturlashning yuqoridan pastga yondashuvidir. Algoritmning ishlash yo'nalishini teskari o'zgartirish orqali, ya'ni asosiy holatdan boshlab va yechimga qarab, biz pastdan yuqoriga qarab dinamik dasturlashni ham amalga oshirishimiz 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 currentFib

Rekursiya va dinamik dasturlash. Dinamik dasturlash asosan rekursiv algoritmlarga qo'llaniladi. Bu tasodif emas, ko'pchilik optimallashtirish muammolari rekursiyani talab qiladi va optimallashtirish uchun dinamik dasturlash qo'llaniladi.

Ammo rekursiyadan foydalanadigan barcha muammolar Dinamik dasturlashdan foydalana olmaydi. Fibonachchi ketma-ketligi muammosi kabi bir-biriga o'xshash kichik muammolar mavjud bo'lmasa, rekursiya faqat bo'linish va zabt etish yondashuvi yordamida yechimga erishishi mumkin.
Shuning uchun birlashma tartiblash kabi rekursiv algoritm Dinamik dasturlashni ishlata olmaydi, chunki kichik muammolar hech qanday tarzda bir-biriga mos kelmaydi.

Ochko'z algoritmlar va dinamik dasturlash. Ochko'z algoritmlari dinamik dasturlashga o'xshaydi, chunki ular ikkalasi ham optimallashtirish uchun vositadir.

Biroq, ochko'z algoritmlar global optimalni topish umidida mahalliy optimal echimlarni yoki boshqacha aytganda, ochko'z tanlovni qidiradi. Shunday qilib, ochko'z algoritmlar o'sha paytda eng maqbul ko'rinadigan taxminlarni amalga oshirishi mumkin, lekin keyinchalik qimmatga tushadi va global optimallikni kafolatlamaydi.
Boshqa tomondan, dinamik dasturlash kichik muammolarning optimal echimini topadi va keyin eng maqbul echimni topish uchun ushbu kichik muammolar natijalarini birlashtirish uchun ongli tanlov qiladi.
Ochko'z algoritm - bu hozirgi vaqtda mavjud bo'lgan eng yaxshi variantni tanlash orqali muammoni hal qilish uchun yondashuv. Tanlov noto'g'ri bo'lsa ham, algoritm hech qachon oldingi qarorni o'zgartirmaydi. U yuqoridan pastga yondashuvda ishlaydi.
Ushbu algoritm barcha muammolar uchun eng yaxshi natijani bermasligi mumkin. Buning sababi shundaki, u har doim global eng yaxshi natijaga erishish uchun mahalliy eng yaxshi tanlovga boradi.
Biroq, agar muammo quyidagi xususiyatlarga ega bo'lsa, algoritmni har qanday muammo bilan ishlatish mumkinligini aniqlashimiz mumkin:

Download 394.27 Kb.

1 2 3 4 5 6

Download 394.27 Kb.