TAR2_20170425 04 Dynamické programovanie pre diskrétne systémy

Zhrnutie prednášky

Prednáška predstavuje princíp dynamického programovania pre diskrétne systémy na príklade cesty z Bratislavy do Košíc, kde sa vyberá medzi troma trasami (poschodia -1, 0, 1) v piatich etapách s cieľom minimalizovať celkové náklady. Ukazuje sa, že dopredný výpočet je neefektívny, keďže vyžaduje opakované prepočítavanie, preto sa zavádza spätný postup od koncového stavu, kde sa v každej etape a stave uchováva optimálna hodnota kriteriálnej funkcie a príslušné optimálne riadenie. Postupným napĺňaním tabuľky dynamického programovania od poslednej etapy po prvú sa nájde globálne optimálne riešenie s minimálnou cenou 8, pričom optimálna trajektória sa následne rekonštruuje spätným prechodom tabuľkou. Na záver sa úloha formalizuje ako všeobecný problém optimálneho diskrétneho riadenia opísaného diferenčnou rovnicou s obmedzeniami na stavy a riadenia, kde sa v každej etape minimalizuje súčet lokálnych nákladov a hodnotovej funkcie nasledujúcej etapy.

• - Diskrétne dynamické programovanie sa demonštruje na príklade voľby optimálnej trasy medzi troma cestami (stavy -1, 0, 1) v piatich etapách.
• - Dopredný spôsob výpočtu je neefektívny, pretože nevyužíva opakovane už spočítané hodnoty.
• - Spätný (backward) postup od koncového stavu umožňuje pri každom kroku využiť už vypočítané optimálne hodnoty nasledujúcej etapy.
• - Pre každý stav a etapu sa v tabuľke ukladá optimálna hodnota kriteriálnej funkcie aj zodpovedajúce optimálne riadenie.
• - Optimálna trajektória sa po naplnení tabuľky rekonštruuje spätným prechodom od začiatočnej etapy.
• - Úloha sa formalizuje ako diskrétny systém opísaný diferenčnou rovnicou (nasledujúci stav = súčasný stav + riadenie) s obmedzeniami na množinu prípustných riadení podľa aktuálneho stavu.
• - Princíp optimality dynamického programovania spočíva v minimalizácii súčtu nákladov aktuálnej etapy a hodnotovej funkcie nasledujúcej etapy.

Zhrnutie pripravené s pomocou AI z prepisu videa.