Tato webová aplikace umožňuje zobrazit grafické znázornění řady různých algoritmů vyhledávání v grafech a zároveň řešit vybrané úlohy s 8 rébusy.
Začínáme
Na levé straně této aplikace se nachází ovládací panel. Pomocí Ovládacího panelu můžete nastavit následující aspekty aplikace:
- Počáteční stav a cílový stav
- Který vyhledávací algoritmus použít
- Kterou heuristickou funkci použít, pokud používáte informovaný vyhledávací algoritmus
- A zda použít jednokrokový nebo burst mód
Každá z těchto možností bude podrobněji popsána níže.
Počáteční a cílové stavy
Chcete-li nastavit počáteční nebo cílové stavy, můžete kliknout buď na tlačítko „Upravit stav“, nebo na grafické znázornění stavu.
Mělo by se zobrazit následující vyskakovací okno:
Chcete-li změnit dlaždici, jednoduše klikněte na dlaždici, kterou chcete nahradit, a poté zadejte novou hodnotu na klávesnici. Tím se dlaždice vymění za tu, na které se dříve nacházela daná hodnota.
Vyhledávací algoritmus
N-Puzzle podporuje pět různých vyhledávacích algoritmů založených na grafu. První tři jsou neinformované vyhledávací algoritmy:
- Vyhledávání podle šířky
- Vyhledávání podle hloubky
- Iterativní prohlubování
Další dva jsou informované vyhledávací algoritmy:
- A* Search
- Greedy Search
Pokud zvolíte informovaný vyhledávací algoritmus, budete muset zvolit také heuristickou funkci.
Heuristická funkce
N-Puzzle podporuje tři různé heuristické funkce:
- Euklidovská vzdálenost
- Manhattanská vzdálenost (vzdálenost město-blok)
- Destičky mimo místo
Jednokrokový nebo burstový režim
N-Puzzle lze používat ve dvou režimech. Výchozí je režim Single-Step, který umožňuje „přetáčet“ hledání po jednotlivých krocích. To je užitečné pro lepší pochopení fungování vyhledávacího algoritmu.
Druhým režimem je režim Burst. Po spuštění režimu Burst Mode pokračuje v prohledávání, dokud není nalezen cílový stav. Vyhledávání v režimu Burst Mode lze pozastavit, ale nelze jej „přetočit“.
Strom vyhledávání
Zobrazení stavu
Když je vyhledávání aktivní, budete moci vidět vizuální zobrazení stromu vyhledávání. Každý uzel tohoto vyhledávacího stromu představuje uspořádání dlaždic (nebo stav) a je nakreslen jako pole, které je rozděleno na 4 části.
Následující schéma ukazuje uzel převzatý z vyhledávání Greedy:
Největší část je stav hádanky. Pod ním jsou dvě menší sekce.
Pod stavem hlavolamu jsou dvě sekce. Sekce vlevo je hloubka uzlu. Sekce vpravo je heuristické skóre. Heuristické skóre se používá pouze u informovaných vyhledávacích algoritmů, takže pokud používáte Breadth-first, Depth-first nebo Iterative Deepening Search, heuristické skóre bude vynecháno.
Poslední sekce zaznamenává pořadí, ve kterém byly uzly rozšířeny. Například kořenový uzel bude vždy „#1“ a další expandovaný uzel bude označen jako „#2“.
Barvy uzlů
Pro lepší „čitelnost“ vyhledávacího stromu je okraj každého uzlu barevně odlišen podle jeho aktuálního stavu.
Následující diagram ukazuje algoritmus A* (s heuristikou euklidovské vzdálenosti) aplikovaný na problém, který lze vyřešit pouze dvěma tahy:
Barvy lze interpretovat následovně:
| Barva | Význam |
|---|---|
| Modrá | Je-li uzel v otevřeném seznamu, bude zvýrazněn modře. |
| Červená | Po každé iteraci vyhledávacího algoritmu bude uzel, který bude expandován jako další, zvýrazněn červeně. To platí i v případě, že byl cílový uzel nalezen. |
| Šedá | Pokud byl stav prozkoumán, bude šedý. Například v kroku 2) výše uvedeného diagramu byl počáteční stav podbarven šedě, což znamená, že byl prozkoumán. V kroku 3) je uzel představující počáteční stav znovu objeven, ale nebude rozšířen, protože počáteční stav byl rozšířen prostřednictvím kořenového uzlu. |
| Zelená | Pokud byl cílový stav nalezen, bude zvýrazněn zeleně. |
| Zlatá | Pokud byl nalezen uzel představující cílový stav, budou všechny uzly na cestě zpět ke kořenovému uzlu zvýrazněny zlatou barvou. |
| Fialová | Při použití iterativního prohlubujícího vyhledávání nebudou do otevřeného seznamu přidány neprozkoumané uzly, které překročí maximální hloubku. Tyto uzly budou podbarveny fialově. |
Otevřené a uzavřené seznamy
Při běhu vyhledávacích algoritmů jsou udržovány dva seznamy. Prvním je Seznam otevřených uzlů – ten slouží k evidenci uzlů, které byly objeveny, ale ještě nebyly prozkoumány.
Druhým je Seznam uzavřených uzlů – ten slouží k evidenci uzlů, které byly prozkoumány, nebo uzlů, které nebudou prozkoumány, protože představují stavy, které již byly prozkoumány prostřednictvím jiných uzlů.
Když je aktivní vyhledávání, bude v levém horním rohu viditelný počet uzlů v otevřených a uzavřených seznamech:
Kredity
.