Teoretický úvod je v plném znění k nalezení zde.
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.
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 |
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.
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.
Soubor se zadáními
zadani.cpp
zadani.html
Implementace heuristiky (klíčová je metoda "getScore()" třídy "State")
kyble.cpp
kyble.html