Úloha 2: Problém kýblů
Jan Dohnal (dohnaj1@fel.cvut.cz)
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.
| kýble (objem) | 14 | 10 | 6 | 2 | 8 | BFS | heuristika | ||
| počátek | 0 | 0 | 1 | 0 | 0 | #operací | #stavů | #operací | #stavů |
| stav 1 | 12 | 6 | 4 | 1 | 8 | 10 | 8991 | 13 | 36 |
| stav 2 | 14 | 4 | 5 | 0 | 4 | 8 | 8322 | 13 | 439 |
| stav 3 | 12 | 6 | 6 | 2 | 4 | 8 | 7961 | 15 | 40 |
| stav 4 | 0 | 2 | 1 | 2 | 8 | 3 | 249 | 4 | 5 |
| kýble (objem) | 15 | 12 | 8 | 4 | 6 | BFS | heuristika | ||
| počátek | 0 | 0 | 0 | 0 | 0 | #operací | #stavů | #operací | #stavů |
| stav 1 | 5 | 5 | 5 | 0 | 1 | 16 | 49350 | 38 | 292 |
| stav 2 | 12 | 1 | 3 | 4 | 5 | 12 | 39982 | 45 | 492 |
| stav 3 | 11 | 1 | 3 | 4 | 5 | 11 | 32742 | 23 | 204 |
| stav 4 | 3 | 12 | 4 | 0 | 6 | 5 | 790 | 8 | 72 |
| stav 5 | 2 | 0 | 4 | 3 | 6 | 7 | 4630 | 16 | 246 |
| kýble (objem) | 14 | 10 | 12 | 3 | 8 | BFS | heuristika | ||
| počátek | 0 | 0 | 0 | 0 | 0 | #operací | #stavů | #operací | #stavů |
| stav 1 | 13 | 9 | 12 | 2 | 7 | 14 | 59199 | 17 | 69 |
| stav 2 | 1 | 5 | 5 | 3 | 4 | 12 | 58703 | 32 | 202 |
| stav 3 | 0 | 9 | 6 | 3 | 1 | 10 | 43650 | 17 | 62 |
| stav 4 | 12 | 0 | 12 | 0 | 2 | 5 | 998 | 5 | 24 |
| stav 5 | 7 | 3 | 7 | 0 | 0 | 7 | 7339 | 10 | 39 |
| stav 6 | 7 | 0 | 7 | 0 | 7 | 9 | 27401 | 13 | 58 |
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: