V životě se občas setkáváme s problémy, které mají učebnicově jasné řešení, ale spoustu jiných se nám nijak hezky lousknout nepodaří. Stojí tedy za trochu námahy, vymyslet si nějaké postupy do zoufalých situací, a celý tenhle těžký svět přitom prozkoumat trochu s odstupem. Následující zápisky se pochopitelně věnují jen počítačovým problémům.

Řešení hrubou silou

Když neumíme správné řešení jen tak spočítat, můžeme vyzkoušet všechna možná řešení a jednou to klapne. Ukázkou tohohle postupu je lámání hesel: máme kódový zámek, který na všechny kombinace krom té správné odpovídá nevlídným zavrčením. Pokud z něj nedovedeme šperhákem vyšťourat nebo stetoskopem odposlechnout nějaké další informace, nezbývá než zkoušet jeden kód za druhým.

V tomhle případě jsou kódy čísla od 0000 do 9999 a my pevně věříme, že jedno z nich zabere, takže je určitě rozumné je projít v nějakém pořadí všechny. Podobný postup jde použít i na lámání hesla neznámé délky: nejdřív vyzkoušíme všechny kódy délky 1, pak všechny kódy délky 2, a tak pokračujeme až do nekonečna. Věříme, že to jednou vyjde.

Případy, kdy nemáme zaručené, že některé heslo bude správné, jsou úplně jiná kategorie a věnuje se jim jiná stránka zápisků. Takové případy buďto vedou ke správnému řešení, anebo k navěky zaseknutému počítači, který se neodvažujeme vypnout, protože by třeba hned v příštím kroku už mohl heslo najít.

Strom řešení

Naše pokusy o řešení většinou nebudou tak přehledně uspořádané jako v případě čísel 0000 až 9999. Abychom si udělali ve věcech pořádek, představíme si, že všechny naše pokusy budou vrcholy nějakého stromu – grafu s jedním kořenem, kde každý vrchol má svého rodiče. Kořen toho grafu bývá něco na způsob prázdného hesla (0 znaků), a jeho potomci postupně přibývají na složitosti.

Problém obchodního cestujícího

Zbytkem zápisků nás bude provázet podomní obchodník, který si hledá optimální cestu mapou. Musí navštívit každé město (nebo každý dům, chcete-li), ale protože většina zákazníků toho vlezlého šmelináře od prvního setkání nenávidí, nesmí se nikam podruhé vrátit. Jedna otázka je, jestli vůbec jde mapu projít a každé místo navštívit akorát jednou, a druhá je, jak to udělat co nejkratší cestou. Zajímavé je, že obě ty otázky jsou stejně těžké, a to hodně těžké.

Každý pokus o řešení je pole měst, a jejich pořadí v poli je pořadí, v jakém je chceme projít. Správné řešení je pochopitelně takové, že mezi každou dvojicí měst v seznamu vede hrana, a krom toho je tam každé město z mapy napsané přesně jednou. Při budování stromu začneme řešení zjevně nesprávnými, ale nadějnými: kořen bude prázdné pole, a jako syny bude mít každé město na mapě. Dál se strom větví tak, že na konec každé cesty přidáme všechny sousedy, kam jde pokračovat. Nemá smysl zkoušet cesty s víc městy, než kolik jich je na mapě, takže strom řešení má konečnou velikost – přesto je ale nehorázně obrovský.

Objevují se nám dva různé grafy: jeden je mapa velikosti n, a podle ní vybudujeme strom řešení, který může být velký až nn (en na entou). Neplést.

Backtracking

Strom řešení nemá smysl ukládat do paměti počítače ani se o to pokoušet, protože v některých případech může být větší než viditelný vesmír. Tak zlé případy se nám sice nejspíš stejnak nepovede vyřešit, ale určitá naděje existuje, když budeme pečliví a chytří. Pro začátek pojďme strom řešení celý projít – nejlíp do hloubky, protože je to úsporné na paměť.

Pole vrchol.synove, jak ho známe ze zápisků o procházení stromem, nám nespadne jen tak do klína, budeme ho muset spočítat. Vrchol je pokus o řešení, tedy nějaká cesta po mapě. Každý její syn je tatáž cesta prodloužená z posledního města do některého jeho souseda. Když náhodou vyrobíme cestu, kde se některé město opakuje, můžeme ji bez rozmyslu zahodit, protože i všichni její synové by byli takhle zmrzačení. Naopak, jakmile vyrobíme cestu s n městy, tak tam jsou všechna (protože už víme, že se neopakují) a proto máme správný výsledek. Program může běžet dál v případě, že chceme najít nejkratší takovou cestu.

Tuhle úlohu jsme řešili rekurzí na cvičení z 3. května. Na té stránce máte už úlohu vyřešenou, takže si ji můžete vyzkoušet.

Branch and Bound

Když hledáme nejlepší řešení, nemusíme backtracking slepě pouštět na všechny možnosti. Jakmile najdeme jedno řešení, dá nám to jistotu, že ničím delším nemá smysl se vůbec zabývat. Od té chvíle tedy má smysl si každý pokus o řešení odhadnout, do jak pěkného výsledku se dovede vyvinout, a když už to nemá šanci zlepšit náš dosavadní úspěch, tak ten pokus i všechny jeho potomky zahodíme.

Jak se může pokus o řešení vyvinout? Především, přidáváním vrcholů na konec délka cesty jedině roste. Když tedy neúplný pokus je delší než řešení, které jsme našli někdy dřív, tak chceme tuhle větev stromu uříznout.

Možná dovedete vymyslet těsnější odhad – například na základě toho, že do seznamu obsahujícího k měst je potřeba ještě n - k měst dopsat a délku několika nejkratších hran na mapě si můžete v programu jednou předpočítat.

Zkuste na stránce cvičení napsat co nejrychlejší program na řešení problému obchodního cestujícího. S pomocí rad pod zadáním lze během několika vteřin řešit například zadání velikosti 33; na druhou stranu, zadání velikosti 30 nemá řešení, takže program musí vyzkoušet opravdu všechny možnosti a výpočet trvá věky.

IDA* (Iterative Deepening A*, procházení do čím dál větší hloubky)

Co když řešení může být libovolně dlouhé? Strom řešení pak je nekonečně hluboký, z každého řešení jde pokračovat dál. Chtěli bychom pustit backtracking, jenže nemáme záruku, že vůbec někdy doběhne – mohl by se v tom nekonečnu utopit a nikdy nenajít jediné správné řešení.

Například se snažíme co nejrychleji vyřešit hlavolam Loydova patnáctka. Přirozeně, mohli bychom si na Wikipedii přečíst, že nejsložitější zadání jde vyřešit na 80 tahů, a spustit backtracking na všechna řešení délky 0 až 80. Jednak je to ztráta času, když zrovna náhodou stačí tři správné tahy (při troše smůly by tyhle tři tahy backtracking vyzkoušel až jako poslední pokus), a druhak je to podvod, protože ten hlavolam za nás musel vyřešit kdysi někdo jiný.

Začneme (stejně jako v předchozím případě) tak, že si vymyslíme dolní odhad na složitost. Ohodnotíme tak zadání, které jsme dostali, a vypadne nám například, že zaručeně nejde vyřešit na méně než dvacet tahů. (Byli bychom radši za horní odhad – totiž právě záruku, že řešení je dlouhé nanejvýš osmdesát tahů. To bývá v praxi ale mnohem těžší vymyslet.) Pokud backtracking nenajde žádné řešení dlouhé dvacet tahů, povolíme mu řetěz třeba na dvacet pět tahů a pustíme ho znova.

A* (Dijkstrův algoritmus s dolním odhadem)

V případě tohohle hlavolamu si asi brzo všimneme, že na každé řešení se jde dostat mnohokrát. Strom řešení je ve skutečnosti spíš takové spletité bludiště. Určitě bychom si tedy pomohli, kdybychom se na stejné místo nevraceli dvakrát. Jak už víme z dřívějška, na hledání cesty v bludišti je skvělý Dijkstrův algoritmus, potažmo A*, pokud dovedeme vymyslet dolní odhad (vzdálenost vzdušnou čarou, řekněme).

Tahle kapitola je ale jen povzdech nad zjištěním, že naše bludiště je v tomhle případě moc složité. Počítač má dost výkonu, aby ho celé postupně prošel (a dokonce se na každé místo mnohokrát vrátil), ale zdaleka nemá dost paměti, aby si všechna navštívená místa pamatoval.

Dijkstrův algoritmus v tomhle případě použít nejde. Musíme se smířit s tím, že velkou část výpočtu stráví počítač opakováním pokusů z dřívějška, které si holt nezvládáme pamatovat.

Třídy složitosti

Je zajímavé se podívat na všechni možné počítačové úlohy zdálky a utřídit si je podle toho, jak jsou těžké. Už dřív jsme si zavedli odhady na asymptotickou složitost jako O(n2), O(n ·log(n)) apod. Teď je zjednodušíme ještě víc: všechno, co je řešitelné v polynomiálním čase, patří do třídy P.

Třída P

Polynomiální čas obecně zahrnuje všechno, co je O(nněkolikátou), takže do třídy P patří všechny učebnicové programy, co jsme měli dřív: hledání cesty v bludišti, hledání nejmenší kostry, hledání přesmyček ve slovníku.

Programy na téhle stránce běží v čase O(nn), což není polynom; v mocnině by muselo být nějaké neměnné číslo. My ale netřídíme programy, ale úlohy. To, že jsme našli blbý program na řešení problému obchodního cestujícího, ještě neznamená, že někdo jiný nepřijde na jiný program, který by běžel v polynomiálním čase.

(Tahle otázka zaslouží rozvést. Na světě jsou velmi chytré programy na řešení problému obchodního cestujícího, například Concorde. Jsou chytré a mnohem rychlejší než ten náš, pořád se ale zdaleka nevejdou do polynomiálního času.)

Třída NP

Některé počítačové úlohy jsou hodně ošklivé nebo i neřešitelné, a těmi se teď nechceme zabývat. Rozšíříme si obzor jenom trochu, a to na úlohy, kterým jde v polynomiálním čase zkontrolovat řešení.

Teoreticky zavedené je to zhruba tak, že si program řešení jen tak natipuje – když je líný počítat, hodí si mincí. Program má hrozné štěstí, takže když řešení existuje, objeví ho na první pokus. Může se ale stát, že řešení neexistuje – program proto nakonec musí udělat zkoušku toho, co natipoval, protože jinak by vracel nesmysly. Pokud tohle všechno stihne v polynomiálním čase, tak patří do třídy NP.

Od oka to vypadá, že třída NP obsahuje těžší problémy než třída P. Ve skutečnosti to tak taky bývá; například problém obchodního cestujícího patří do třídy NP a je těžké ho vyřešit. Zajímavé ale je, že vlastně nikdo nemá důkaz, že problémy NP jsou nějak zvlášť těžké. Na ten důkaz je vypsaná vysoká odměna a spousty matematiků si s ním lámou hlavu, ale nikomu se zatím nepovedlo ho lousknout. Možná se ho ještě dožijeme, anebo naopak někdo ukáže, že to není pravda a že všechny problémy třídy NP jsou řešitelné polynomiálně.

NP-úplné problémy

Abychom měli aspoň trochu pevné půdy pod nohama, uděláme krok stranou. Vymyslíme si několik úloh, které prokazatelně patří do třídy NP a které zároveň jsou dost těžké, aby s jejich pomocí šel vyřešit i jakýkoliv jiný problém složitosti NP.

Je to spousta těžké matematiky a formalismu, tak tuhle oblast jen přehledově načrtneme. Začneme od problému splnitelnosti (SAT):

Splnitelnost (SAT)

Program dostane zadaný logickou rovnici ve specifickém tvaru a má za úkol určit, jestli má řešení, nebo ne. Ta rovnice smí vypadat asi takhle:

(a || !b || c) && (!c || d || a || !f) && ... = true
Logické spojky tady mají význam jako v Javascriptu nebo podobných jazycích. Proměnné a, b atd. můžou mít buďto hodnotu true, nebo false. Levá strana rovnice je vlastně seznam podmínek, které musejí platit zároveň, a každá z těch podmínek je vlastně seznam proměnných, které ji můžou zachránit. Pravá strana rovnice je vždycky true.

Dá to kus dřiny, ale každý program z třídy NP jde do takovéhle rovnice zakódovat. Co víc, to samotné zakódování trvá polynomiálně dlouho – takže kdybychom dovedli v polynomiálním čase vyřešit tu logickou rovnici, vyřešíme i původní problém. To samotné kódování je dost zdlouhavé a otravné (Cookova-Levinova věta), tak se s ním nebudeme namáhat.

Hamiltonská cesta (HP)

Obchodní cestující chce najít co nejkratší cestu na mapě. Hamiltonská cesta je obdobná otázka, jestli vůbec jde mapu projít celou tak, abychom se na žádné místo nevraceli. Načrtneme si, proč je tenhle problém stejně těžký jako SAT.

Postup je následující: napíšeme program, který řeší problém hamiltonské cesty, a podle chuti občas zavolá funkci SAT(rovnice). Předpokládáme prostě, že SAT už někdo vyřešil za nás, takže stačí vymyslet správnou logickou rovnici. Tenhle program poběží v polynomiálním čase, takže kdyby šlo řešit SAT polynomiálně, půjde tak i hledat hamiltonskou cestu.

Převod SAT → HP

Cesta po mapě n měst bude dlouhá n, takže si pro popis cesty zavedeme n×n proměnných, kde každá bude znamenat, které město je kolikáté v pořadí. Každý řádek je jeden krok cesty, města jsou ve sloupcích. V každém sloupci tabulky musí být některá proměnná zapnutá, protože každým městem musíme projít. V každém řádku tabulky musí být některá proměnná zapnutá, aby v cestě nebyly díry. Přidáme tedy do rovnice 2n podmínek: za i-tý krok přidáme podmínku (pi,1 || pi,2 || ... || pi,n) a za j-té město přidáme podmínku (p1,j || p2,j || ... || pn,j).

Potřebujeme ale taky zajistit, že každým městem projdeme jenom jednou. To jde říct taky tak, že ve stejném městě nebudeme ve dvou různých časech. Pro každé město a každé dva časy tedy přidáme podmínku, která zakazuje, abychom ty možnosti označili obě. V případě j-tého města to bude vypadat nějak takhle: (!p1,j || !p2,j) && (!p1,j || !p3,j) && (!p2,j || !p3,j) &&... && (!pn-1,j || !pn,j). Obdobnou sadou podmínek zajistíme, že nejsme zároveň ve dvou různých městech.

Zbývá cestu donutit, aby si nevymýšlela hrany. Když jsme v čase i v j-tém městě, tak v čase i+1 musíme být v některém městě, kam z j vede hrana. A naopak, v čase i-1 jsme museli přijít z některého města, kam z j vede hrana. Tohle zajistí spousta podmínek ve tvaru (!pi,j || pi+1,a || pi+1,b || pi+1,c) – pokud by například z města i vedly hrany do měst a, b, c. Číst se to dá takhle: „buďto jsme tam nebyli, anebo jsme se odtamtud dostali.“ Čas 1 a čas n pochopitelně mají jenom půlku těch podmínek.

Všechny podmínky poskládáme do logické rovnice, jak jsme si ji zavedli nahoře, a jednou zavoláme SAT. Stačí rovnou vrátit jeho výsledek.

Převod HP → SAT

Obrácený postup je, že vyrobíme mapu, skrz kterou vede cesta jedině v případě, že zadaná logická rovnice má řešení. Za každou proměnnou přidáme takovýhle graf: Budeme mu říkat pantograf, protože tak vypadá. Můžeme ho podle potřeby udělat jakkoliv dlouhý.

Všimněte si, že když první sloupec v pantografu projdete shora dolů, všechny ostatní budete muset projít taky tak. Procházení shora dolů znamená, že proměnná bude true, procházení odspoda znamená false.

Teď potřebujeme vyjádřit podmínky, jak jsou zapsané v logické rovnici. Za každou přidáme do grafu další vrchol, a napojíme ho na pantografy proměnných, které se v něm vyskytují. Když je proměnná v té podmínce napsaná jen tak, napojíme ten vrchol souběžně s některou hranou pantografu, co vede doprava nahoru. Když je proměnná s vykřičníkem, napojíme ten vrchol souběžně s hranou doprava dolů. Podmínka je splněná, pokud ji aspoň jednou projdeme. Projít ji můžeme jenom z pantografu jejích proměnných, a jenom když pantograf procházíme tím správným směrem.

Pantografy všech proměnných prostě spojíme za sebe. Do žádného vrcholu pantografu nesmí vést víc než čtyři hrany; když je to potřeba, vyrobíme si delší pantograf.

Řádný důkaz by zase vyžadoval pečlivý rozbor, co všechno se může stát, ale to snad není potřeba. Tak nějak vidíme, že bude potřeba začít nalevo, projít postupně všechny pantografy a navštívit všechny podmínkové vrcholy, až skončíme úplně napravo. Tím způsobem najdeme řešení původní rovnice. A naopak, když máme řešení rovnice, dovedeme do grafu namalovat hamiltonskou cestu.