Základní problém je definován takto: K dispozici jsou dva kýble (predem
daných obecně rozdílných objemů), vodovodní kohoutek a kanál. Na pocá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, le připustíme ulití většího počtu kýblů,
aby na pocátku rešení byla v kýblech nejaká voda, a že predepíšeme koncový
objem vody v každém kýblu.
Stručný popis použité heuristiky
Problém nelze řešit metodou hrubé síly, při použití 5 kýblů můžeme mít v bodě stavového prostoru až 30=5*(4+2) možností. Problém má však malý stavový prostor díky malým celočíselným hodnotám objemu kýblů. Z tohoto důvodu je vhodné použít přesné Hash tabulky (index odpovídá stavu). Dále použijeme uřezávání díky stavům, z nichž už se do výsledného nemůžeme dostat, například jeden stav před koncem mají 2 kýble menší hodnoty objemů oproti požadavku.
Jak je vidět, metoda prodloužení v nadějném stavu nedává vždy nejkratší výsledek, a také né vždy vede k rychlejšímu nalezení. Zato druhá metoda je použitelná a dostatečně rychlá.