2. úloha

Problém kýblů

Zadání domácí úlohy

Zkušební instance

Pokyny pro vypracování

Implementační poznámky

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 všech následujících příkladech a srovnejte s prohledáváním stavového prostoru do šířky (BFS). Volitelně srovnejte i s prohledáváním do hloubky (DFS).
Zvolenou heuristiku popište ve zprávě.

Zde máte k dispozici 15 zkušebních instancí. Ve všech případech se jedná o 5 kýblů. Všechny instance jsou v "rozumném" čase řešitelné BFS.

Kýble (objem)		15	12	8	4	6
Počáteční stav		0	0	0	0	0
Koncové stavy	Instance 2.1	5	5	5	0	1
	Instance 2.2	12	1	3	4	5
	Instance 2.3	11	1	3	4	5
	Instance 2.4	3	12	4	0	6
	Instance 2.5	2	0	4	3	6

Kýble (objem)		14	10	12	3	8
Počáteční stav		0	0	0	0	0
Koncové stavy	Instance 3.1	13	9	12	2	7
	Instance 3.2	1	5	5	3	4
	Instance 3.3	0	9	6	3	1
	Instance 3.4	12	0	12	0	2
	Instance 3.5	7	3	7	0	0
	Instance 3.6	7	0	7	0	7

Zpráva bude obsahovat:

stručný popis použité heuristiky
délku cesty k jednotlivým řešením (tedy počet manipulací s kýbly)
počet navštívených bodů stavového prostoru pro jednotlivé instance (je to lepší kritérium kvality heuristiky než výpočetní čas), pro Vaší heuristiku a prohledávání do šířky. Dobrovolně i pro prohledávání do hloubky (DFS)
zdrojové texty v souboru

Kýble (objem)

Počáteční stav

Koncové stavy

Instance 1.1

Instance 1.2

Instance 1.3

Instance 1.4

Jelikož se jedná o poměrně rozsáhlý problém, máte k dispozici fragmenty zdrojového kódu v jazyce C, které implementují základní operace nad množinou kýblů a stavovým prostorem, takže Vaším úkolem vlastně je naprogramovat a začlenit Vaši heuristiku do programu. Použití této podpory není povinné.

K dispozici je Vám část zdrojového kódu programu - k stažení:

.c
.h
.arj
novější verze, kompilovatená pod Linuxem, laskavostí p. Medveckého

Podpora produkuje binární soubor obsahující Vámi prozkoumaný stavový prostor (funkce save a save_vertices viz dále). Tyto soubory neodevzdávejte na server (jsou dost velké), ale uschovejte je pro případné řešení problémů a vyhodnocení.
Funkce, do které máte napsat Vaši heuristiku, se jmenuje search.
Stavový prostor je implementován jako souvislé pole uzlů s odkazem na předchůdce (index do pole uzlů) vertices, tudíž není třeba provádět žádnou alokaci paměti.
Funkce většinou vracejí buď "logickou" hodnotu (0,1), nebo index do pole vertices.
Pro operace s kýbly máte k dispozici sadu funkcí isempty, isfull, fill, empty a pour.
Dva stavy můžete mezi sebou porovnat funkcí compare. Prozkoumávaný uzel se zapisuje do první neobsazené buňky pole stavového prostoru a případně se tam může zapsat natrvalo funkcí putvertex. Na první neobsazenou buňku pole ukazuje index ffree.
Pokud budete chtít prohledávat do šířky, máte k dispozici funkce pro operaci s frontou rozpracovaných uzlů enqueue a dequeue. Test, zda daný stav je hledaným řešením, se provádí pomocí funkce check. V případě, že jste řešení nalezli, můžete ho uložit do souboru funkcí save. Vámi prozkoumaný stavový prostor můžete uložit v textovém tvaru (dump_vertices) a v binárním tvaru (save_vertices).