Zobecněný problém dvou kýblů

1. Úkol

Navrhnětete a implementujte heuristiku řešící zobecněný problém dvou kýblů. Heuristiku otestujte na příkladech.

2. Rešení

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é. Úkolem je docílit, 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.

2.1 Hrubá síla

Metoda je založena na projití generování a procházení kombinací vylití, naplění a přelití kýblů do doby, než je nalezeno řešení. Nové stavy se řadí do fronty jak vznikají, procházení je po hladinách, bez heuristiky a je časově velmi náročné.

2.2 Heuristika

Nové stavy vzniklé operací s kýblem se vloží do prioritní fronty podle nějakého kritéria. Zvolili jsme řazení fronty podle počtu kýblů, které jsou již naplněny podle cílového stavu. Nejdříve jsou tedy vyzkoušeny stavy, které jsou nejblíže řešení.

objem 14 10 6 2 8 manipulací uzlů
počáteční stav 0 0 1 0 0
koncový stav 1 12 6 4 1 8 9 325
koncový stav 2 14 4 5 0 4 10 23
koncový stav 3 12 6 6 2 4 10 24
koncový stav 4 0 2 1 2 8 4 6

Tabuka 1. Statistiky řešení pro první várku dat

objem 15 12 8 4 6 manipulací uzlů
počáteční stav 0 0 0 0 0
koncový stav 1 5 5 5 0 1 28 572
koncový stav 2 12 1 3 4 5 33 285
koncový stav 3 11 1 3 4 5 20 228
koncový stav 4 3 12 4 0 6 8 19
koncový stav 5 2 0 4 3 6 19 127

Tabuka 2. Statistiky řešení pro druhou várku dat

objem 14 10 12 3 8 manipulací uzlů
počáteční stav 0 0 0 0 0
koncový stav 1 13 9 12 2 7 17 245
koncový stav 2 1 5 5 3 4 26 414
koncový stav 3 0 9 6 3 1 25 195
koncový stav 4 12 0 12 0 2 8 24
koncový stav 5 7 3 7 0 0 10 80
koncový stav 6 7 0 7 0 7 13 105

Tabuka 3. Statistiky řešení pro třetí várku dat

3. Závěr

Při použití uvedené heuristiky jsme vyřešili problém kýblů na různých příkladech. Použitý algoritmus řazení do fronty byl zvolen intuitivně, jistě by se dal najít jiný, lepší a matematicky podložený. Tento ale pracuje dostatečně uspokojivě. Napoprvé jsme vyzkoušeli náhodné vkládání operací do fronty, výsledky ale byly špatné v porovnání s implementovanou metodou.

Dodatek

Kompletní balíček s programem pro řešení úlohy, výsledky testů a soubory pro make.
Zdrojový kód programu pro usnadnění prohlížení.
Spustitelný soubor programu pro Linux.