36PAA - Problém kýblů

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

Heuristika

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í

InstanceBFSHeuristika
Počet operacíNavštívené stavyPočet operacíNavštívené stavyGenerované stavy
1.11089912080732
1.287988175441724
1.387895812121
1.4315545121
2.1164934934705025496
2.2124166840955028547
2.3113574928574520263
2.45871124481975
2.576323197662762
3.114591993613674349
3.21258771243703755
3.31040907323002290
3.4514601239359
3.5791541031327
3.69277722611978178

Výpisy programu:

Graf: Délka cesty k řešení (počet manipulací s kýbly)

délka cesty k řešení

Graf: Počet stavů stavového prostoru

počet stavů

Graf: Heuristika - srovnání počtu generovaných a navštívených stavů

heuristika - počet 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ů.