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.
Naším úkolem je navrhnout a implementovat heuristiku, která daný problém vyřeší.
Pro získání heuristické hodnotu stavu ohodnotím nezávisle každý kýbl zvlášť, přičemž kýbl, který obsahuje požadované množství, je ohodnocen nulou. Kýbl, který obsahuje jinou hodnotu, ovšem v cílovém stavu má být buď zcela prázdný nebo zcela plný, je ohodnocen nejmenším postihem (neboť se do cílového stavu může kdykoliv jedním tahem dostat). Nejvyšším postihem je ohodnocen kýbl, který je buď zcela plný nebo zcela prázdný, neboť takový stav nemá žádnou „hodnotu“. Zbytek stavů (kýbl není ani plný, ani prázdný, ani plný či prázdný být nemá) je ohodnocen poměrem aktuální hodnoty a kapacity (toto kritérium je zvoleno prakticky libovolně a na výsledek nemá prakticky vliv).
K heuristické hodnotě je pak přičten počet kroků, kterým byl stav dosažen (algoritmus A*). Relativní vliv heuristiky lze měnit pomocí konstanty, kterou je heuristická část ohodnocení vynásobena. Pro hodnoty menší nebo rovné jedné je ohodnocení přípustné, tzn. program najde vždy nejkratší řešení. Vyšší ohodnocení zase obvykle způsobí výraznější zmenšení prohledávané části stavového prostoru, ovšem nenajde vždy nejkratší postup.
Program jsem použil ve třech variantách: zcela bez heuristiky (hodnota heuristiky = 0, jde tedy o prohledávání do šířky), s přípustnou heuristikou (hodnota heuristiky = 1) a se zdůrazněnou heuristikou (hodnota heuristiky = 3). Je vidět, že přípustná heuristika skutečně vždy najde nejkratší řešení, ovšem zvýrazněná heuristika zase mnohem více ořeže prohledávaný stavový prostor.
BFS | Zdůrazněná | Přípustná | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tahů | Čas [s] | Tahů | Čas [s] | Tahů | Čas [s] | |||||||||
14/10/6/2/8 | ||||||||||||||
Stav 1 | 10 | 8992 | 0,312 | 10 | 784 | 9 % | 0,0322 | 10 | 8650 | 96 % | 0,303 | |||
Stav 2 | 8 | 8773 | 0,273 | 9 | 1797 | 20 % | 0,0661 | 8 | 5852 | 67 % | 0,189 | |||
Stav 3 | 8 | 8338 | 0,263 | 9 | 1389 | 17 % | 0,0501 | 8 | 6575 | 79 % | 0,219 | |||
Stav 4 | 3 | 71 | 0,00104 | 4 | 7 | 10 % | 0,000169 | 3 | 13 | 79 % | 0,000277 | |||
15/12/8/4/6 | ||||||||||||||
Stav 1 | 16 | 49345 | 2,97 | 17 | 42883 | 87 % | 2,80 | 16 | 49168 | 100 % | 3,29 | |||
Stav 2 | 12 | 43544 | 2,48 | 13 | 32151 | 74 % | 2,00 | 12 | 32677 | 75 % | 1,97 | |||
Stav 3 | 11 | 35432 | 1,94 | 13 | 16298 | 46 % | 0,911 | 11 | 32626 | 92 % | 1,99 | |||
Stav 4 | 5 | 783 | 0,0117 | 7 | 312 | 40 % | 0,00730 | 5 | 202 | 26 % | 0,00351 | |||
Stav 5 | 7 | 6203 | 0,181 | 7 | 1447 | 23 % | 0,0683 | 7 | 1008 | 16 % | 0,0254 | |||
14/10/12/3/8 | ||||||||||||||
Stav 1 | 14 | 59199 | 3,84 | 14 | 42019 | 71 % | 2,94 | 14 | 58936 | 100 % | 4,15 | |||
Stav 2 | 12 | 57310 | 3,60 | 14 | 42967 | 75 % | 2,93 | 12 | 52476 | 92 % | 3,59 | |||
Stav 3 | 10 | 40990 | 2,40 | 10 | 4418 | 11 % | 0,222 | 10 | 29998 | 73 % | 1,80 | |||
Stav 4 | 5 | 2153 | 0,0517 | 6 | 478 | 22 % | 0,0181 | 5 | 159 | 7 % | 0,00291 | |||
Stav 5 | 7 | 11184 | 0,444 | 7 | 80 | 1 % | 0,00256 | 7 | 2800 | 25 % | 0,0946 | |||
Stav 6 | 9 | 36507 | 2,00 | 10 | 6420 | 18 % | 0,340 | 9 | 17360 | 48 % | 0,945 |
Zvolená heuristika je relativně jednoduchá, přesto přináší poměrně zajímavé výsledky (zvláště ve zdůrazněné variantě, pokud nám nevadí nižší kvalita nalezených řešení). Je mnoho způsobů, jak heuristiku ještě vylepšit. Několik příkladů takových vylepšení: penalizovat vylévání vody, bonifikovat stavy se správným nebo téměř správným celkovým objemem vody, případně zavést do hodnocení i závislosti mezi kýbly, neboť v současné podobě jsou kýble hodnoceny na sobě navzájem nezávisle.