|
Algoritmdan jadval yordamida foydalanish
|
| bet | 3/3 | | Sana | 18.02.2024 | | Hajmi | 241,03 Kb. | | #158458 |
Bog'liq 7-ma’ruza Dinamik programmalashtirish usuli4. Algoritmdan jadval yordamida foydalanish
qiymatlar bilan birga (6) ga maksimum beruvchi va (5) ga maksimum beruvchi sonlarni ham yozib qo’yamiz (agar (5) va (6) ga maksimum beruvchi nuqtalar bir nechta bo’lsa, ularning hammasi yoziladi). Jadvalni to’ldirgandan so’ng (7) bo’yicha formula bo’yicha (1) masala yechimi ni osongina aniqlash mumkin.
Algoritmdan jadval yordamida foydalanish qo’lda bajariladigan hisoblashlar uchun tavsiya qilinadi.
Eslatma. Asosiy bog’lanish tenglik ko’rinishda bo’lganda (ya’ni ) sonlarni jadvalga yozish shart emas. Bu holda (1) masala yechimining koordinatasini formula bilan topamiz.
1-jadval
|
0
|
1
|
2
|
…
|
|
…
|
|
|
|
|
|
…
|
|
…
|
|
|
|
|
|
…
|
|
…
|
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
|
|
|
|
…
|
|
…
|
|
2-misol.
bu yerda butun qiymatlar qabul qiladi.
Yechish. Berilgan masala uchun
2-jadvalni to’ldiramiz. Birinchi qatorga quyidagi sonlarni yozamiz:
Ikkinchi satrni to’ldiramiz:
Xuddi shunga o’xshash, jadvalning uchinchi satrini funksiyaning
ifodadan aniqlanuvchi qiymatlar lar va bu ifodaga maksimum beruvchi sonlar bilan to’ldiramiz.
2-jadval
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
|
0
0
|
1
|
2
2
|
3
|
8
4
|
5
|
18
6
|
|
0
0
|
0
|
2
0
|
0
|
8
0
|
0
|
18
0
|
|
0
0
|
0
|
2
0
|
0
|
8
0
|
0
|
18
0
|
Tuzilgan jadvalning oxirgi ustuni berilgan masala yechimini aniqlaydi, chunki (7) formulaga ko’ra.
Maqsad funksiyasining maksimal qiymati
Mustaqil ishlash uchun savollar
1. Qaralayotgan (1) masalani dinamik dasturlash usuli bilan yechishning asosiy bosqichlari.
2. Bellman funksiyasi, Bellman tenglamasi.
3. Dinamik dasturlash usuli bilan o’zgaruvchilari butun qiymatli bo’lgan (1) masalani yechish algoritmi.
4. Algoritmdan jadval yordamida foydalanish qanday bajariladi?
Mustaqil bajarish uchun topshiriqlar
1. Dinamik dasturlash metodidan foydalanib quyidagi masalalarni yeching:
1)
2)
3)
4)
5)
6)
7)
8)
2. Dinamik dasturlash usuli bilan o’zgaruvchilar butun qiymatli bo’lgan quyidagi masalalarni yeching (jadvaldan foydalaning):
1)
2)
3)
4)
5)
6)
7)
8)
Mavzuni mustahkamlash uchun tavsiya etiladigan adabiyotlar
Вагнер Г. Основы исследований операции. Т. 1–3. М.: Мир. 1972-73.
Зайченко Ю. Б. Исследование операций. Киев. 1979.
Таха Х. Введение в исследование операций. Т. 1, 2. М.: Мир. 1981.
|
| |
