Tato stránka vyžaduje podporu CSS stylů

2. domácí úloha z předmětu PAA

Řešení problému přelévání vody

Oto Válek

FEL ČVUT, letní semestr 2001/2002, cvičení St 12:45

1. Specifikace úlohy

Problém přelévání vody je řešen prohledáváním do šířky s prioritní frontou. Byly použity dvě různé heuristické funkce pro výpočet priority pro frontu a připravené instance ze zadání. Výpočet byl ukončen při prvním dosažení cílového stavu.

Algoritmus byl implementován v jazyce Perl, tedy bez připravených fragmentů zdrojového kódu v jazyce C. Byl použit Active Perl 5.005_03 pod Win NT 4.0 a procesor Intel Pentium 100MHz. Výpočetní čas jednotlivých instancí nebyl měřen, celkem však testy trvaly zhruba 14 minut.

2. Heuristické funkce

Heuristické funkce vycházejí z představy vzdálenosti ve stavovém prostoru. Podstatná zde není vzdálenost euklidovská, ale vzájemná dosažitelnost stavů. Stav (5,0,5) je tak blíže stavu (5,5,5) než například (4,4,4). Důležitější je počet kýblů, které jsou již správně naplněny. Funkce byly proto zvoleny takto:

1.funkce

Započítá 2 body za každý kýbl, který již je správně naplněn, a 1 bod za každou kýbl, který je naplněn jako jiný v cílovém stavu. Pak totiž stačí už jen přelít jeho objem.

$priority = 0;
foreach $i (0..$max) {
 foreach $j (0..$max) {
  if ($buckets[$i]==$final[$j]) {
   $priority += ($i==$j) ? 2 : 1;
  }
 }
}

2.funkce

Zjednodušená varianta, započítává jen správně naplněné kýbly a ohodnotí každý 1 bodem.

$priority = 0;
foreach $i (0..$max) {
 if ($buckets[$i]==$final[$i]) {
  $priority += 1;
 }
}

3. Naměřené výsledky

Následují výsledky naměřené pro obě heuristické funkce. Udán je počet operací vedoucí k výsledku a počet navštívených stavů, pričemž žádný stav nebyl navštíven dvakrát. Nejsou započítány ani stavy, které byly vygenerovány a do fronty uloženy, ale navštíveny nebyly. Barevně odlišeny jsou nejlepší hodnoty. Metody jsou dále porovnány podle počtu případů, které vyřešily lépe.

číslo   cesta k řešení a prošlé stavy
zadání     1.funkce         2.funkce 
-------------------------------------
1.1       13    36         13   123
1.2       13   440         11    80
1.3       15    40         10    17
1.4        4     5          4     5

2.1       38   292         28   499
2.2       45   492         33   303
2.3       23   204         20   236
2.4        8    72          8    16
2.5       16   246         19   122

3.1       17    69         17   229
3.2       32   202         26   419
3.3       17    62         25   191
3.4        5    24          8    19
3.5       10    39         10    79
3.6       13    58         11    87
-------------------------------------
nejlepší    3     8          7     6

4. Závěr

Z naměřených hodnot je patrné, že první, složitější heuristika dosahovala horších výsledků, zato však po menším počtu navštívených stavů, tedy v kratším čase. Druhá heuristika nacházela lepší výsledky delší dobu, to znamená, že se více blížila čistému hledání do šířky, které vždy nalezne nejkratší cestu.

K implementaci algoritmu bylo výhodné použít tzv. asociativního pole Perlu pro zjišťování, zda byl daný stav již navštíven. Asociativní pole je implementováno pomocí hashovacích tabulek a proto se přistup do něj blíží konstatní složitosti. Naopak pro prioritní frontu jsem použil pole s porovnáváním priorit až pri výběru z něj, tady se složitostí zhruba O(n) oproti ideálně dosažitelné O(log n). Na výsledcích udávaných v počtech navštívených stavů se však tyto rozdíly neprojeví.

5. Soubory

2kyble.zip - ZIP archiv zdrojového souboru v Perlu, zadaných a naměřených hodnot a tohoto dokumentu.

2. domácí úloha z předmětu PAA Řešení problému přelévání vody Oto Válek