Zadání
Navrhněte a implementujte heuristiku řešící zobecněný problém dvou kýblů. Heuristiku otestujte na všech následujících příkladech a srovnejte s prohledáváním stavového prostoru do šířky (BFS). Volitelně srovnejte i s prohledáváním do hloubky (DFS). Zvolenou heuristiku popište ve zprávě.
Definice problému
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.
Implementace
Úlohu jsem implementoval v Jazyce C# jako konzolovou aplikaci. Vstupní data jsou součástí kódu a výsledky jsou vypisovány na standardní výstup. Základem řešení je mírně modifikovaný BFS algoritmus. Místo fronty CLOSE jsem použil mapu do které ukládám veškeré stavy. Klíčem do mapy je Hash, který je roven obsahu všech kýblů (pro 1 kýbl stačí 6b, máme 5 kýblů, tj. stačí 30b, tj. int). Výhodou tohoto řešení (inspirace od Augiho) je jeho rychlost a bezkonfliktnost. V případě heuristiky jsem nahradil frontu OPEN prioritní frontou. Priorita je rovna součtu absolutních hodnot rozdílu současného a koncového stavu přes všechny kýble. Tj. čím menší číslo, tím větší přednost.
BFS
- BFS.cs - V metodě compute je implementován vlastní výpočet. While cykl dokud není fronta OPEN prázdná vybírá z ní stavy a expanduj je (plní, vylévá a přelévá kýble). Každý nově objevený stav je vložen do mapy STATES. Nově expandovaný stav je vložen do OPEN pouze pokud není nalezeno řešení, nebo expandovaný stav může zlepšit řešení.
- Input.cs - Obsahuje pouze zadání (tj.: kapacity, počáteční a koncový stav), použita jako parametr konstruktoru třídy BFS.
- Program.cs - Zavolá BFS pro každou instanci a vypíše výsledek.
- State.cs - Reprezentuje stav stavového prostoru, uchovává aktuální stav kýblů, ukazatel na předešlý stav a délku cesty.
Heuristika
- Heuristic.cs - Základ je stejný jako u BFS. Navíc je pro každý nový stav vypočtena Priorita (minimální cesta vedoucí k cíli - součet absolutních hodnot rozdílu současného a koncového stavu) a stav je vložen do prioritní fronty.
- Input.cs - viz. Input z BFS.
- Program.cs - viz Program z BFS.
- PQ.cs - Prioritní fronta. Implementována jako pole Front, kde rozměr pole je dán maximální hodnotou priority. Je to jednoduché řešení a v tomto případě postačující.
- State.cs - viz. State z BFS + přidána metoda Priority().
Naměřené hodnoty a výsledky
Měřil jsem na NTB s procesorem Centino 1.4GHz, nastavení max Performance při napájení z adaptéru. Použitý OS: Windows XP SP2 s .net Framework 2.
Tabulka výsledků měření
| Instance | BFS | Heuristika | |||
|---|---|---|---|---|---|
| Počet operací | Navštívené stavy | Počet operací | Navštívené stavy | Generované stavy | |
| 1.1 | 10 | 8991 | 20 | 80 | 732 |
| 1.2 | 8 | 7988 | 17 | 544 | 1724 |
| 1.3 | 8 | 7895 | 8 | 12 | 121 |
| 1.4 | 3 | 155 | 4 | 5 | 121 |
| 2.1 | 16 | 49349 | 34 | 7050 | 25496 |
| 2.2 | 12 | 41668 | 40 | 9550 | 28547 |
| 2.3 | 11 | 35749 | 28 | 5745 | 20263 |
| 2.4 | 5 | 871 | 12 | 448 | 1975 |
| 2.5 | 7 | 6323 | 19 | 766 | 2762 |
| 3.1 | 14 | 59199 | 36 | 1367 | 4349 |
| 3.2 | 12 | 58771 | 24 | 370 | 3755 |
| 3.3 | 10 | 40907 | 32 | 300 | 2290 |
| 3.4 | 5 | 1460 | 12 | 39 | 359 |
| 3.5 | 7 | 9154 | 10 | 31 | 327 |
| 3.6 | 9 | 27772 | 26 | 1197 | 8178 |
Výpisy programu:
Graf: Délka cesty k řešení (počet manipulací s kýbly)
Graf: Počet stavů stavového prostoru
Graf: Heuristika - srovnání počtu generovaných a navštívených stavů
Závěr
Zadané instance jsou přijatelně rychle řešitelné pomocí BFS s ořezáváním neperspektivních stavů. Heuristika založená na minimalizaci vzdálenosti k výsledku dává velice dobré výsledky. V průměru bylo vygenerováno 102,5x méně stavů, přičemž cesta se průměrně prodloužila 2,3x. Maximálně se cesta prodloužila 3,3x a v nejlepším případě bylo vygenerováno 650x méně stavů.