Search
sem01-bfs
bfs.cpp
sem01-iddfs
iddfs.cpp
iddfs_weighted.cpp
Diskrétní dynamický systém je jednoznačně určený svým počátečním stavem, množinou možných akcí a přechodovou funkcí, která pro daný stav a danou akci určí stav následující. Takovým systémem je například následující bludiště.
V tomto případě je počátečním stavem pozice, na které v bludišti začínáme (např. (0,0)) a množinou možných akcí pak { Up, Down, Left, Right } značící pohyb v horizontálním nebo vertikálním směru. Přechodová funkce nám říká, do jakých pozic se můžeme posunout v případě, že směr není zahrazený stěnou. Pokud je zahrazený, zůstaneme na místě.
Stavový prostor pro daný diskrétní dynamický systém je pak množina všech konfigurací, kterých může systém nabývat. Graf stavového prostoru nám na základě přechodové funkce určuje, jakým způsobem se můžeme pomocí vykonávání akcí pohybovat mezi jednotlivými konfiguracemi. Na následujícím obrázku můžete vidět graf stavového prostoru pro naše bludiště.
Vaším úkolem bude naimplementovat paralelní verze dvou základních algoritmů pro prohledávání stavových prostorů (tedy potenciálně nekonečných grafů).
Ve Vašem řešení samozřejmě můžete kombinovat prvky obou přístupů, respektive přijít s vlastní strategií prohledávání stavového prostoru. Například můžete prvky prohledávání do šířky používat v rámci ID-DFS (samozřejmě v omezené míře kvůli paměťové náročnosti prohledávání do šířky) a naopak.
Pro Vaše testování máte k dispozici 4 domény:
RODS
TOWERS
DISCS
get_identifier()
DISCS*TOWERS*ceil(log2(RODS)) ⇐ 64
TOWERS == 1
NUM_VARS
NUM_CLAUSES
MAX_CLAUSE_SIZE
NUM_VARS ⇐ 40
UNIFORM=false
SIZE
SOLUTION_DEPTH
SIZE=3
SIZE=4
WIDTH
HEIGHT
log2(WIDTH*HEIGHT) ⇐ 64
Zda je stav řešením (a tedy jedním z cílů) můžete zjistit voláním funkce is_goal().
is_goal()
Prohledávání do šířky implementujte do poskytnutého souboru bfs.cpp. Paměťově efektivní prohledávání (které budeme spouštět na velkých problémech, na kterých prohledávání do šířky selže kvůli paměťové náročnosti!) implementujte do souboru iddfs.cpp. Pokud chcete ID-DFS pro úlohy s proměnlivou cenou hran implementovat oddeleně, použijte soubor iddfs_weighted.cpp. Každá z prohledávacích metod vrací ukazatel (typu std::shared_ptr<const state>) na cílový stav, který byl dosažen pomocí optimální cesty. Na začátku prohledávání dostanete na vstupu pouze ukazatel na počáteční stav (typu std::shared_ptr<const state>). Následující stavy můžete získat voláním metody next_states() na daném stavu. Pro více informací si pročtěte komentáře v souboru state.h. Pokud optimálních řešení existuje více, vracejte stav s minimálním identifikátorem (viz metoda state::get_identifier()).
std::shared_ptr<const state>
next_states()
state.h
state::get_identifier()
Za úlohu můžete získat maximálně 12 bodů v závislosti na rychlosti vašeho řešení. Body se Vám budou nasčítávat podle následujících podúloh.