2. Problém přelévání vody
Zadání:
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 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 |
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)
-
zdrojové texty v souboru
Řešení:
Tento problém se standardně řeší pomocí prohledávání stromu do šířky (DFS).
Bruteforce spočívá v projití celého stavového prostoru a hledání prvního nebo nejlepšího řešení, což je časově velmi náročné.
Při použití heurestiky nahradíme klasickou frontu frontou prioritní,
kde zkoumané stavy seřadíme podle určitého kriteria. Vlastní algoritmus je pak již známý DFS. V mém programu jsou implementovány dva
způsoby ohodnocení:
První ohodnocuje řešení podle počtu správně naplněných kýblů:
cena = SUMi ( actuali == cili )
Druhé ohodnocení je dáno euklidovskou vzdáleností aktuálního řešení od cílového řešení:
cena = - SQRT ( SUMi ( actuali - cili ) )
Kde minus před odmocninou je z důvodu opačného ohodnocování oproti prvnímu řešení (fronta řadím sestupně).
Odmocninu v programu při ohodnocování nepočítám, protože výsledek neovlivní.
Naměřené hodnoty:
Výsledné hodnoty jsou uvedeny pro obě použité varianty ohodnocení.
První je počet již seřazených kýblů a druhý euklidovská vzdálenost.
Při programování bylo ozkoušeno více algoritmů pro ohodnocení než uvedené dva,
žádný však na zadaných instancích nebyl viditelně rychlejší než naše první použitá metoda.
| objem |
14 |
10 |
6 |
2 |
8 |
manipulací |
uzlů |
| počátek |
0 |
0 |
1 |
0 |
0 |
"1" |
"2" |
"1" |
"2" |
| konec 1 |
12 |
6 |
4 |
1 |
8 |
13 |
20 |
121 |
143 |
| konec 2 |
14 |
4 |
5 |
0 |
4 |
11 |
21 |
90 |
613 |
| konec 3 |
12 |
6 |
6 |
2 |
4 |
10 |
8 |
24 |
10 |
| konec 4 |
0 |
2 |
1 |
2 |
8 |
4 |
4 |
6 |
6 |
| objem |
15 |
12 |
8 |
4 |
6 |
manipulací |
uzlů |
| počátek |
0 |
0 |
0 |
0 |
0 |
"1" |
"2" |
"1" |
"2" |
| konec 1 |
5 |
5 |
5 |
0 |
1 |
28 |
44 |
572 |
32001 |
| konec 2 |
12 |
1 |
3 |
4 |
5 |
33 |
33 |
285 |
29151 |
| konec 3 |
11 |
1 |
3 |
4 |
5 |
20 |
33 |
228 |
22197 |
| konec 4 |
3 |
12 |
4 |
0 |
6 |
8 |
17 |
19 |
2035 |
| konec 5 |
2 |
0 |
4 |
3 |
6 |
19 |
22 |
127 |
2381 |
| objem |
14 |
10 |
12 |
3 |
8 |
manipulací |
uzlů |
| počátek |
0 |
0 |
0 |
0 |
0 |
"1" |
"2" |
"1" |
"2" |
| konec 1 |
13 |
9 |
12 |
2 |
7 |
17 |
36 |
245 |
3884 |
| konec 2 |
1 |
5 |
5 |
3 |
4 |
26 |
55 |
414 |
1226 |
| konec 3 |
0 |
9 |
6 |
3 |
1 |
25 |
28 |
195 |
1768 |
| konec 4 |
12 |
0 |
12 |
0 |
2 |
8 |
12 |
24 |
105 |
| konec 5 |
7 |
3 |
7 |
0 |
0 |
10 |
15 |
80 |
1422 |
| konec 6 |
7 |
0 |
7 |
0 |
7 |
13 |
52 |
105 |
4303 |
Závěr:
Použití heuresitky nám nezaručuje nalezení nejlepšího řešení.
Tato nevýhoda je však kompenzována velikým zrychlením oproti procházení celého stromu.
Problém je nalézt vhodnou ohodnocovací funkci.
Ze zde uvedených dvou možných řešní je jasně lepší ohodnocování podle počtu kýblů v koncovém stavu.
Jistě existuje lepší algoritmus, tento však při své jednoduchosti podavá vynikající výsledky.
Přílohy:
zdrojový kód voda.cpp
zakompresovaná data použitá v analýze data.zip