TAR2_20120308 02 Dynamické programovanie pre diskrétne systémy

Zhrnutie prednášky

Prednáška predstavuje koncept diskrétneho dynamického programovania na príklade multistage optimalizačného problému – prechodu cez sériu domov s tromi poschodiami (poschodie, prízemie, suterén), kde cieľom je nájsť trasu s minimálnymi nákladmi. Ukazuje sa, prečo naivná rekurzia od začiatku je neefektívna kvôli opakovanému prepočítavaniu rovnakých hodnôt, a preto sa problém rieši spätne od koncového bodu pomocou Bellmanovho princípu optimality. Pre každý uzol sa počíta a ukladá optimálna hodnotová funkcia aj optimálny smer ďalšieho kroku, čím sa získa kompletná optimálna stratégia z akéhokoľvek bodu grafu. Následne sa problém formalizuje ako úloha riadenia diskrétnych systémov so stavom, riadením, diskrétnou dynamikou (diferenčnou rovnicou) a účelovou funkciou, pričom sa odvádza všeobecná Bellmanova rovnica dynamického programovania pre diskrétne systémy analogická spojitému prípadu, riešená spätným postupom od konečného času N.

• - Diskrétne dynamické programovanie rieši multistage optimalizačné problémy s konečnou množinou riadení
• - Príklad: prechod sieťou domov s poschodiami, minimalizácia celkových nákladov trasy
• - Naivná rekurzia od začiatku je neefektívna kvôli duplicitnému prepočítavaniu rovnakých podproblémov
• - Riešenie sa počíta spätne od koncového stavu s nulovou hodnotou účelovej funkcie
• - Pre každý uzol sa ukladá optimálna hodnota aj optimálny smer ďalšieho kroku (Bellmanov princíp optimality)
• - Formalizácia úlohy: stav (poschodie), riadenie (hore/rovno/dole), diskrétna dynamika ako diferenčná rovnica
• - Odvodenie Bellmanovej rovnice pre diskrétne systémy: J(k)=min_U [L(x,u,k)+J(k+1,x(k+1))], riešené odzadu od N

Zhrnutie pripravené s pomocou AI z prepisu videa.