Skip to content
Menu
CDhistory
CDhistory

N-Puzzle

Posted on november 4, 2021 by admin

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
  • Kezdeti és célállapotok
  • Keresési algoritmus
  • Heurisztikus függvény
  • Single-Step vagy Burst mód
  • A keresési fa
  • állapot ábrázolása
  • Csomópontok színei
  • Nyitott és zárt listák
  • Kredit

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

.

Vélemény, hozzászólás? Kilépés a válaszból

Az e-mail-címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük

Legutóbbi bejegyzések

  • Az Acela visszatért: New York vagy Boston 99 dollárért
  • OMIM bejegyzés – # 608363 – CHROMOSOME 22q11.2 DUPLICATION SYNDROME
  • Kate Albrecht szülei – Tudj meg többet apjáról Chris Albrechtről és anyjáról Annie Albrechtről
  • Temple Fork Outfitters
  • Burr (regény)

Archívum

  • 2022 február
  • 2022 január
  • 2021 december
  • 2021 november
  • 2021 október
  • 2021 szeptember
  • 2021 augusztus
  • 2021 július
  • 2021 június
  • 2021 május
  • 2021 április
  • DeutschDeutsch
  • NederlandsNederlands
  • SvenskaSvenska
  • DanskDansk
  • EspañolEspañol
  • FrançaisFrançais
  • PortuguêsPortuguês
  • ItalianoItaliano
  • RomânăRomână
  • PolskiPolski
  • ČeštinaČeština
  • MagyarMagyar
  • SuomiSuomi
  • 日本語日本語
©2022 CDhistory | Powered by WordPress & Superb Themes