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ů.
x_i - Aktuální objem i-tého kýble vkládaného prvku.
k_i - 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.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í.

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.