Úloha z předmětu 36PAA
Martin Tůma
Navrhněte a implementujte heuristiku řešící zobecněný problém dvou kýblů [1]. Heuristiku otestujte na všech daných příkladech a srovnejte s prohledáváním stavového prostoru do šířky (BFS). Volitelně srovnejte i s prohledáváním do hloubky (DFS). Zvolenou heuristiku popište ve zprávě.
Po mnoha experimentech byla zvolena následující heuristika: Při procházení stavového prostoru je pro nově objevené stavy použita místo standartní fronty fronta prioritní. Priorita p vkládaného prvku je pak určena jako jeho "vzdálenost" od koncového stavu:
Kde:
n - Počet kýblů.
xi - Aktuální objem i-tého kýble vkládaného prvku.
ki - Objem i-tého kýble koncového prvku (řešení).
Naměřené hodnoty udává následující tabulka a přidružené grafy. Na PC s CPU Celeron M 1.47GHz, Linux 2.6.20, gcc 4.1.2 (-O3 -march=pentium-m) trvá výpočet všech řešení pomocí BFS 1.3s, pomocí heuristiky pak 0.3s.
Instance | BFS - Kroků řešení | BFS - Navštívených stavů | Heuristika - Kroků řešení | Heuristika - Navštívených stavů |
---|---|---|---|---|
1.1 | 10 | 8992 | 23 | 74 |
1.2 | 8 | 7989 | 20 | 539 |
1.3 | 8 | 7896 | 8 | 10 |
1.4 | 3 | 156 | 4 | 5 |
2.1 | 16 | 49350 | 45 | 5743 |
2.2 | 12 | 41669 | 54 | 8083 |
2.3 | 11 | 35750 | 83 | 5263 |
2.4 | 5 | 872 | 12 | 448 |
2.5 | 7 | 6324 | 16 | 587 |
3.1 | 14 | 59200 | 38 | 744 |
3.2 | 12 | 58772 | 26 | 323 |
3.3 | 10 | 40908 | 33 | 317 |
3.4 | 5 | 1461 | 12 | 45 |
3.5 | 7 | 9155 | 10 | 79 |
3.6 | 9 | 27773 | 26 | 1075 |
celkem | 137 | 356267 | 410 | 23335 |
Tabulka 1. Naměřené hodnoty.
Graf 1. Srovnání počtu navštívených stavů.
Graf 2. Srovnání počtu kroků řešení.
Použitá heuristika výrazně (15x) zmenšuje prohledávaný stavový prostor, nicméně současně také znatelně zvyšuje počet kroků řešení (4x). Dále je třeba si uvědomit, že asymptotická složitost operací nad prioritní frontou je O(log(n)) oproti O(1) u standartní fronty, čemuž také odpovídá pouze čtyřnásobné časové zlepšení za použití heuristiky. Vzhledem k těmto faktům je výhodné použít heuristiku až u "větších" problémů, než jsou jednotlivé instance zadání.
[1]
http://service.felk.cvut.cz/courses/36PAA/Kyble.htm
1. kyble_bfs.cpp
- Program pro řešení problému pomocí BFS.
2. kyble_h1.cpp
- Program pro řešení problému pomocí heuristiky.
3. data.txt
- Datový soubor zadání pro programy výše.