`O‘zbekiston respublikasi

Беллманнинг функционал тенгламалари” ёки “Динамик дастурлашнинг асосий функционал тенгламалари” деб аталади.
Ушбу тенгламалар ёрдамида динамик дастурлашнинг  босқичидаги ечимини сўнгги  босқичдаги ечими орқали топилади. Шунинг учун юқоридаги муносабатлар Беллманнинг реккурент муносабатлари деб аталади.
4. Масалалар


Энг қисқа йўлни аниқлаш алгоритми қуйидаги босқичлардан иборат:
1-қадам. н = 1, С1(и) = Си9. Биринчи босқичда 9-нуқтага иккинчи босқичнинг 6, 7, 8 нуқталаридан бориш мумкин. Шунингдек: С1(6) = 15; С1(7) = 3; С1(8) = 10.
2-қадам. Н = 2, бу ерда биз учинчи босқичнинг (4 ва 5) нуқталаридан иккинчи босқичга қадар бўлган йўлларни кўриб чиқамиз. Бу ерда функционал Беллман тенгламаси қуйидаги шаклга эга бўлади:

Шунингдек қуйидагига эга бўламиз:

Шартли равишда оптимал йўл (5-7);



Шартли равишда оптимал йўллар (4-6 ва 4-8).
3-қадам. н = 3, бу ерда тўртинчи босқичнинг (2 ва 3) нуқталаридан учинчи босқичгача бўлган йўлларни кўриб чиқилади.

Шартли равишда оптимал йўл (2–5).

Шартли оптимал йўл (3-4).


4-қадам. н = 4, бу эрда 1-нуқтадан тўртинчи босқичнинг нуқталаригача бўлган йўлларни кўриб чиқилади.
С4(1) = мин {С12 + С3(2), С13 + С3(3)} = мин {(1 + 22); (2 + 20);} = 22.
Шартли равишда оптимал йўл (1-3).
Энди биз 1-нуқтадан 9-гача бўлган энг қисқа шартсиз йўлни топамиз. Шартли оптималлаштириш босқичида минимал йўлнинг узунлиги С4(1) = 22 эканлиги аниқланди, бу натижа биринчи нуқтадан учинчисига ўтганда эришилади, кейин тўртинчисига ўтиш керак. Ушбу босқичдан бошлаб, 2-босқичда кўрсатилгандек, 6 ва 7-нуқталарга иккита мумкин бўлган эквивалент йўналиш мавжуд. Шундай қилиб, оптимал ечимга 10.2-расмда кўрсатилган иккита йўналиш орқали эришилади, аниқроғи (1-3–4–6–9) ва (1-3–4–8–9).

10.2-расм. Оптимал йўл
Динамик дастурлаш одатда муаммоларни ечишда иккита ёндашувга амал қилади:
Юқоридан пастга: вазифа кичикроқ қисмларга бўлинади, улар ҳал қилинади ва кейин асл муаммони ҳал қилиш учун бирлаштирилади. Тез-тез учрайдиган кичик қисмларни ечимлари хотирада сақланади.
Қуйидан юқорига: Дастлабки муаммони ҳал қилиш учун керак бўладиган барча пастки жадваллар олдиндан ҳисоблаб чиқилади ва кейинчалик асл муаммони ҳал қилишда фойдаланилади. Ушбу усул керакли стек ҳажмининг катталиги ва функцияларни чақириш сони нуқтаи назаридан юқоридан пастга бўлган динамик дастурлашга қараганда яхшироқдир, аммо баъзида келажакда биз учун қайси кичик масала натижаси керак бўлишини олдиндан аниқлаш осон эмас.
Одатда динамик дастурнинг ишлаш вақти қуйидаги функциялардан иборат:
Олдиндан ишлов бериш
Лооп фор лоопи неча марта ишлайди
Қайта ишлашни такрорлаш учун бирида ишлаш учун қанча вақт кетиши керак
Пост-қайта ишлаш
Умуман олганда, иш вақти қуйидаги шаклда бўлади:
Дастлабки ишлов бериш + Лооп * Такрорлаш + Пост-ишлаш
Динамик дастурлар учун катта-О билан танишиш учун пунчcард муаммосининг ишлаш вақтини таҳлил қилайлик. Бу ерда пунчcард муаммолари динамик дастури:
деф пунчcардСчедуле (н, қийматлар, кейинги):
# Эслатма қаторини бошланг - 4 босқич
мемо = [0] * (н + 1)
# Асосий корпусни ўрнатиш
мемо [н] = қийматлар [н]
# Н дан 1 гача хотиралар жадвалини тузинг - 2 босқич
диапазондаги и учун (н-1, 0, -1):
мемо [и] = макс (в_и + мемо [нехт [и]], мемо [и + 1])
# ОПТ (1) муаммосига эчим - 3 босқич
қайтиш эслатмаси [1]
Унинг иш вақти бузилсин:
Дастлабки ишлов бериш: Бу ерда ёдлаш массивини яратиш керак. О (н).
Лооп неча марта ишлайди: О (н).
Лооп итерацияси учун бирида ишлаш учун такрорийлик қанча вақтни олади: такрорланиш доимий ишлаш вақтини олади, чунки ҳар бир итерацияда иккита вариант ўртасида қарор қабул қилинади. О (1).
Пост-қайта ишлаш: Бу ерда йўқ! О (1)


Муаммоли динамик дастурнинг умумий иш вақти О (н) О (н) * О (1) + О (1) ёки соддалаштирилган шаклда О (н).