Úvod

Zdrojové súbory na cvičenie si stiahnite spoločne ako archív.

Problém bludiska

Pomocou paralelného IDA* algoritmu vyriešte problém bludiska. Ľavý horný roh je štartovacou pozíciou, cieľovou je pravý dolný roh. Využite všetky možné nástroje pomoci programátora súčasnej doby. Pracujte v trojiciach. Vaše riešenie by malo byť schopné spracovať bludisko rozmerov 500×500. Plný počet bodov môžete získať iba v tom prípade, že budete rozumieť vami obhajovanej implementácii. Na riešenie tohto problému odporúčame MPI. Nebránime sa však ani CUDA frameworku. Voľba je na vás.

Generátor bludiska

Modul maze.py obsahuje implementáciu niekoľkých typov bludísk:

1. Jednoduchý labyrint, ktorý obsahuje náhodne umiestnené prekážky. V závislosti od parametra density sa určuje hustota prekážok. Nevýhodou tohto generátora je to, že veľmi často vygeneruje labyrint, kde nejestvuje cesta zo štartu do cieľa.
2. Priateľský labyrint obsahuje symetricky rozložené prekážky, ktoré veľmi veľmi mierne ovplyvňujú proces hľadania riešenia. Vždy jestvuje cesta zo štartu do cieľa.
3. Hadí labyrint vytvára jedinú cestu, ktorá sa kľukatí ako had zo štartovacej pozície do cieľovej. Podotýkame, že aj pri tomto type generátora jestvujú nastavenia (keď je počet riadkov deliteľný 4), kedy riešenie (cesta zo štartu do cieľa) nejestvuje.
4. Dokonalý labyrint. Niet čo dodať 😉

Bolo by veľmi vhodné, ak by ste počas cvičenia stihli experimentovať s rôznymi typmi labyrintov a ich nastaveniami, aby ste pochopili, ako štruktúra labyrintu ovplyvňuje efektivitu paralelného riešenia.

Heuristika

Taktiež by ste mali stihnúť experimentovať s rôznymi typmi typmi heuristiky. V pomocnom programovom kóde riešenia (ktoré nie je paralelné) sa využíva Manhattanská vzdialenosť od aktuálnej pozície do cieľa. Vašou úlohou je overiť správanie modelu pri použití Euklidovskej vzdialenosti a taktiež v situácii, keď zvýšite váhu heuristiky (napr. h(node)*1.5). Aký je dôsledok zvýšenia váhy heuristiky? To zistíte, keď na rovnakom bludisku spustíte (ovšem že viackrát!) model bez zvýšenej váhy a so zvýšenou váhou heuristiky.

Ukážkové implementácie (rekurzívna a nerekurzívna verzia)

Súbor ida_recursive.py obsahuje rekurzívnu implementáciu algoritmu IDA*. Jeho hlavnou nevýhodou je počet rekurzívnych vnorení, ktoré je štandardne v jazyku Python obmedzené na hodnotu 1000. Takže pomocou tohto riešenia môžete riešiť bludiská, kde hĺbka vnorenia nepresiahne toto obmedzenie.

Súbor ida_iterative.py je prepracovanou verziou rekurzívnej implementácie na implementáciu pomocou cyklu (a pamäťového zásobníka). Lebo ako už bolo spomenuté na prednáške a ako ste už dávno vedeli: Pre každú rekurzívnu funkciu f existuje ekvivalentná iteračná funkcia g (používajúca cykly a explicitnú pamäť/zásobník), ktorá pre rovnaké vstupné hodnoty vráti rovnaký výsledok, a naopak. Ekvivalencia platí pri predpoklade, že máme k dispozícii neobmedzenú (alebo dostatočne veľkú) pamäť, napríklad pre simuláciu zásobníka volaní.