Search
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
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()
Stáhněte si balíček sem_01.zip (v případě, že Váš procesor nepodporuje použité vektorové instrukce, nahraďte soubor domains/hanoi.h tímto souborem). Prohledávání do šířky implementujte do 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. 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.
domains/hanoi.h
bfs.cpp
iddfs.cpp
std::shared_ptr<const state>
next_states()
state.h
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.
Zazipované soubory bfs.cpp a iddfs.cpp odevzdávejte do systému BRUTE do 1.5.2018 23:59 CET.
Pokud byste chtěli algoritmus pro nalezení nejlevnější cesty ve váženém grafu odevzdat zvlášť, naimplementujte tento algoritmus v tomto souboru a odevzdejte ho spolu s bfs.cpp a iddfs.cpp.