Úvod - specifikace úlohy

Teoretický úvod je v plném znění k nalezení zde.

Popis použité heuristiky

Rozhodl jsem se vyzkoušet a porovnat tři různé heuristiky. Všechny tři mají společný základ - prohledávají stavový prostor do šířky a stavy k prozkoumání se ukládají do prioritní fronty. Rozdíl mezi třemi heuristikami spočívá pouze ve způsobu výpočtu priority ve frontě. Čím nižší je ohodnocení stavu, tím "lepší" je pro řešení a tím vyšší prioritu má ve frontě. Nulové ohodnocení má výsledný stav.

Popis algoritmu

Zadaná data

Kýble (objem) 14 10 6 2 8
Počátek 0 0 1 0 0
Stav 1 12 6 4 1 8
Stav 2 14 4 5 0 4
Stav 3 12 6 6 2 4
Stav 4 0 2 1 2 8

 
 
Kýble (objem) 15 12 8 4 6
Počátek 0 0 0 0 0
Stav 1 5 5 5 0 1
Stav 2 12 1 3 4 5
Stav 3 11 1 3 4 5
Stav 4 3 12 4 0 6
Stav 5 2 0 4 3 6

 
 
Kýble (objem) 14 10 12 3 8
Počátek 0 0 0 0 0
Stav 1 13 9 12 2 7
Stav 2 1 5 5 3 4
Stav 3 0 9 6 3 1
Stav 4 12 0 12 0 2
Stav 5 7 3 7 0 0
Stav 6 7 0 7 0 7

Naměřené hodnoty

heuristika 1 heuristika 2 heuristika 3
zadání stavy kroky stavy kroky stavy kroky
1_1 750 24 1 982 23 3 209 32
1_2 678 13 337 18 452 26
1_3 179 15 242 20 174 19
1_4 37 4 91 4 398 28
2_1 2 266 50 2 266 48 20 023 77
2_2 2 514 65 5 135 59 27 308 78
2_3 864 22 8 252 61 14 348 73
2_4 85 9 72 9 81 13
2_5 716 26 761 25 1 921 34
3_1 1 994 28 1 786 41 2 830 41
3_2 2 998 29 3 790 29 2 208 68
3_3 661 24 483 31 1 278 50
3_4 192 13 315 19 666 26
3_5 1 181 31 2 456 37 3 506 55
3_6 697 28 1 915 30 1 790 47
nejlepší 9x 11x 5x 8x 2x 0x

Šedivě jsou podbarveny nejlepší dosažené hodnoty pro daná vstupní data. Poslední řádek udává, v kolika případech byla daná heuristika lepší, než ostatní heuristiky použité na stejná data.

Zhodnocení

Z naměřených hodnot je vidět, že k nejlepším výsledkům ve většině případů dospěla kupodivu nejjednodušší první heuristika. Naopak znatelně nejhorší výsledky přinesla třetí heuristika. Z toho je patrné, že informace, jak moc jsou objemy kbelíků rozdílné od požadovaných, není pro určení "kvality" stavu příliš důležité. Mnohem důležitější je jestli daný kbelík už dosáhl požadovaného objemu (první dvě heuristiky). Druhá heuristika přinášela většinou stejně dobré nebo trochu lepší řešení, co do počtu nutných "kýblových" operací, než první heuristika, to ale na úkor počtu prozkoumávaných stavů.

Je zřejmé, že pro různá zadání by se daly hodnoty bodových penalizací upravovat tak, aby dávaly lepší řešení. To však záleží na konkrétních případech.

Zdrojové kódy

Soubor se zadáními
zadani.cpp
zadani.html

Implementace heuristiky (klíčová je metoda "getScore()" třídy "State")
kyble.cpp
kyble.html