Závěrečná zpráva 2

Úvod

Popis heuristiky

Heuristika staví na prohledávání do šířky, které je vylepšeno záměnou fronty za frontu s předbíháním vzhledem k prioritě (o tom viz dále). Aby bylo zabráněno smyčkám a neefektivnímu prohledávání již navštívených částí stavového prostoru, stavy už známé zahazujeme.

Priorita stavu ve frontě by měla odrážet jeho vzdálenost k cílovému stavu. Protože to se těžko odhaduje, rozhodl jsem se ohodnotit jednotlivé operace vzhledem k tomu, jak přibližují konečné řešení. Přitom jsem vycházel z předpokladu, že cesta k cíli vede hlavně přes získávání takových objemů, které je obtížné vytvořit. Proto je cílem mého ohodnocení podporovat takové kombinace, které vedou ke vzniku objemů, jež se dosud nevyskytly. Čísla použitá pro ohodnocení jsem stanovil čistě odhadem, pro skutečné použití by bylo zapotřebí určit je na základě experimentů.
Protože heuristika má mít nulovou hodnotu pro cílový stav, platí pro ohodnocení "čím vyšší tím horší":

- plný a prázdný kýbl: nejvíce "trestných bodu" (nejjednodušeji získatelný)
- již jednou získaný objem: hodně (zajímavé jsou hlavně nové kombinace)
- zcela nový objem: málo
- cílový objem: nula

Popis algoritmu

1. Vlož počáteční stav do fronty
2. opakuj {
2.1 Vezmi čelo fronty
2.2 Je vzatý stav konečný? Pokud ano, ohlaš úspěch a skonči.
2.3 Získej všechny potomky stavu (postupným uplatněním všech smysluplných operací)
- pokud je potomek již navštíveným stavem (tzn. je ve vertices[]), zahoď jej
- jedná-li se o nový stav, spočti jeho prioritu a vlož jej do fronty
} až dokud prioritní fronta není prázdná (pak ohlaš neúspěch);

Výsledky

1. tabulka zadání

2. tabulka zadání

3. tabulka zadání

Závěr

Heuristika pokaždé našla řešení v rozumném čase, přičemž můžeme vysledovat zdánlivou závislost mezi délkou cesty a počtem navštívených stavů, což je dáno tím, že oboje se odvíjí od složitosti žádaného cílového stavu (částečně však závisí na štěstí jak brzy na jak kvalitní řešení narazíme). Otázka je, jak moc se to které řešení blíží řešení optimálnímu co do počtu operací s kýbly. Kdyby se trochu experimentovalo s hodnotami heuristiky pro ohodnocování stavů, s největší pravděpodobností by se povedlo najít takové, pro něž by byl obvykle výsledek lepší. Co se týče počtu navštívených stavů a náročnosti na paměť, stálo by za uvážení vnést do výpočtu víc inteligence a nezkoušet kombinace všech kýblů, ale s ohledem na to, že operacemi na dvou kýblech o nesoudělných objemech lze docílit jakéhokoliv množství tekutiny v rozmezí těchto objemů, mohli bychom se omezit pouze na pár kýblů po většinu výpočtu. V tomto nenáročném případě však je mé řešení postačující.

Přílohy

• kyble.hh.html
• kyble.cc.html
• Solution a trace soubory:
  
  solution.txt.1.txt solution.txt.1.1.txt solution.txt.1.2.txt solution.txt.1.3.txt solution.txt.1.4.txt solution.txt.2.1.txt solution.txt.2.2.txt solution.txt.2.3.txt solution.txt.2.4.txt solution.txt.2.5.txt solution.txt.3.1.txt solution.txt.3.2.txt solution.txt.3.3.txt solution.txt.3.4.txt solution.txt.3.5.txt solution.txt.3.6.txt trace.txt.1.txt trace.txt.1.1.txt trace.txt.1.2.txt trace.txt.1.3.txt trace.txt.1.4.txt trace.txt.2.1.txt trace.txt.2.2.txt trace.txt.2.3.txt trace.txt.2.4.txt trace.txt.2.5.txt trace.txt.3.1.txt trace.txt.3.2.txt trace.txt.3.3.txt trace.txt.3.4.txt trace.txt.3.5.txt trace.txt.3.6.txt