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

TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI URGANCH FILIALI KOMPYUTER INJINIRINGI FAKULTETI

MUSTAQIL ISH

Fan:Algoritmlarni loyihalash
Guruh: 961-20
Bajardi: Sharipova Charosxon
Tekshirdi: Yuspova Janar


Mavzu: Statistik modellashtirishda eng kichik kvadratlar usuli. Dinamik
dasturlash.
Reja:
1. Dinamik dasturlashning tamoyili
2. Dinamik dasturlash masalalarini yechish sxemasi.

Dinamik dasturlashning tamoyili

Maqsad funktsiyasining koʼrinishi va oʼzgaruvchilarga qoʼyiladigan
cheklanish shartlari sistemasiga koʼra matematik dasturlash asosan olti turga
ajratiladi:

1. Chiziqli dasturlash. Аgar maqsad funktsiyasi va oʼzgaruvchilarga qoʼyilgan

shartlar chiziqli (masalan koʼrinishda boʼlsa, u holda dasturlash
chiziqli dasturlash deyiladi. Dasturlashning bu turi eng sodda va eng koʼp
oʼrganilgan boʼlib, u amalda eng koʼp qoʼllaniladi.
2. Chiziqli boʼlmagan dasturlash. Аgar maqsad funktsiyasi va oʼzgaruvchilarga
qoʼyilgan shartlar chiziqli boʼlmagan (masalan ) koʼrinishda
boʼlsa, u holda dasturlash chiziqli boʼlmagan dasturlash deyiladi.
3. Dinamik dasturlash. Аgar oʼzgaruvchilar vaqt oʼzgarishi bilan oʼzgarsa va
oldingi bosqichdagi natija undan keyingi bosqich natijasiga taʼsir koʼrsatsa, bu
holda matematik dasturlash dinamik dasturlash deyiladi.
Bu turdagi dasturlar iqtisodiy masalalarda koʼp uchraydi.
Bundan tashqari yuqoridagi uch turdagi dasturlashdagi oʼzgaruvchilarning qabul
qilish qiymatlariga koʼra:

1. Diskret dasturlashtirish. Bunda oʼzgaruvchilar, baʼzi diskret (uzlukli)

qiymatlarini qabul qiladi.
2. Butun sonli dasturlashtirish. Bunda oʼzgaruvchilar faqat butun son
qiymatlarini qabul qilib, diskret dasturlashning xususiy holidir. (masalan
avtomobillar, binolar, pasajirlar).
3. Stoxastik dasturlashtirish. Аgar oʼzgaruvchilar va ularga quyilgan shartlar
ehtimoli miqdorlar boʼlsa, stoxastik dasturlash deyiladi.
Dinamik dasturlash — matematikaning koʻp bosqichli eng maqbul
(optimal) boshqarishga oid masalalar nazariyasi va ularni yechish usullarini
oʻrganuvchi boʻlimi. Bu yerda dasturlash tushunchasi "rejalashtirish", "qaror qabul
qilish", yaʼni "bir qarorga kelish" maʼnolarida ham qoʻllaniladi. Bu prinsip
dinamik dasturlashning asosiy masalasini oxiridan boshlab yechishga imkon
beradi. Dinamik dasturlash chekli bosqichli jarayonlardan tashqari, uzluksiz davom
etadigan jarayonlar uchun ham ishlab chiqilgan. U texnika, kosmik parvozlar, xalq
xoʻjaligini rejalashtirishning turli masalalarida eng maqbul yechimlar topishga
imkon beradi. Dinamik dasturlash usuli elektron hisoblash mashinalari,
kompyuterlar yordamida tatbiq qilinadi.

Dinamik dasturlash - bu matematik dasturlash bo'limlaridan biri bo'lib, unda

yechish jarayonini alohida bosqichlarga bo'lish mumkin. Ushbu bo'lish turli xil
printsiplarga muvofiq amalga oshiriladi. Ba'zi vazifalar vaqt bo’yicha,
boshqalarida boshqaruv ob'ektlari bo’yicha. Ba'zan bo'linish sun'iy ravishda
amalga oshiriladi. Ushbu yondashuv bizga bitta katta o'lchovli muammoni kichik
o'lchamdagi ko'plab muammolarga bo’lish imkonini beradi. Bu hisoblash hajmini
sezilarli darajada kamaytiradi va boshqaruv qarorlarini qabul qilish jarayonini
tezlashtiradi. Dinamik dasturlash tamoyili shundaki, eng optimal yo'lning har
qanday qismi optimaldir. Bu har bir bosqichda oldingi bosqichlarda topilgan
yo'lning qismlaridan foydalangan holda optimal yo'lni topishga imkon beradi.
Optimallashtirishning eng taniqli usullaridan biri bu o'tgan asrning elliginchi
yillarida amerikalik olim Richard Bellman tomonidan taklif etilgan dinamik
dasturlashdir. Dinamik dasturlashni ko'p bosqichli qarorlar qabul qilish
jarayonlarini tahlil qilishda ishlatiladigan matematik protseduralar to'plami sifatida
aniqlash mumkin. O'z navbatida, qaror qabul qilishning ko'p bosqichli jarayoni
umumiy maqsadga erishishga qaratilgan izchil qarorlar qabul qilinadigan faoliyat
sifatida belgilanishi mumkin. Dinamik dasturlashning mohiyati optimallashtirish
tamoyiliga asoslanadi. Buni shunday tariflash mumkin – optimal strategiya
shunday xususiyatga egaki, dastlabki holat va yechim qanday bo'lishidan qat'iy
nazar, keyingi yechimlar dastlabki qarordan keyin yuzaga keladigan holat uchun
eng optimal strategiyaga ega bo'lishi kerak.
2. Dinamik dasturlash masalalarini yechish sxemasi.
Ko'p bosqichli qarorlarni qabul qilish jarayonlari turli xil vaziyatlarda
uchrashi mumkin, masalan, zaxiralarni boshqarish, resurslarni taqsimlash yoki
kosmik kemalarni boshqarish vazifalari. Har bir ko'p bosqichli qarorlarni qabul
qilish jarayonini yo'naltirilgan tarmoqdagi eng qisqa yo'lni topishning eng
tushunarli ko'p bosqichli jarayonini ishlab chiqish deb hisoblsh mumkin (10.1-
rasm). Ushbu misoldan foydalanib, R. Bellmanning optimallashtirish tamoyili
mohiyatini namoyish etish mumkin.
Yo'naltirilgan tarmoq
Yo'naltirilgan tarmoq N qaror bosqichlariga ega bo'lsin. 10.1-rasmdan
ko’rinib turibdiki N = 5 ga teng. Quyidagi belgilashni kiritamiz:
n - bosqich raqami (n = 1, 2, 3, 4,5);
i - harakat amalga oshirilgan joy (i = 1, 2, ..., 8);
j - harakat yo'naltirilgan nuqta (j = 2, 3, ..., 9);
Sij - i nuqtadan j nuqtagacha bo'lgan masofa;
Sn (i) - bu masalani yechishning n-bosqichida i nuqtadan oxirgi nuqtagacha
bo'lgan minimal masofa.
Nuqta n-bosqichga tegishli deb taxmin qilinadi, agar undan aniq n bosqichda
yakuniy nuqtaga o'tish mumkin bo'lsa. Ko’rinib turibdiki, n-bosqichning biror

nuqtasidan 9-nuqtagacha bo’lgan minimal yo’l shu bosqichning qaysi nuqtasida

ekanligimizga bog'liq bo'ladi. N-bosqichga tegishli bo'lgan n-elementning raqami
tizimning n-bosqich holat o'zgaruvchisi bo'ladi. Optimallashtirish odatda jarayon
oxiridan boshlanadi, chunki n-bosqichning ba'zi nuqtalarida bo'lganligi sababli (n -
1) - bosqichning nuqtalaridan biriga o'tish to'g'risida qaror qabul qilinadi va
keyingi harakat yo'nalishi oldingi bosqichlardan ma'lum bo’ladi. (N - 1)
bosqichning j raqami n bosqichda boshqarish o'zgaruvchisi bo'ladi.
Birinchi bosqich (n = 1) uchun maqsad funktsiya (Bellman funktsiyasi)
birinchi bosqich (6, 7, 8) nuqtalaridan 9 oxirgi nuqtaga qadar bo'lgan minimal
yo'ldir, ya'ni S1 (i) = si9. Keyingi bosqichlar uchun yo'l uzunligi ikki yig’indidan
iborat –n-bosqichning i nuqtasidan j (n - 1)-bosqichning j nuqtasigacha bo’lgan Sij
yo’li va j nuqtadan oxirgi nuqtagacha bo'lgan yo'lning minimal uzunligi, ya'ni Sn -
1 (j). Shunday qilib, funktsional Bellman tenglamasi quyidagi shaklga ega bo'ladi:
Minimal uzunlik ma'lum bir qiymat j* da erishiladi, bu i nuqtadan oxirgi
nuqtaga harakatning optimal yo'nalishidir. Beshinchi bosqichda biz boshlang'ich
nuqtaga etib boramiz va tizimning holati i = 1 bo’lib aniqlangan bo’ladi. S5(1)
funktsiyasi 1-chi nuqtadan 9-nuqtagacha bo’lgan minimal yo’lni ifodalaydi.
Optimal yo'nalish barcha bosqichlarni teskari tartibda tahlil qilish orqali
aniqlanadi.
4. Masalalar
Eng qisqa yo'lni aniqlash algoritmi quyidagi bosqichlardan iborat:
1-qadam. n = 1, S1(i) = Si9. Birinchi bosqichda 9-nuqtaga ikkinchi bosqichning 6,
7, 8 nuqtalaridan borish mumkin. Shuningdek: S1(6) = 15; S1(7) = 3; S1(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.

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.
S4(1) = min {S12 + S3(2), S13 + S3(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 S4(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).
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:

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).