Ez a webes alkalmazás lehetővé teszi a különböző gráfkereső algoritmusok grafikus megjelenítését, miközben a kiválasztott 8 feladványt megoldja.
Kezdés
Az alkalmazás bal oldalán a Vezérlőpult látható. A Vezérlőpult segítségével az alkalmazás következő szempontjait állíthatja be:
- A kezdeti állapot és a célállapot
- Melyik keresési algoritmust használja
- Melyik heurisztikus függvényt használja, ha informált keresési algoritmust használ
- És hogy egylépéses vagy burst módot használjon
Az alábbiakban mindegyik lehetőséget részletesebben ismertetjük.
Kezdeti és célállapotok
A kezdeti vagy célállapotok beállításához vagy az “Állapot szerkesztése” gombra, vagy az állapot grafikus ábrázolására kattinthat.
A következőhöz hasonló felugró ablakot kell látnia:
A lapka módosításához egyszerűen kattintson a lecserélni kívánt lapkára, majd írja be az új értéket a billentyűzeten. Ezáltal a csempe kicserélődik azzal, amelyik korábban az adott értéket tartalmazta.
Keresési algoritmus
A N-Puzzle öt különböző grafikonalapú keresési algoritmust támogat. Az első három nem informált keresési algoritmus:
- Breadth-first Search
- Depth-first Search
- Iterative Deepening Search
A másik kettő informált keresési algoritmus:
- A* Keresés
- Greedy Search
Ha informált keresési algoritmust választ, akkor egy heurisztikus függvényt is ki kell választania.
Heurisztikus függvény
A N-Puzzle három különböző Heurisztikus függvényt támogat:
- Euklideszi távolság
- Manhattan távolság (város-blokk távolság)
- Tiles Out-of-place
Single-Step vagy Burst mód
A N-Puzzle kétféle módban használható. Az alapértelmezett a Single-Step mód, amely lehetővé teszi a keresés “visszatekerését”, lépésenként. Ez hasznos ahhoz, hogy jobban megértsük, hogyan működik egy keresési algoritmus.
A másik mód a Burst mód. Ha egyszer elindult, a Burst Mode addig folytatja a keresés futtatását, amíg a célállapotot meg nem találjuk. A Burst módú keresés szüneteltethető, de nem lehet “visszatekerni”.
A keresési fa
állapot ábrázolása
Mialatt a keresés aktív, a keresési fa vizuális ábrázolása látható. Ennek a keresési fának minden egyes csomópontja a lapkák egy elrendezését (vagy állapotát) képviseli, és egy négy szakaszra osztott dobozként van megrajzolva.
A következő ábrán egy Greedy keresésből vett csomópont látható:
A legnagyobb szakasz a puzzle állapota. Alatta két kisebb szakasz látható.
A rejtvényállapot alatt két szakasz található. A bal oldali szakasz a csomópont mélysége. A jobb oldali szakasz a heurisztikus pontszám. A heurisztikus pontszámot csak az informált keresési algoritmusok esetén használjuk, tehát ha Breadth-first, Depth-first vagy Iterative Deepening Search-et használunk, a heurisztikus pontszám kimarad.
Az utolsó szakasz rögzíti a csomópontok kibontásának sorrendjét. Például a gyökércsomópont mindig “#1” lesz, és a következő kibontandó csomópontot “#2”-ként fogja jelölni.
Csomópontok színei
A keresési fa “olvashatóbbá” tétele érdekében az egyes csomópontok határa az aktuális állapotuk alapján színkódolással van ellátva.
A következő ábra az A* algoritmust (az euklideszi távolság heurisztikával) mutatja egy olyan problémára alkalmazva, amely mindössze két lépéssel megoldható:
A színek a következőképpen értelmezhetők:
| Szín | Megjelölés |
|---|---|
| Kék | Ha egy csomópont szerepel a nyitott listában, akkor kékkel lesz kiemelve. |
| Piros | A keresési algoritmus minden egyes iterációja után a legközelebb kibontandó csomópont piros színnel lesz kiemelve. Ez akkor is érvényes, ha a célcsomópontot már megtaláltuk. |
| Szürke | Ha egy állapotot már feltártunk, akkor az szürke színű lesz. Például a fenti diagram 2) lépésében a kezdeti állapotot szürkére színeztük, hogy jelezzük, hogy azt már feltártuk. A 3) lépésben a kezdeti állapotot reprezentáló csomópont újra felfedezésre kerül, de nem lesz kibontva, mivel a kezdeti állapot a gyökércsomóponton keresztül lett kibontva. |
| Zöld | Ha a célállapotot megtaláltuk, az zöld színnel lesz kiemelve. |
| arany | Amikor a célállapotot képviselő csomópontot megtaláltuk, a gyökércsomóponthoz visszavezető úton lévő összes csomópont arany színnel lesz kiemelve. |
| lila | Iteratív mélyítő keresés használata esetén a maximális mélységet meghaladó feltáratlan csomópontok nem kerülnek fel a nyitott listára. Ezek a csomópontok lila színűek lesznek. |
Nyitott és zárt listák
A keresési algoritmusok futása közben két listát vezetünk. Az első a Nyitott lista – ez a már felfedezett, de még fel nem fedezett csomópontok nyilvántartására szolgál.
A második a Zárt lista – ez a már felfedezett csomópontok nyilvántartására szolgál, illetve azon csomópontok nyilvántartására, amelyeket nem fedezünk fel, mert olyan állapotokat képviselnek, amelyeket más csomópontokon keresztül már felfedeztünk.
Mikor a keresés aktív, a Nyitott és Zárt listában lévő csomópontok száma látható a bal felső sarokban:
Kredit
.