Tomáš Kubeš - kubest1
FEL-ČVUT PAA (Problémy a algoritmy) LS 2005
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 daných příkladech.
Za předpokladu, že objemy kýblů jsou celočíselné nebo alespoň obecně soudělné, je stavový prostor úlohy složen z bodů, které reprezentují všechny možné stavy kýblů (tj. množství vody v nich).
V dodávané návrhové šabloně již existují prostředky, které umožní pohodlně implementovat řešení s procházením stavového prostoru prohledáváním do šířky. Tento algoritmus je ale v obecné formě pro tento případ nepoužitelný - je třeba projít velmi mnoho stavů. Lze sice nalézt optimální řešení, avšak čas na to potřebný je neúměrný.
Značného urychlení lze dosáhnout, pokud se bude pokaždé následný testovaný stav vybírat podle nějakého chytrého kritéria, které zajistí, že přednost při testování dostanou perspektivní stavy. Toto lze implementovat teoreticky jednoduše - klasickou frontu proto nahradíme frontou prioritní, jednotlivé stavy ohodnotíme a podle tohoto ohodnocení do fronty vkládáme. Stavy s vhodnějším ohodnocením se ukládají do fronty blíže k začátku - jsou tedy zpracovány dříve než ostatní.
K řešení této úlohy jsem využil nabídnuté šablony pro práci se stavovým prostorem a pro operace s kýbly (viz. http://service.felk.cvut.cz/courses/36PAA/Kyble.htm)
Frontu (tj. chování funkcí enqueue a dequeue) jsem pozměnil na binární vyhledávací strom, kdy vlevo jsou řazeny uzly s vyšším ohodnocením. Ohodnocení je požadovaná heuristická funkce. Navrhl jsem jí jako počítání vzdálenosti v eukleidovském prostoru o n rozměrech, kde n je počet kýblů - tj.: sum(0, n, sqrt(hladina(n)aktuální-hladina(n)cílová)2). Její asymptotická výpočetní náročnost je tedy O(n), pro rozumně velká zadání, jí můžeme chápat jako konstantní. Dequeue vybírá ten nejpravější uzel. Díky užití binárního stromu je složitost těchto funkcí přibližně logaritmická vzhledem k počtu stavů ve frontě (kterých může být ovšem obecně poměrně mnoho, řádově stejně jako stavů celkem). Strom sice není vyvažován, ovšem obecně lze asymptotickou složitost operací popsat jako O(log(N)), kde N je celkový počet stavů úlohy.
Další rozšíření oproti původnímu spočívá v zavedení bitové mapy pro kontrolu, zda již nebyl stav ve stavovém prostoru navštíven. Tato metoda je dramaticky rychlejší než-li procházení celého stavového prostoru funkcí compare() - (O(1) vs. O(N2)).
| Kýble (objem) | 14 | 10 | 6 | 2 | 8 | počet kroků k řešení | počet prohledaných stavů |
| Počátek | 0 | 0 | 1 | 0 | 0 | ||
| Stav 1 | 12 | 6 | 4 | 1 | 8 | 21 | 1082 |
| Stav 2 | 14 | 4 | 5 | 0 | 4 | 23 | 1954 |
| Stav 3 | 12 | 6 | 6 | 2 | 4 | 8 | 88 |
| Stav 4 | 0 | 2 | 1 | 2 | 8 | 4 | 54 |
| Kýble (objem) | 15 | 12 | 8 | 4 | 6 | počet kroků k řešení | počet prohledaných stavů |
| Počátek | 0 | 0 | 0 | 0 | 0 | ||
| Stav 1 | 5 | 5 | 5 | 0 | 1 | 68 | 43817 |
| Stav 2 | 12 | 1 | 3 | 4 | 5 | 40 | 43295 |
| Stav 3 | 11 | 1 | 3 | 4 | 5 | 42 | 34903 |
| Stav 4 | 3 | 12 | 4 | 0 | 6 | 13 | 4125 |
| Stav 5 | 2 | 0 | 4 | 3 | 6 | 22 | 4400 |
| Kýble (objem) | 14 | 10 | 12 | 3 | 8 | počet kroků k řešení | počet prohledaných stavů |
| Počátek | 0 | 0 | 0 | 0 | 0 | ||
| Stav 1 | 13 | 9 | 12 | 2 | 7 | 41 | 10666 |
| Stav 2 | 1 | 5 | 5 | 3 | 4 | 55 | 7811 |
| Stav 3 | 0 | 9 | 6 | 3 | 1 | 28 | 3057 |
| Stav 4 | 12 | 0 | 12 | 0 | 2 | 13 | 872 |
| Stav 5 | 7 | 3 | 7 | 0 | 0 | 18 | 4170 |
| Stav 6 | 7 | 0 | 7 | 0 | 7 | 56 | 19623 |
Užití heuristiky přineslo v mnoha případech skutečně velmi značné zrychlení výpočtu oproti užití původního procházení do šířky, nicméně se ukázalo, že pro některá zadání bylo stále potřeba projít poměrně velké množství stavů, řádově se blížící velikosti stavového prostoru. Pro jiné úlohy byl počet navštívených stavů naopak skutečně minimální.
Bohužel ukázalo se, že některá zadání této heuristice příliš nevyhovují. V případech, kdy bylo nutné projít přibližně 40 000 stavů lze očekávat, že velká část zrychlení běhu programu připadá spíše na bitvou mapu navštívených stavů, nežli na heuristiku. Tento nedostatek je námětem na zamyšlení se nad dalšími možnostmi řešení.