Úloha č. 2 - problém kýblů
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.
Zadání úlohy
Navrhněte a implementujte heuristiku řešící zobecněný problém dvou kýblů. Heuristiku otestujte na následujících příkladech:
| Kýble (objem) |
14 |
10 |
6 |
2 |
8 |
| Počátek |
0 |
0 |
1 |
0 |
0 |
| Stav 1 |
12 |
6 |
4 |
1 |
8 |
| Stav 2 |
14 |
4 |
5 |
0 |
4 |
| Stav 3 |
12 |
6 |
6 |
2 |
4 |
| Stav 4 |
0 |
2 |
1 |
2 |
8 |
| Kýble (objem) |
15 |
12 |
8 |
4 |
6 |
| Počátek |
0 |
0 |
0 |
0 |
0 |
| Stav 1 |
5 |
5 |
5 |
0 |
1 |
| Stav 2 |
12 |
1 |
3 |
4 |
5 |
| Stav 3 |
11 |
1 |
3 |
4 |
5 |
| Stav 4 |
3 |
12 |
4 |
0 |
6 |
| Stav 5 |
2 |
0 |
4 |
3 |
6 |
| Kýble (objem) |
14 |
10 |
12 |
3 |
8 |
| Počátek |
0 |
0 |
0 |
0 |
0 |
| Stav 1 |
13 |
9 |
12 |
2 |
7 |
| Stav 2 |
1 |
5 |
5 |
3 |
4 |
| Stav 3 |
0 |
9 |
6 |
3 |
1 |
| Stav 4 |
12 |
0 |
12 |
0 |
2 |
| Stav 5 |
7 |
3 |
7 |
0 |
0 |
| Stav 6 |
7 |
0 |
7 |
0 |
7 |
Řešení
V rámci vytváření vhodného algoritmu pro tuto úlohu, jsem vytvořil řadu různých heuristik a náhodně generovaných zadání testoval počet prošlých uzlů, délku cesty, resp. odchylku a parametr hodnotící zvolenou heuristiku 1/(delka*pocet_proslych_uzlu). Tak mi vznikl graf s poměrným měřítkem (není důležitá hodnota a spíše poměr-porovnání):
Popis implementovaných heuristik
Prohledávání do šířky
Prohledávání do šířky prochází v průměru (existují instance, při kterých prohledávání do hloubky projde více uzlů) nejvíce uzlů, ale zaručeně nachází nejkratší cestu, resp.nejmenší počet operací, které jsou nutné provézt.
Prohledávání do hloubky
Prohledávání do hloubky by v principu měl oproti prohledávání do šířky nalézt řešení rychleji, ale obecně s velmi dlouhou cestou. Samotné prohledávání stavového prostoru je velmi závislé na pořadí vygenerovaných následujících stavů.
Suma absolutních odchylek
Tato heuristika vypočítá rozdíly mezi posuzovaným a cílovým stavem. Z nich vypočte sumu a sečte se vzdáleností od počátku.
Heuristika je velmi jednoduchá a rychlá. Přesto se vyznačuje poměrně dobrou aproximací a tak tato heuristika patří mezi nejlepší.
Eliminace + použitelnost možných změn
Tato heuristika rozdělí kýble do dvou skupin, do první dá kýble, které již mají požadovanou hodnotu. Ze zbylých určí jaké stavy mohou generovat (rozdíly maxim) a ohodnotí je podle aktuální hodnoty v kýblu. V poslední fázi pro každý kýbl hledá, kolik stojí daná operace. Při nenalezení je ohodnocena podle rozdílu od cíle.
Jedná se poměrně o složitou heuristiku, která generuje služné výsledky. Pro svou složitost výpočtu je ale značně nevhodná (především v porovnání s následující).
Správná hodnota, 1 přelití, 2. přelití
Tato heuristika je založena na myšlence, že výsledkem je suma dílčích ohodnocení kýblů. Tzn. že každému kýblu bude přiřaze ohodnocení podle toho do které skupiny patří:
- v kýbli je požadované množství
- požadované množství lze realizovat 1 přelitím z jiného kýble
- požadované množství lze realizovat 2 přelitími z jiných kýblů
- ani jedna z předchozích
Zbývající voda
Tato heuristika je nejjednoduší, velmi podobná sumě rozdílů. Zde se porovnává rozdíl vody ve všech kýblech na počátku a konci.
Oproti již zmíněné má stejnou složitost, ale mnohem horší výsledky...
Eliminace + Správná hodnota, 1 přelití, 2. přelití
Jak je již patrné, tato heuristika vznikla odvozením jiné. Rozdíl je v tom, že se nejprve provede eliminace - rozdělení do dvou skupin (kýble s vyhovujícím obsahem/ostatní) a na skupině kýblů, kde množství nevyhovuje se provede výše zmíněná heuristika.
Takto upravená heuristika má oproti původní několik rozdílných vlastností. Není zaručeno, že tato heuristika je lepší, její lepší hodnoty jsou patrné až na větším testovaném vzorku. Své výhody získává především na snížení počtu poršlých stavů, za což ale platí větší možnou odchylkou od optimálního řešení.
Výsledky
Protože jako nejlepší heuristika byla vybrána jedna, která byla modifikována a mezi nimiž jsou naprosto rozdílné charakteristiky, zapsal jsem do výsledků obě dvě, přičemž je očekáváno, že jedna bude mít kratší cesty a druhá méně prohledaných uzlů...
| úloha |
prohledávání do šířky |
Správná hodnota, 1 přelití, 2. přelití |
Eliminace + správná hodnota, 1 přelití, 2. přelití |
| počet prošlých uzlů |
počet operací |
počet prošlých uzlů |
počet operací |
počet prošlých uzlů |
počet operací |
| 1/1 |
8991 |
10 |
125 |
11 |
41 |
17 |
| 1/2 |
8015 |
8 |
77 |
9 |
56 |
14 |
| 1/3 |
7914 |
8 |
12 |
10 |
13 |
10 |
| 1/4 |
163 |
3 |
4 |
4 |
5 |
4 |
|
| 2/1 |
49349 |
16 |
13288 |
18 |
769 |
32 |
| 2/2 |
41672 |
12 |
1390 |
16 |
134 |
41 |
| 2/3 |
35752 |
11 |
257 |
14 |
54 |
14 |
| 2/4 |
871 |
5 |
15 |
6 |
27 |
8 |
| 2/5 |
6279 |
7 |
204 |
13 |
85 |
17 |
|
| 3/1 |
59199 |
14 |
876 |
14 |
66 |
17 |
| 3/2 |
58768 |
12 |
1529 |
17 |
136 |
28 |
| 3/3 |
40886 |
10 |
255 |
14 |
25 |
14 |
| 3/4 |
1504 |
5 |
24 |
9 |
14 |
10 |
| 3/5 |
9042 |
7 |
57 |
9 |
15 |
8 |
| 3/6 |
27168 |
9 |
193 |
10 |
275 |
14 |
|
| součet |
355573
| 137
| 18306
| 174
| 1715
| 248
|
Naměřené hodnoty zcela splnily očekávání. Součet jednotlivých sloupců jasně nazančuje charaktrerické vlastnosti heuristik a BFS.
Rozdíly v počtu prošlých stavů mezi prohledáváním do šířky a nějakou z heuristik je velký. Dále je vidět, že rozdíl mezi jednotlivými heuristikami není zaručen, ale vcelku se dá říci, že heuristika eliminace+1,2,3 je co se týče náročnosti na počtu prošlých stavů výhodnější.
Program
Aplikace je psaná v Javě 1.5 (JBuilder 2006). Pro spuštění bude možná nutné upravit cestu k interpretu v souboru run.bat.
stáhnout
Závěr
Na aplikaci je zřetelně vidět, jak může správně zvolená heuristika změnit, resp. zrychlit chod aplikace.
Na druhou stranu z pohledu počtu různých heuristik a procházení stavového prostoru lze konstatovat, že každá z heurstik může mít jiné výhody a tak zvolit jednoznačně nejlepší není úplně snadné.
Například heuristika součet absolutních hodnot rozdílů má také dobrou aproximaci, která se blíží k nejlepším, ale narozdíl od nich je velmi snadno implementovatelná a výpočet její hodnoty mnohem rychlejší, a tak by v určitých případech mohla být výhodnější...
