Petr Malát	Úloha 1	Úloha 2	Úloha 3	Úloha 4	Úloha 5	Úloha 6	Pondělí 11:00

Řešení problému kýblů

Popis problému

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.

Zadání

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ě.

Řešení

Popis implementace

Program je napsán tak, že umožňuje výměnou hlavní datové struktury provést měření pro heuristiku (prioritní fronta), DFS (zásobník) i BFS (fronta). Volba se provede definováním DFS (pro DFS) či BFS (pro BFS) při překladu. V přídě že není definováno ani jedno z maker, použije se heuristika. Dále je možné předefinovat počet kýblů předefinováním makra KYBLU. Zdrojový kód programu, brutal-force testování parametrů heuristiky a vyhodnocovač.

Popis heuristiky

Heuristická funkce ohodnotí stav na základě toho, jak "hodně se blíží" cílovému stavu. Každá podobnost s cílovým stavem je ohodnocena a cena stavu je součet těchto jednotlivách cen. Dále se ještě znevýhodňují stavy, kterých je snadné dosáhnout.

Bere se v úvahu:

stav kýble je roven cílovému stavu
stav kýble je roven cílovému stavu jiného kýble
cílový stav kýble je roven aktuálnímu stavu jiného kýble
po přelití aktuálního kýble do jiného bude v některém končný stav a naopak
kýbl je prázdný
kýbl je plný

Problém je jen to, jak správně ohodnotit jednotlivé vlastnosti stavu. Nejdříve jsem hodnoty určil intuitivně, ale pak jsem použil systematické zkoušení všech kombinací na jednotlivé instance. Počet různých cen jsem snížil na pět a každá postupně nabývala jedné z deseti hodnot (z různých rozsahů). Bohužel jsem rozsahy nezvolil úplně optimálně, protože výsledné hodnoty ležely u jejich hranic a výpočet jsem již nemohl opakovat z časových důvodů.

Pro porovnání jsem vybral 3 různé heuristiky - první z nich se snaží o co nejkratší cestu, druhá o co nejmenší počet generovaných stavů a třetí o kombinaci obojího (minimalizuje výraz délka_cesty × délka_cesty × délka_cesty × počet_stavů)

Pozorování

#i	Prohledávání do šířky		Prohledávání do hloubky		Heuristika 1		Heuristika 2		Heuristika 3
#i	Operací	Délka	Operací	Délka	Operací	Délka	Operací	Délka	Operací	Délka
1.1	229761	11	76228	1044	3194	14	1595	25	1704	14
1.2	146426	9	56334	323	10981	13	907	17	10875	14
1.3	146959	9	1076	45	1126	14	477	16	401	15
1.4	475	4	56036	313	69	5	69	5	69	5
2.1	1322350	17	279834	9911	5380	31	3618	55	3518	28
2.2	857459	13	206898	7460	7095	40	7601	41	5335	37
2.3	591729	12	297611	10469	10375	37	7653	78	8219	30
2.4	4155	6	18289	698	1063	8	170	9	1311	9
2.5	43654	8	142668	5258	6588	22	2004	26	3265	18
3.1	1586657	15	506574	14479	4361	30	2385	35	2467	26
3.2	1490103	13	220791	7978	11761	32	3199	32	3135	31
3.3	798505	11	48290	1834	3405	19	1055	31	841	18
3.4	4857	6	14893	566	589	6	350	8	386	8
3.5	63224	8	45180	1713	630	9	430	11	320	10
3.6	390606	10	136794	5064	995	14	1102	18	1198	15

#i - číslo instance
Operací - počet operací s kýbly - generování stavů, započítává se i stav, který už byl navštíven
Délka - délka řešení = počet stavů při přechodu od výchozího stavu k cílovému pomocí vykonávání elementárních operací. Triviální řešení (výchozí stav se rovná cílovému) má délku jedna.

podrobnější tabulka