Mavzu: Statistik modellashtirishda eng kichik kvadratlar usuli. Dinamik dasturlashning tamoyili

4. Masalalar 
Eng qisqa yo'lni aniqlash algoritmi quyidagi bosqichlardan iborat: 
1-qadam. n = 1, S
1
(i) = S
i9
. Birinchi bosqichda 9-nuqtaga ikkinchi bosqichning 6, 
7, 8 nuqtalaridan borish mumkin. Shuningdek: S
1
(6) = 15; S
1
(7) = 3; S
1
(8) = 10. 
2-qadam. N = 2, bu yerda biz uchinchi bosqichning (4 va 5) nuqtalaridan ikkinchi 
bosqichga qadar bo'lgan yo'llarni ko'rib chiqamiz. Bu yerda funktsional Bellman 
tenglamasi quyidagi shaklga ega bo’ladi: 
Shuningdek quyidagiga ega bo’lamiz: 
Shartli ravishda optimal yo'l (5-7); 
Shartli ravishda optimal yo'llar (4-6 va 4-8). 
3-qadam. n = 3, bu yerda to'rtinchi bosqichning (2 va 3) nuqtalaridan uchinchi 
bosqichgacha bo'lgan yo'llarni ko'rib chiqiladi. 

---

4 
Shartli ravishda optimal yo'l (2–5).
Shartli optimal yo'l (3-4). 
4-qadam. n = 4, bu erda 1-nuqtadan to'rtinchi bosqichning nuqtalarigacha bo'lgan 
yo'llarni ko'rib chiqiladi. 
S
4
(1) = min {S
12
+ S
3
(2), S
13
+ S
3
(3)} = min {(1 + 22); (2 + 20);} = 22. 
Shartli ravishda optimal yo'l (1-3). 
Endi biz 1-nuqtadan 9-gacha bo'lgan eng qisqa shartsiz yo'lni topamiz. Shartli 
optimallashtirish bosqichida minimal yo'lning uzunligi S
4
(1) = 22 ekanligi 
aniqlandi, bu natija birinchi nuqtadan uchinchisiga o'tganda erishiladi, keyin
to'rtinchisiga o'tish kerak. Ushbu bosqichdan boshlab, 2-bosqichda ko'rsatilgandek, 
6 va 7-nuqtalarga ikkita mumkin bo'lgan ekvivalent yo'nalish mavjud. Shunday 
qilib, optimal yechimga 10.2-rasmda ko'rsatilgan ikkita yo'nalish orqali erishiladi, 
aniqrog'i (1-3–4–6–9) va (1-3–4–8–9). 
10.2-rasm. Optimal yo’l 
Dinamik dasturlash odatda muammolarni yechishda ikkita yondashuvga amal 
qiladi: 
Yuqoridan pastga: vazifa kichikroq qismlarga bo'linadi, ular hal qilinadi va 
keyin asl muammoni hal qilish uchun birlashtiriladi. Tez-tez uchraydigan kichik 
qismlarni yechimlari xotirada saqlanadi. 
Quyidan yuqoriga: Dastlabki muammoni hal qilish uchun kerak bo'ladigan 
barcha pastki jadvallar oldindan hisoblab chiqiladi va keyinchalik asl muammoni 
hal qilishda foydalaniladi. Ushbu usul kerakli stek hajmining kattaligi va 
funktsiyalarni chaqirish soni nuqtai nazaridan yuqoridan pastga bo'lgan dinamik 
dasturlashga qaraganda yaxshiroqdir, ammo ba'zida kelajakda biz uchun qaysi 
kichik masala natijasi kerak bo'lishini oldindan aniqlash oson emas. 
Odatda dinamik dasturning ishlash vaqti quyidagi funktsiyalardan iborat: 
 
Oldindan ishlov berish 
 
Loop for loopi necha marta ishlaydi 
 
Qayta ishlashni takrorlash uchun birida ishlash uchun qancha vaqt ketishi 
kerak 
 
Post-qayta ishlash 
Umuman olganda, ish vaqti quyidagi shaklda bo'ladi: 

---

5 
Dastlabki ishlov berish + Loop * Takrorlash + Post-ishlash 
Dinamik dasturlar uchun katta-O bilan tanishish uchun punchcard muammosining 
ishlash vaqtini tahlil qilaylik. Bu yerda punchcard muammolari dinamik dasturi: 
def punchcardSchedule (n, qiymatlar, keyingi): 
# Eslatma qatorini boshlang - 4 bosqich 
memo = [0] * (n + 1) 
# Asosiy korpusni o'rnatish 
memo [n] = qiymatlar [n] 
# N dan 1 gacha xotiralar jadvalini tuzing - 2 bosqich 
diapazondagi i uchun (n-1, 0, -1): 
memo [i] = maks (v_i + memo [next [i]], memo [i + 1]) 
# OPT (1) muammosiga echim - 3 bosqich 
qaytish eslatmasi [1] 
Uning ish vaqti buzilsin: 
 
Dastlabki ishlov berish: Bu yerda yodlash massivini yaratish kerak. O (n). 
 
Loop necha marta ishlaydi: O (n). 
 
Loop iteratsiyasi uchun birida ishlash uchun takroriylik qancha vaqtni oladi: 
takrorlanish doimiy ishlash vaqtini oladi, chunki har bir iteratsiyada ikkita 
variant o'rtasida qaror qabul qilinadi. O (1). 
 
Post-qayta ishlash: Bu yerda yo'q! O (1) 
Muammoli dinamik dasturning umumiy ish vaqti O (n) O (n) * O (1) + O (1) 
yoki soddalashtirilgan shaklda O (n). 
Nazorat savollari 
1. Dinamik dasturlashning umumiy vazifasini qanday o'rnatish kerak? 
2. Dinamik dasturlash muammosi qanday shakllantirilgan va uning chiziqli 
dasturlash muammolaridan farqi nimada? 
3. Dinamik dasturlashning matematik modelining xususiyatlari qanday? 
4. Dinamik dasturlash usulining asosi nimada? 
5. Optimallashtirish tamoyili nima va Bellman tenglamalari qanday yozilgan?