1) Zadání : K dispozici je 5 kýblů naplněných do počátečních stavů, předem daných obecně rozdílných objemů, vodovodní kohoutek a kanál. Vaším úkolem je docílit toho, aby v kýblech byla voda o předem stanoveném objemu, přičemž můžete pouze naplnit kýbl z kohoutku do plného stavu, vylít celý kýbl do kanálu a přelít kýbl do jiného tak, aby druhý kýbl nepřetekl.
|
Kýble (objem) |
14 |
10 |
6 |
2 |
8 |
|
Počátek |
0 |
0 |
1 |
0 |
0 |
|
1 Stav 1-1 |
12 |
6 |
4 |
1 |
8 |
|
2 Stav 1-2 |
14 |
4 |
5 |
0 |
4 |
|
3 Stav 1-3 |
12 |
6 |
6 |
2 |
4 |
|
4 Stav 1-4 |
0 |
2 |
1 |
2 |
8 |
|
Kýble (objem) |
15 |
12 |
8 |
4 |
6 |
|
Počátek |
0 |
0 |
0 |
0 |
0 |
|
5 Stav 2-1 |
5 |
5 |
5 |
0 |
1 |
|
6 Stav 2-2 |
12 |
1 |
3 |
4 |
5 |
|
7 Stav 2-3 |
11 |
1 |
3 |
4 |
5 |
|
8 Stav 2-4 |
3 |
12 |
4 |
0 |
6 |
|
9 Stav 2-5 |
2 |
0 |
4 |
3 |
6 |
|
Kýble (objem) |
14 |
10 |
12 |
3 |
8 |
|
Počátek |
0 |
0 |
0 |
0 |
0 |
|
10 Stav 3-1 |
13 |
9 |
12 |
2 |
7 |
|
11 Stav 3-2 |
1 |
5 |
5 |
3 |
4 |
|
12 Stav 3-3 |
0 |
9 |
6 |
3 |
1 |
|
13 Stav 3-4 |
12 |
0 |
12 |
0 |
2 |
|
14 Stav 3-5 |
7 |
3 |
7 |
0 |
0 |
|
15 Stav 3-6 |
7 |
0 |
7 |
0 |
7 |
2) Vypracování : Pro řešení zadaného problému jsem jako vhodný programovací jazyk zvolil Borland C++ Builder 5. Zdrojový program i spustitelný soubor jsou přiloženy.
3) Rozbor řešení :
Jako heuristickou metodu jsem použil hledání do šířky - prioritní frontu, do které vkládám všechny možné ohodnocené stavy z vybraného stavu, které generuji pro všechny kýble pomocí funkcí: vylít kýbl, naplnit kýbl, přelít kýbl do ostatních a vždy kontroluji, zda-li generovaný stav již ve frontě není (nekontroluji, ale zda-li tam již nebyl) a zda-li jsem již nedospěl k výsledku. Ohodnocování uzlů jsem rozdělil dle následujících kritérií:
· vylití plného kýble
· vylití částečně naplněného kýble
· naplnění prázdného kýble
· naplnění částečně naplněného kýble
· přelití se zbytkem, plného kýble do prázdného kýble
· přelití se zbytkem, částečně naplněného kýble do prázdného kýble
· přelití se zbytkem, plného kýble do částečně naplněného kýble
· přelití se zbytkem, částečně naplněného kýble do částečně naplněného kýble
· přelití beze zbytku, plného kýble do prázdného kýble
· přelití beze zbytku, částečně naplněného kýble do prázdného kýble
· přelití beze zbytku, plného kýble do částečně naplněného kýble
· přelití beze zbytku, částečně naplněného kýble do částečně naplněného kýble
Vygenerovaný stav pak uložím do prioritní fronty. Prioritní fronta zvýhodňuje při vkládání stavu o stejném ohodnocení později vkládaný stav.
V programu jsem využil připraveného kódu, který jsem upravil a doplnil funkcemi potřebnými pro prioritní frontu a prohledávání do šířky. Program postupně řeší všechny zadání a navíc generuje soubor reseni.txt (viz. Naměřené hodnoty).
4) Naměřené hodnoty :
|
ZADANI |
START |
KONEC |
Čas |
MA_BYT |
JSOU |
Správně |
OPERACI |
STAVU |
|
|
1 |
1-1 |
17:50:41 |
17:51:05 |
0:00:24 |
12_6_4_1_8_ |
12_6_4_1_8_ |
ANO |
16 |
5134 |
|
2 |
1-2 |
17:51:07 |
17:51:11 |
0:00:04 |
14_4_5_0_4_ |
14_4_5_0_4_ |
ANO |
15 |
2095 |
|
3 |
1-3 |
17:51:12 |
17:51:31 |
0:00:19 |
12_6_6_2_4_ |
12_6_6_2_4_ |
ANO |
20 |
4855 |
|
4 |
1-4 |
17:51:33 |
17:51:34 |
0:00:01 |
0_2_1_2_8_ |
0_2_1_2_8_ |
ANO |
5 |
495 |
|
5 |
2-1 |
17:51:34 |
19:25:40 |
1:34:06 |
5_5_5_0_1_ |
5_5_5_0_1_ |
ANO |
66 |
45284 |
|
6 |
2-2 |
19:26:20 |
20:14:27 |
0:48:07 |
12_1_3_4_5_ |
12_1_3_4_5_ |
ANO |
73 |
33317 |
|
7 |
2-3 |
20:14:42 |
20:21:24 |
0:06:42 |
11_1_3_4_5_ |
11_1_3_4_5_ |
ANO |
49 |
19957 |
|
8 |
2-4 |
20:21:32 |
20:21:33 |
0:00:01 |
3_12_4_0_6_ |
3_12_4_0_6_ |
ANO |
7 |
296 |
|
9 |
2-5 |
20:21:33 |
20:29:10 |
0:07:37 |
2_0_4_3_6_ |
2_0_4_3_6_ |
ANO |
50 |
13083 |
|
10 |
3-1 |
20:29:22 |
21:30:24 |
1:01:02 |
13_9_12_2_7_ |
13_9_12_2_7_ |
ANO |
68 |
40722 |
|
11 |
3-2 |
21:30:43 |
22:40:34 |
1:09:51 |
1_5_5_3_4_ |
1_5_5_3_4_ |
ANO |
26 |
55356 |
|
12 |
3-3 |
22:40:59 |
22:46:41 |
0:05:42 |
0_9_6_3_1_ |
0_9_6_3_1_ |
ANO |
47 |
19855 |
|
13 |
3-4 |
22:46:50 |
22:56:12 |
0:09:22 |
12_0_12_0_2_ |
12_0_12_0_2_ |
ANO |
71 |
24525 |
|
14 |
3-5 |
22:56:24 |
23:15:55 |
0:19:31 |
7_3_7_0_0_ |
7_3_7_0_0_ |
ANO |
75 |
34179 |
|
15 |
3-6 |
23:16:10 |
0:20:00 |
1:03:50 |
7_0_7_0_7_ |
7_0_7_0_7_ |
ANO |
38 |
54099 |
|
celkem |
|
|
6:26:39 |
|
|
|
626 |
353252 |
|
Poslední sloupec uvádí celkový počet stavů, při nalezení správného řešení. Předposlední sloupec pak počet operací, které jsou popsány v souborech solutionXX.txt, nutných pro dosažení řešení.
5) Závěr :
Z naměřených výsledků je jasně patrné, že navržená heuristika vždy dokázala problém vyřešit, což obecně neplatí. Pro lepší, výsledky by bylo třeba si pohrát s jednotlivými ohodnoceními. Pro každé zadání by ovšem mohlo být optimální nastavení jiné a tak jsem se spokojil pouze s hrubým praktickým odhadem (pro 1. stav), že nejvíce se má ohodnotit naplnění, pak přelévání a nejméně vylévání kýblů.
Kyble.cpp – zdrojový soubor
Kyble.exe – spustitelný soubor
solutionXX.txt – soubory s řešením jednotlivých zadání