2. úloha - problém kýblů

Tomáš Kubeš - kubest1
FEL-ČVUT PAA (Problémy a algoritmy) LS 2005
 

Specifikace úlohy

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.

Zadání

Navrhněte a implementujte heuristiku řešící zobecněný problém dvou kýblů. Heuristiku otestujte na daných příkladech.

Rozbor úlohy a řešení

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í.

Implementace řešení

Popis

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)).

Program

Řešení jednotlivých zadání:

 
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

Závěr

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í.