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
), počtem věží (na začátku obsazených kolíků, TOWERS
) a počtem kotoučů v každé věži (DISCS
). Doména je korektní (funkce get_identifier()
vrací unikátní identifikátory), pokud platí DISCS*TOWERS*ceil(log2(RODS)) ⇐ 64
.
NUM_VARS
), počtem termů ke splnění (NUM_CLAUSES
) a maximální velikostí termu (MAX_CLAUSE_SIZE
). Doména je korektní pokud NUM_VARS ⇐ 40
. V této doméně je i možnost vygenerovat zadání, kde je cena za různé zvolené proměnné různá (UNIFORM=false
) - v opačném případě mají všechny přechody cenu 1.
SIZE
xSIZE
) a počtem náhodných tahů, které jsou použity pro vygenerování iniciální konfigurace (SOLUTION_DEPTH
). Doména je korektní pro SIZE=3
a SIZE=4
.
WIDTH
xHEIGHT
). Doména je korektní, pokud log2(WIDTH*HEIGHT) ⇐ 64
. Obdobně jako u SATu je zde možnost proměnlivých cen za přechod při volbě parametru UNIFORM=false
.
Zda je stav řešením (a tedy jedním z cílů) můžete zjistit voláním funkce 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
.
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
.