PAA 2007-2008, Petr Maj (majp1)
Základní problém je definován takto: K dispozici jsou dva kýble (předem daných obecně rozdílných objemů), vodovodní kohoutek a kanál. Na počátku jsou oba kýble prázdné. Vaším úkolem je docílit toho, aby v jednom kýblu byla voda o předem stanoveném objemu, přičemž můžete pouze naplnit plný kýbl z kohoutku, vylít celý kýbl do kanálu a přelít jeden kýbl do druhého tak, aby druhý kýbl nepřetekl.
Problém lze zobecnit tím, že připustíme užití většího počtu kýblů, aby na počátku řešení byla v kýblech nějaká voda, a že předepíšeme koncový objem vody v každém kýblu.
Navrhněte a implementujte heuristiku řešící zobecněný problém dvou kýblů. Heuristiku otestujte na všech následujících příkladech a srovnejte s prohledáváním stavového prostoru do šířky (BFS). Volitelně srovnejte i s prohledáváním do hloubky (DFS).
Zvolenou heuristiku popište ve zprávě. uplne zadani ulohy
Pro heuristiku jsem se rozhodl pro algoritmus A, s heuristickou funkci odhadu vypocitanou podle nasledujiciho algoritmu: Pro kazdou nadobu funkce spocte pocet kroku ktery je nutny k tomu, aby se tato dostal do spravne hodnoty finalni nadoby. Pokud je jiz nadoba spravne naplnena je jeji hodnota 0 a nadoba se zaroven zaskrtne ze jiz byla pouzita. Pokud je spravna velikost nadoby prazdna, nebo plna, pak je pro jeji vytvoreni potreba pouze jeden krok (nadoba se ale nezaskrtne jako pouzita). Pokud ani tato moznost neprobehne, zkusi se zda je mozne vygenerovat spravny obsah nadoby ze zbyvajicich (jeste nepouzitych nadob). Pokud ano, nastavi se cena na 1, jinak na 2.
Vysledna hodnota se pak sklada z dosavadni delky cesty a z odhadovane delky cesty. Tyto hodnoty je mozne zapinat a vypinat a dostat tak 3 mozne algoritmy, jak je uvedeno ve vysledne tabulce. Prvni odpovida BFS (bereme v uvahu pouze dosavadni delku cesty), druhy odpovida algoritmu A a treti pak odpovida rychlenu prohledavani, kde se uprednostnuje jak rychle jsme schopni z daneho uzlu nalezt reseni, nikoli jak dlouho nam trvalo se do uzlu dostat. V tomto pripade program najde reseni mnohem rychleji, ale nejedna se jiz o optimalni (nejkratsi reseni).
Bohuzel tato funkce neni pripustna, protoze muze davat odhad horsi nez skutecnost (napriklad v pripade 4 nadob z nichz zadna neni optimalni ale prvni a druha dohromady daji doplnek do 3ti). Svuj algoritmus jsem vsak porovnaval s daty od Tomase Nykodyma z minuleho roku, a az na 3 pripady jsem dosahoval vyrazne lepsich (hlavne kratsich) vysledku. Ve trech pripade jsem dokonce v relativne kratkem case vypocital hodnotu ktera jeho algoritmu trvala tak dlouho ze vypocet prerusil.
Co se implementace tyce, nejprve jsem ho chtel udelat v Pythonu, kdyz jsem ho vsak dokoncil zjistil jsem ze byl velice neefektivni pri praci s prioritni frontou a vypocty na nem trvaly neunosne dlouho. Nastesti prenest myslenku do pripravenych C souboru nebylo tak tezke, i kdyz pochopeni prace C++ nebylo zrovna intuitivni.
Program je dale upraven tak ze pouziva trochu objekty a STL tridy.
zdrojovy kod heuristiky zdrokovy kod funkce search kompletni zdrojovy kod cpp kompletni zdrojovy kod h| Instance | BFS - pocet stavu | Delka optimalniho reseni | A - pocet stavu | Delka A reseni | Rychly Alg. | Delka rychleho alg. |
| 1.1 | 8991 | 10 | 3083 | 10 | 367 | 14 |
| 1.2 | 8928 | 8 | 508 | 8 | 210 | 11 |
| 1.3 | 8930 | 8 | 322 | 8 | 137 | 10 |
| 1.4 | 1086 | 3 | 47 | 3 | 36 | 3 |
| 2.1 | 3102 | 33 | ||||
| 2.2 | 1400 | 41 | ||||
| 2.3 | 6175 | 11 | 1161 | 32 | ||
| 2.4 | 3347 | 5 | 100 | 5 | 48 | 5 |
| 2.5 | 14647 | 7 | 780 | 7 | 796 | 19 |
| 3.1 | 1110 | 23 | ||||
| 3.2 | 1343 | 20 | ||||
| 3.3 | 4584 | 10 | 399 | 16 | ||
| 3.4 | 6846 | 5 | 72 | 5 | 82 | 7 |
| 3.5 | 22626 | 7 | 288 | 7 | 103 | 8 |
| 3.6 | 42737 | 9 | 2419 | 9 | 215 | 11 |
Tato uloha ackoli byla velice primitivni na naprogramovani a vymysleni byla pro me prekvapenim co se tyce vykonnosti algoritmu, specielne kdyz doslo na porovnani zminene vyse. Necekal bych ze tak mala oprava, kterou jsem zavedl vicemene z kosmetickeho hlediska, aby byla moje heuristicka funkce presnejsi tak dramaticky ovlivni vysledky A algoritmu, ktery se na testovacich datech nikdy neodchylil od optima vypocteneho BFS a i ve sve rychle verzi byl o dost presnejsi nez porovnavana verze. Zajimavy byl i speed-up reseni ktery tato heuristika mela.
Otazkou vsak je jaky algoritmus je nejlepsi v praxi. Protoze asi nejbeznejsi pripad tohoto problemu v praxi se objevil ve filmu Die Hard III kde museli Bruce Willis a Samuel L. Jackson namerit presny objem aby zastavili bombu v omezenem case. V tomto pripade mi prijde nejlepsi pustit okamzite rychlou verzi ktera nejake reseni da vzdy a kdyz se bude vedet co delat s nadobami, muze na pozadi bezet verze A ktera mozna dospeje ke kratsimu vysledku:-)