Úloha dvou džbánů je hlavolam, v němž je cílem odměřit určité množství vody za pomoci dvou (několika) nádob různého objemu a neomezeného zdroje vody.

Vzorové zadání

Máte k dispozici dvě nádoby o objemu 3 a 5 litrů a neomezený zdroj vody. Odměřte přesně 4 litry vody.

Řešení

Sestrojme si graf, který reprezentuje tento problém. Uzly na vodorovné ose značí stav vody ve větším džbánu, uzly na svislé v menším džbánu. Vodorovné hrany představují dolévání vody do většího džbánu (případně její vylévání), svislé hrany analogicky představují dolévání vody do menšího džbánu (a její vylévání). Diagonální hrany reprezentují přelévání vody mezi džbány.

Graf neobsahuje žádné vnitřní uzly, jelikož jsme schopni určit objem odměřované vody pouze tehdy, je-li jeden alespoň jeden z džbánů zcela naplněn nebo zcela vyprázdněn.

Graf problému dvou džbánů

Takto sestrojený graf již pouze prohledáme do šířky s tím, že si pro jednotlivé uzly budeme zaznamenávat předchůdce. V okamžiku nalezení uzlu 0/4 prohledávání zastavíme a zrekonstruujeme zpětnou cestu.

Řešení problému dvou džbánů

Varianty hlavolamu

V případě obtížnějšího zadání, kdy nejsou jednotlivé operace ekvivalentní (například přesné dolévání z jedné nádoby do druhé je ohodnoceno dráž než vylévání vody), musíme cenami operací ohodnotit jednotlivé hrany. V tomto případě provedeme hledání nejkratší cesty z počátku (uzlu 0/0) do cílového uzlu 0/4 pomocí Dijkstrova, Floyd-Warshallova nebo Bellman-Fordova algoritmu.

Zadání obsahující více džbánů je totožné s původním problémem, pouze je zapotřebí konstruovat graf ve více dimenzích.