Úloha 2

Autor: Petr Chytil

Problém kýblů

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.

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ě.

Poznámky k implementaci

Zvolil jsem vlastní řešení v jazyce Java a nevyužíval tak nabízené prostředí. Řešení používá objekty třídy Vertex, jimž odpovídají jednotlivé stavy stavového prostoru a objekty třídy Bucket, kterým odpovídají jednotlivé kýble. Objekty kýbl nabízí všechny základní operace specifické pro tento problém (vylij, nalij, přelij), výpočet vzdálenosti od řešení (použito při heuristice) a pár dalších šikovných metod (hash, porovnání). Stav pak obsahuje seznam kýblů, umí zjistit, zda-li je řešením, počítá sumu vzdáleností kýblů od řešení a obsahuje metody pro usnadnění porovnání dvou stavů. V souboru Main je hlavní smyčka programu a zadání jednotlivých instancí. Každá instance je v ní vyřešena dvěma způsoby – BFS a heuristikou.

Řešení pomocí BFS

Na prohledávání do šířky není mnoho k vysvětlování. Z prvního stavu (ten je specifikován v zadání) vygeneruji všechny následníky pomocí operací vylij, nalij a přelij, které aplikuji na všechny kýble, které stav obsahuje. Takto vytvořené stavy přidám do obyčejné FIFO fronty. Před přidáním ještě kontroluji, zda-li již nebyl takovýto stav dříve vygenerován (z každého nově vytvořeného stavu vytvářím hash, která jej jednoznačně popisuje v našem omezeném stavovém prostoru – tuto hash si pak ukládám do hashmapy pro rychlé vyhledávání již vytvořených stavů). Další věcí je kontrola, jestli není stav řešením našeho problému – na to mi odpoví sám pomocí příslušné metody.

Řešení heuristikou

Heuristika kopíruje řešení pomocí BFS. Jediná změna v kódu je použití prioritní fronty. Ta řadí objekty na základě jejich jednoznačného pořadí. To jsem určil přiřazením přirozeného čísla n každému stavu. Číslo n jsem nazval vzdáleností od řešení. Na úrovni stavu je tato vzdálenost sumou vzdáleností jednotlivých kýblů, v tomto stavu obsažených. Kýbl má tuto vzdálenost určenou jako absolutní hodnotu rozdílu aktuálního množství vody v kýblu a požadovaného množství vody v kýblu. Žádné stavy se z prioritní fronty nevyřazují, takže máme jistotu, že nepřicházíme o řešení.

Zdrojový kód řešení

• Zdrojový kód řešení (obsahuje i heuristiku) v jazyce Java: Main.java Vertex.java Bucket.java

Výstup programu (naměřená data)

• K nahlédnutí v souboru mereni.txt

Tabulka srovnávající BFS s heuristikou

První dva sloupce ukazují počet uzlů, které byly expandovány (closed). V dalších dvou jsou vidět počty operací, které je potřeba provést nad naší množinou kýblů, abychom se dobrali k nalezenému řešení. A konečně poslední dva sloupce srovnávají v procentech BFS a heuristiku (oba jsou počítány jako BFS/heuristika).

Závěr

Vcelku jednoduchá heuristika nám pomohla (až na jednu výjimku potvrzující pravidlo) k výraznému snížení počtu navštívených uzlů stavového prostoru. Počet operací s kyblíky byl dle očekávání větší než když jsme stavový prostor poctivě procházeli pomocí BFS.