Problém kýblů

Úloha z předmětu 36PAA

Martin Tůma

Zadání

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ě.

Řešení

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:

p = -\sum_{i=1}^n |x_i - k_i|

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

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.110 899223 74
1.2 8 798920 539
1.3 8 7896 8 10
1.4 3 156 4 5
2.11649350455743
2.21241669548083
2.31135750835263
2.4 5 87212 448
2.5 7 632416 587
3.1145920038 744
3.2125877226 323
3.3104090833 317
3.4 5 146112 45
3.5 7 915510 79
3.6 927773261075
celkem137356267 41023335

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í.

Závěr

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í.

Reference

[1] http://service.felk.cvut.cz/courses/36PAA/Kyble.htm

Přílohy

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.