Bellmanův princip optimality
Dušan Polanský
Jsem člověk s vyloženě průměrným IQ – teď v 64. letech mi je to již šum a fuk, ale v mládí bych vyšší IQ bral –, takže mi docela dost dlouho trvá, než něco plně pochopím, přesněji strávím. Ono je vždy veliký rozdíl mezi pochopením čehokoli jenom povrchně, nebo poctivě do hloubky. Pascalův trojúhelník z kombinatoriky naučíte nakreslit i školáka, dokonce ho naučíte i pasivně jej používat, ale do hloubky pochopit jeho strukturu, to je již o něčem jiném. Dodnes škodolibě vzpomínám, jak ještě nedávno několik dobře placených výzkumných chytrolínů s vysokým IQ tvrdilo, že mají experimentální důkaz, že rychlost světla může být vyšší než oněch pověstných 300 000 km/s. To jsem se opravdu pobavil a trpělivě jsem čekal, kdy se ukáže, že jsou vedle, jak ta jedle. A také se ukázalo, že jsou. Tak či onak, jsou principy, jejichž pochopení dá zabrat většině lidí, i těm, které Bůh obdařil vysokým IQ.
Takovým principem podle mne je i Bellmanův princip optimality (BPO). Na první pohled BPO není nijak složitý princip, problémy nastávají teprve při jeho aplikaci, což zase není nic neobvyklého, znají to hlavně lidi z praxe. Na školní tabuli je vždy vše jasné. BPO má navíc jednu velikou vadu krásy, nedává konkrétní návod, jak řešit problém, na který BPO lze aplikovat. Pro každý konkrétní příklad je potřeba vymyslet, jak vůbec BPO na řešení problému aplikovat. Pochopitelně předem si je potřeba ujasnit, zda lze BPO na problém aplikovat, protože ne každý optimalizační problém lze pomocí BPO řešit. BPO vám uvedu ve formulaci, jak mu rozumím já. V knihách o optimalizaci lze najít explicitnější formulaci, která pracuje s pojmy: systém, stav systému, optimální trajektorie. Těmto pojmům se raději vyhneme a navíc chceme vystačit s terminologií a znalostmi matematiky ze základní školy. Nakonec když něčemu doopravdy rozumíte, tak by vám vždy látka ze základní školy měla na výklad postačit.
BPO: Řešený problém splňuje princip BPO, když jeho řešení může být rozloženo na řešení dílčích podproblémů tak, že optimální řešení celého problému obsahuje i optimální řešení těchto dílčích podproblémů.
Co vlastně tímto obecným tvrzením říkáme? Podívejte se na obrázek č. 1 (číslo obrázku zjistíte po najetí myší na něj). Je na něm graf ne příliš rozsáhlé silniční sítě. Uzly jsou označeny písmeny u s příslušnými indexy, vzdálenosti mezi uzly písmenem d a dvěma indexy, první index je číslo uzlu, z něhož vzdálenost měříme, druhý číslo uzlu, do něhož vzdálenost měříme. Pro jednoduchost předpokládejme, že indexy lze prohodit, což v praxi vždy nemusí platit. Tyhle situace známe hlavně z měst, kde se jezdí i po jednosměrkách, takže nejednou trasa z bodu A do bodu B je jiná než z bodu B do bodu A. Náš graf je navíc čistě schematický, to znamená, že vyjadřuje pouze strukturu sítě, ale vzdálenosti mezi uzly jsou dány čísly a ne naměřenou vzdáleností pravítkem z našeho obrázku. Podobné obrázky známe např. z plánů metra v metropolích. Nejsou sice v měřítku, ale přitom zachycují to podstatné: strukturu sítě a křižování tras. Na obrázku vidíme podbarvenou nejkratší trasu z uzlu u1 do u9. Teď si představme, že by nás zajímala nejkratší trasa z u3 do u6. BPO nám říká, že pokud hledání nejkratší trasy bylo možné rozložit tak, že optimální řešení celého problému obsahuje i optimální řešení dílčích podproblémů, tak nejkratší trasa z u3 do u6 leží opět na nejkratší trase z u1 do u9. Na první pohled je to logické, vždyť pokud by vedla nejkratší trasa z u3 do u6 např. po trase u3, u4, u7, u6, není žádný důvod, aby i nejkratší trasa z u1 do u9 nevedla také po trase u3, u4, u7, u6.
Teď si možná říkáte, že tohle je víc než jasné a že vlastně ani nevíte, proč vůbec vedu tolik řečí o takové samozřejmosti. Ne, tohle není vůbec samozřejmé! V technické praxi, ale i v lidském životě totiž narážíme na problémy, u nichž výše uvedena podmínka není automaticky splněna, tedy dílčí optimální řešení nejsou podmnožinou celkového optimálního řešení. Příklad ze života: právě jste skončil střední školu a máte nabídku dobře placené práce na plný úvazek. Rodiče vás přemlouvají, abyste to nebral, ale raději pokračoval ve studii na kvalitní vysoké škole, že zatím sice budete muset peníze oželet, ale později se vám s velikou pravděpodobností vrátí i s úroky. Shrnuto: podle názoru rodičů se váš život bude s velikou pravděpodobností odvíjet lépe, když vystudujete vysokou školu, než když nastoupíte do práce hned po střední škole a výšku nikdy nevystudujete. Pokud vás přesvědčí a vy výšku vystudujete a budete mít v životě profesní úspěch, tak pracovní poměr po střední škole bez vystudování vysoké školy neleží na vaší profesně optimální trase, ač z hlediska krátkodobého se jevil pracovní poměr po střední škole jako velice výhodný (jsou mezi námi občas i takoví, jež nechtějí být ekonomicky závislý na rodičích; nakonec i já jsem vypadl z domu v 19. letech a již jsem si nikdy nevzal od rodičů ani korunu). Pochopitelně lze namítnout, že profesní úspěch nemusí znamenat úspěch v osobním životě. Možná, že jenom se střední školou byste potkali vhodnějšího partnera, ale to je již jiná báseň. Na složitosti života se obvykle nehodí žádná matematika ani žádné principy.
I my teď budeme hledat jakousi optimální trasu. Sice ne životem, ale délkově nejkratší trasu v rámci jakési uměle vymyšlené silniční sítě. Pokusíme se tuhle trasu najít aplikováním BPO. Silniční síť jsem převzal z jednoho videa na internetu. Na příkladu mě zaujalo, že pán, co BPO vykládá, neupozornil diváky, že ještě existují další dvě řešení se stejnou minimální délkou, ale hlavně nevysvětlil, jak je systematicky najít. Jinak na zadání sítě opravdu vůbec nezáleží, postup řešení – jak pozná i naprostý laik – je naprosto stejný, mechanický. Pochopitelně pokud je síť rozsáhlejší je rozumné si vzít na pomoc PC a zvolit propracovanější algoritmus hledání nejkratší trasy, např. Dijkstrův algoritmus. Ale to je již mimo rozsah našeho povídání; nakonec jsou o tom k dostání knihy pojednávající o optimalizaci nebo grafových algoritmech.
Teď se podívejme na obrázek č. 2. Naše zadání je prosté: dostat se nejkratší trasou z počátečního uzlu A do koncového uzlu J. Každý motorista dobře ví, že délkově nejkratší trasa nemusí být časově nejkratší či nejbezpečnější, ale tyhle typy motoristických úvah teď zcela zanedbáme. Všimněme si, že uzly sítě jsou uspořádané do jakýchsi 5 pomyslných pásem: A; B, C, D; E, F, G; H, I a koncový uzel J. Tyhle pásma nejsou ničím umělým, jednoduše vyjadřují vzájemnou dosažitelnost uzlů ze sousedních uzlů. Úlohu se pokusíme vyřešit dvěma způsoby. Při prvním budeme postupovat úmyslně velmi laicky z uzlu A do uzlu J, v druhém z uzlu J k uzlu A, přičemž využijeme BPO.
Takže úmyslně postupujme z uzlu A do uzlu J podle jednoduchého algoritmu. Pokaždé najdeme nejkratší trasu z jednoho pásma do sousedního, přičemž začínáme v uzlu A. A budeme si myslet (nesprávně), že pokud z těchto nejkratších tras mezi pásmy uzlů složíme i trasu celkovou, že i trasa celková bude minimální. Jistě v speciálních případech to může být pravda, ale obecně to platit nebude. V našem příkladu výsledkem našeho postupu je červená trasa. Její délka je 13 délkových jednotek. Zbytečně nespekulujme, zda to je, nebo není nejkratší trasa. V našem jednoduchém příkladu i běžným pohledem lze zjistit, že jsou možné i kratší trasy. Jenomže kdyby uzlů bylo např. několik stovek, už tak jednoduše bychom si tuhle skutečnost neověřili.
Teď budeme postupovat od koncového uzlu J k počátečnímu uzlu A, přičemž aplikujeme BPO. Než se do toho pustíme, zavedeme si jedno důležité označení. F(X) bude minimální vzdálenost potřebná k dosažení uzlu J, tedy koncového uzlu, z uzlu X. Kupříkladu F(B) znamená minimální vzdálenost z uzlu B do koncového uhlu J. Paralelně s výkladem budeme sledovat výpočty na obrázku č. 2 pod schématem silniční sítě. Zatím si ale vůbec nebudeme všímat tečkovaných kroužků ani svislic po levé straně. Je zřejmé, že F(J) = 0. Proč? Protože když budeme v uzlu J, tak minimální vzdálenost k dosažení uzlu J je 0 délkových jednotek. Podobně F(H) = 3 a F(I) = 4. Zatím se neděje nic zajímavého, ale přesuňme se k pásmu uzlů E, F, G. Zkusme spočíst F(E). Jak budeme uvažovat? Z uzlu E vedou spojnice do uzlů H (délka spojnice je 1) a I (délka spojnice je 4), takže F(E) bude minimum z 1 + F(H) a 4 + F(I). Příjemné je, že F(H) a F(I) již známe, takže bez problémů lehce spočteme minimum: 1 + 3 = 4, 4 + 4 = 8. Minimum z těchto dvou hodnot je 4. Funkci min {1 + F(H), 4 + F(I)} říkáme Bellmanova funkce. Naše podoba této funkce se hodí pouze pro námi řešený problém. V tom je celá potíž, že pro každý jednotlivý problém má Bellmanova funkce jiný tvar, nakonec je to logické již jenom proto, ne vždy minimalizujeme, často hledáme maximum, např. pokud chceme dosáhnout maximálního zisku z investovaných peněz. Šikovnost naší Bellmanové funkce je v tom, že při jejím výpočtu pro určitý uzel již známe z předchozího výpočtu hodnoty F(X), jež se v Bellmanové funkci pro určitý uzel vyskytují. To je nakonec pointa všech výpočtů podle BPO. Kdybychom řešení podproblémů F(H) a F(I) neznali, nevyřešili bychom ani problém F(E), jenž tyhle podroblémy obsahuje.
K čemu jsme se zatím dopracovali? Pouze víme, že nejkratší vzdálenost z uzlu E do uzlu J je 4 jednotky. To automaticky neznamená, že i celá optimální trasa z uzlu A do uzlu J musí vést právě přes uzel E. Zatím jsme neprozkoumali uzly F a G. Výpočet F(F) a F(G) vidíme na obrázku č. 2. Běžným pohledem vidíme, že z uzlů v pásmu E, F, G je shodou náhod nejvýhodnější trasa do uzlu J opravdu z uzlu E. To nám ale stále negarantuje, že celá optimální trasa z uzlu A do uzlu J povede přes uzel E. Výpočet F(B), F(C), F(D) a F(A) teď jistě zvládlete i sami. Délka minimální trasy nám vyšla 11 jednotek.
Opět si zrekapitulujme, k čemu jsme se zatím dopracovali. Spočetli jsme, že minimální trasa má délku 11 jednotek, což je výborný výsledek, vždyť trasa, kterou jsme našli předchozí metodou měla 13 jednotek. Teď jde o to zjistit, přes které uzly minimální trasa povede. Mohli bychom uvažovat nějak takhle: v každém pásmu si tečkovaným kroužkem vyznačíme minimální hodnotu, přece hledáme minimální trasu! Vidíme, že minimální trasa – je vyznačena tečkovaně – vede z uzlu A do uzlu J vede přes uzly C, E, a H. Kontrolní výpočet ukazuje, že opravdu vzdálenost je 11 jednotek. Ale možná je tento postup jenom výsledkem náhodné trefy. Stačí když se podíváme pozorně na naši silniční síť, jsou tam ještě dvě trasy s délkou 11 jednotek, jedna je vyznačena čerchovaně a druhá křížky. Jak vlastně systematicky vypsat všechny trasy o délce 11 jednotek?
Systematický postup nalezení všech tras s minimální délkou si teď pečlivě vysvětlíme. Pro lepší orientaci jsme uzly v jednom pásmu označili svislicí na levém boku a navíc jsme pásma oddělili vodorovnou čarou.
Začneme od posledního řádku s výpočtem F(A), přesněji od posledního řádku, v němž jsme se dopracovali k délce minimální trasy 11. Vidíme, že délka 11 nám vyšla výpočtem dvou výrazů: 4 + F(C) a 3 + F(D). Tím víme, že minimální trasy určitě půjdou v prvním pásmu přes dva uzly C a D. Začneme uzlem C. V řádku pro výpočet F(C) minimální hodnota 7 nám vyšla výpočtem výrazu 3 + F(E), tím je jasné že trasa půjde přes uzel E. V řádku pro výpočet F(E) nám minimální hodnota 4 vyšla výpočtem výrazu pro 1 + F(H), takže víme, že minimální trasa půjde přes uzel H. Tím máme určenou první minimální trasu, tečkovanou. Zapišme si ji: A -> C -> E -> H -> J.
Teď půjdeme přes uzel D, protože při výpočtu F(A) minimální hodnota 11 vyšla i výpočtem výrazu 3 + F(D). Podíváme se na řádek pro výpočet F(D). Vidíme že, minimální hodnota 8 vyšla výpočtem dvou výrazů: 4 + F(E) a 1 + F(F). Vydejme se prvně uzlem E. Řádek s výpočtem F(E) nám říká, že minimální hodnota 4 vyšla výpočtem výrazu 1 + F(H), čímž je jasné, že předposledním uzlem minimální trasy bude H. Zapišme si druhou minimální trasu, čerchovanou: A -> D -> E -> H -> J.
Když si pozorně přečteme předchozí odstavec, v uzlu D jsme měli dvě volby: E a F. Volbu E jsme již využili, teď se vydáme uzlem F. V řádku pro výpočet F(F) minimální hodnota 7 vyšla výpočtem 4 + F(I), čímž víme, že naše minimální trasa půjde přes uzel I. Zapišme si poslední, třetí, minimální trasu, je vyznačena křížky: A -> D -> F -> I -> J.
Právě výpočet uvedený ve třech posledních odstavcích mi vždy chyběl ve všech výkladech BPO, které jsme kdy četl. Vše bylo podáno složitě, přes rafinované označení, tabulky, brr.
Zkusme si jalespoň námatkově ověřit, že opravdu při našem postupu hledání minimální trasy z uzlu A do uzlu J platí BPO. Jak na to? Zvolme si dva libovolné uzly na některé z třech minimálních tras a zkusme najít nejkratší trasu z jednoho z těchto uzlů do druhého. Musí pokaždé ležet na celé minimální trase z uzlu A do uzlu J. Pokud by tomu tak nebylo, námi nalezené minimální trasy jsou sice shodou náhod správné, ale náš postup nevyužívá BPO. Kontrolu si proveďte i pro zbývající dvě minimální trasy.
Pochopitelně si nejeden čtenář položí otázku, zda lze námi použitý postup s využitím BPO použít i při postupu z bodu A do bodu J. Ano, lze. Řešení s krátkým komentářem najdete v dodatku.
Závěrem hlavního textu jedno malé terminologické vysvětlení. V souvislosti s BPO se mluví o dynamickém programování. Proč? Především programováním se zde nerozumí programování v tom slova smyslu, jak mu rozumíme intuitivně dnes, tedy psaní programového kódu v programovacím jazyce. Dynamické programování, lineární programování, nelineární programování a další jsou historické poválečné názvy pro techniky používané pro řešení optimalizačních úloh. Kupříkladu při lineárním programování se sestaví model systému, který chceme optimalizovat, včetně omezujících podmínek (jednak které plynou přímo z omezení modelu a pak obvykle z požadavku nezápornosti proměnných) a funkce (obvykle se jí říká účelová funkce), kterou chceme maximalizovat, nebo minimalizovat. Celý model se pak naťuká např. do tabulkového procesoru Excel, aplikuje se vhodná metoda řešení soustavy rovnic a obvykle za rozumnou chvíli – pokud model není příliš rozsáhlý – nám Excel vychrlí výsledek. Nakonec o lineárním programování jsem již povídání napsal. Odkaz je zde. Název lineární programování pochází z toho, že neznáme veličiny vystupují pouze v lineárním tvaru. U nelineárního programování některé z neznámých vystupují i ve vyšších mocninách. Ovšem řešení těchto úloh není dynamické. Představte si, že naši úlohu s nalezením minimální trasy bychom řešili na počítači, což se dnes obvykle i děje. Opět bychom silniční síť v nějaké předepsané formě zadali do počítače a na vlastní výpočet bychom použili program, který by problém řešil stejnou technikou, jakou jsme mi použili na obrázku č. 2. Program by musel postupovat naprosto stejně, jako jsme postupovali my. Mimo jiného by si musel uchovávat výsledky řešení dílčích podproblémů, aby mohl vyřešit i problémy, které tato dílčí řešení obsahují. A nejen to, když jsme systematicky hledali všechny minimální trasy, museli jsme si pamatovat, pro které uzly nám vyšli minimální hodnoty Bellmanové funkce a podle těchto uzlů pak větvit další výpočet. Tedy i výpočet počítačem by byl dynamický, krok po kroku, neřešil by problém jaksi najednou, jako když řešíme např. soustavu lineárních rovnic v případě lineárního programování. Ale i přes složitost dynamických výpočtů je to často výhodnější metoda než vyzkoušet všechny možnosti (v našem příkladu všechny možné trasy). Nakonec i proto BPO spatřil světlo světa.
Dodatek. Výše jsme se zmínili, že lze postupovat s použitím BPO i od uzlu A do uzlu J. Nesmíme si to ale plést s postupem od uzlu A k uzlu J na prvním obrázku, tam jsme aplikovali vyloženě jednoduchý přístup. Výpočet by měl být zřejmý z obrázku č. 3. Ovšem je tu jeden podstatný rozdíl; F(X) zde označuje minimální vzdálenost k dosažení A z uzlu X, výše to byla vzdálenost k dosažení koncového uzlu J. Opět jsme se dopracovali k délce minimální trasy 11 jednotek. Vlastní minimální trasu po výpočtu příslušných Bellmanových funkcí hledáme teď od koncového uzlu. Na obrázku je vyznačena jenom jedna minimální trasa, postup jejího nalezení je naznačen tečkováním. Další dvě minimální trasy si jistě najdete sami postupem popsaným výše.
V Brně 15. února 2016.