Úloha 2: Problém kýblů
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.
Navrhněte a implementujte heuristiku řešící zobecněný problém dvou kýblů. Heuristiku otestujte na následujících příkladech a srovnejte s prohledáváním stavového prostoru do šířky (BFS).
Pro řešení daného problému byla použita metoda s využitím prioritní fronty pro ukládání stavů. Priorita prvku je určena pomocí tohoto pravidla: Pokud se v aktuální konfiguraci vyskytuje kýbl se stejným obsahem vody na správné pozici jako v koncovém stavu, zvýší se priorita o 2. Pokud se vyskytuje správný objem ale na špatné pozici, zvýší se priorita o 1. V další iteraci se pak vybírá prvek s nejvyšší prioritou.
V následujících tabulkách jsou naměřené počty operací a zanoření do stavů pro použitou heuristiku. Šedomodrá pole popisují parametry kýblů, růžové jsou koncové stavy kýblů a žluté jsou výsledky.
Naměřené hodnoty ukazují, že použitá heuristika je jednoduchá a vcelku účinná. Hodnoty pro výpočet priority jsou definovány staticky, pro dosažení lepších výsledků by bylo výhodnější provádět dynamický výpočet v závislosti na konkrétní instanci problému. Další možností by bylo neuvažovat všechny kombinace přelívání kýblů, ale jen ty, které mohou vést k výsledku. To by si však vyžádalo vyšší inteligenci algoritmu.
Ke stažení je k dispozici zabalená celá úloha, nebo jen zdrojový kód vytvořený v programovacím jazyku C: