Navrhněte a implementujte heuristiku řešící zobecněný problém dvou kýblů. Heuristiku otestujte na zadaných příkladech.
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.
Heuristika je úpravou prohledávání do šířky, používající prioritní frontu a provádějící operace s kýbly v závislosti na aktuálním objemu daného kýble.
Na počátku se provede iniciace - do fronty se vloží počáteční stav a inicializují se pomocné proměnné používané algoritmem. Poté je spuštěn prohledávací algoritmus.
V každém kroku prohledávacího algoritmu je vyjmut první prvek z fronty a prozkoumán - pro všechny kýble se provádějí následující operace v závislosti na "typu" objemu:
Před potvrzením stavu a uložením do fronty je kontrolováno, jestli jsme již nedosáhli výsledného stavu a též zda se již tento stav v množině prozkoumaných stavů nenachází - podruhé se samozřejmě neukládá.
Jak již bylo uvedeno, použitá fronta je frontou prioritní. Při
vložení se tedy počítá "cena" stavu, kdy jsou objemy v jednotlivých
kýblech hodnoceny podle typu objemu, též je uvažováno správné umístění daného
objemu. Konfigurací hodnocení objemů by možná bylo možno dosáhnout i lepších
výsledků metody, hodnoty jsou definovany ve výčtovém typu EContentPrice. Objemy jsou
děleny na tyto skupiny:
prázdný kýbl, objem některého kýble,
kombinace dvou kýblů, jiný objem
přičemž hodnocena je pouze "needed" hodnota - daný objem je výsledným
objemem některého kýble a hodnota "placed" - needed objem na správném
místě.
Vytvořil jsem dvě modifikace algoritmu podle způsobu uložení
stavu s cenou stejnou jako cena jiného stavu ve frontě již uloženého - nový stav se
ukládá buď před nebo za tyto již existující stavy.
Obecně je výhodnější spíše vkládání za, hlavně pro zmenšení počtu operací
potřebných k dosažení koncového stavu, i když velmi záleží na konkrétní
instanci problému, někdy se zvýší celkový počet prozkoumaných stavů.
Srovnání obou způsobů naleznete v následující části referátu.
Samotný program (zdrojový kód) používá připravený zdroják kyble.c, do kterého byla má heuristika přidána, a to na dvě části - samotná heuristika doprostřed (před metodu search), včetně potřebných datových struktur, a ke konci bylo přidáno několik metod pro automatické načítání dat a ukládání výsledků.
Výsledky pro jednotlivé testovací příklady jsou uvedeny v následující tabulce.
| Vkládání PŘED | Vkládání ZA | Rozdíl (Z-P) | ||||||||
| Příklad | Varianta | Stavů | Operací | Čas[ms] | Stavů | Operací | Čas[ms] | Stavů | Operací | Čas |
| 1 | 1 | 167 | 16 | 110 | 190 | 17 | 110 | 23 | 1 | 0 |
| 2 | 104 | 9 | 50 | 114 | 9 | 60 | 10 | 0 | 10 | |
| 3 | 171 | 19 | 160 | 176 | 12 | 110 | 5 | -7 | -50 | |
| 4 | 34 | 4 | 60 | 43 | 4 | 60 | 9 | 0 | 0 | |
| 2 | 1 | 1379 | 43 | 2090 | 1481 | 26 | 2080 | 102 | -17 | -10 |
| 2 | 331 | 23 | 220 | 349 | 18 | 220 | 18 | -5 | 0 | |
| 3 | 1193 | 57 | 1590 | 373 | 14 | 170 | -820 | -43 | -1420 | |
| 4 | 98 | 11 | 110 | 78 | 8 | 50 | -20 | -3 | -60 | |
| 5 | 125 | 14 | 110 | 101 | 12 | 50 | -24 | -2 | -60 | |
| 3 | 1 | 262 | 19 | 220 | 304 | 22 | 220 | 42 | 3 | 0 |
| 2 | 966 | 37 | 990 | 1178 | 21 | 1430 | 212 | -16 | 440 | |
| 3 | 270 | 21 | 220 | 132 | 11 | 110 | -138 | -10 | -110 | |
| 4 | 62 | 8 | 110 | 49 | 7 | 50 | -13 | -1 | -60 | |
| 5 | 383 | 17 | 220 | 229 | 15 | 170 | -154 | -2 | -50 | |
| 6 | 1872 | 34 | 3350 | 1278 | 11 | 1600 | -594 | -23 | -1750 | |
| Součty | 7417 | 332 | 9610 | 6075 | 207 | 6490 | -1342 | -125 | -3120 | |
Ze srovnání jsou patrny lepší výsledky vkládání nového stavu na konec úseku fronty, což je způsobeno především velkým zrychlením u dlouho trvajících instancí, kdy je rychleji přeskočeno lokálně nejlepší řešení, které však nevede k řešení celkovému.
Mnou vytvořená heuristika by měla řešit libovolnou instanci zobecněného problém kýblů, alespoň všechny testovací zadání byly úspěšně vyřešeny.
Kvalita algoritmu lze těžko posoudit, nemám totiž žádné srovnání. Výsledky by možná bylo možno zlepšit změnou některých parametrů algoritmu, zvláště ohodnocením "ceny" jednotlivých typů objemů pro ukládání do prioritní fronty.
Také jsem uvažoval o rozdělení algoritmu na "prozkoumávací" část a část "dokončovací", kde by se přímo (tedy nikoliv náhodným či úplným pruhledáváním stavů) získávaly objemy prázdné, plné a kombinace dvou kýblů. Nejsem si však jist, zda by složitost dokončovací části nebyla příliš velká, z časových důvodů jsem se k jejímu podrobnějšímu rozboru bohužel nedostal.