A szerver PHP-ben generál egy labirintust, majd a kiválasztott algoritmusokkal (egyszerre legfeljebb 6) megoldja - nézd meg egymás mellett, mennyire eltérően járja be ugyanazt a labirintust nyolc különböző keresési stratégia.
0 / 0. lépés
A labirintus-generálás előbb egy véletlenszerű feszítőfát épít (minden cellából pontosan egy út vezet minden másikhoz), majd néhány falat ledönt: így hurkok és több lehetséges út is keletkezik, és a terep egy része "nehéz" (háromszoros költségű).
A szélességi keresés (BFS) rétegenként, a starttól egyenlő távolságra lévő cellákat járja be - súlyozatlan gráfban ez garantáltan a legrövidebb utat találja meg, de sok memóriát használ, mert egyszerre sok cellát tart nyilván.
A mélységi keresés (DFS) egy irányba megy, amíg lehet, és csak zsákutcánál lép vissza - kevesebb memóriát használ, de nem garantálja a legrövidebb utat, gyakran kanyargósabb megoldást ad.
A Dijkstra-algoritmus a BFS súlyozott változata: mindig a jelenleg legolcsóbban elérhető cellát dolgozza fel legközelebb, így a nehéz terepet (háromszoros költség) figyelembe véve is a legolcsóbb utat garantálja.
Az A* a Dijkstra egy okosabb változata: egy heurisztikával (jellemzően a célig hátralévő távolság becslésével) előre irányítja a keresést, ezért jellemzően kevesebb cellát vizsgál meg, mint a Dijkstra, miközben ugyanúgy garantálja az optimális utat.
A mohó legjobb-először keresés az A* "féloldalas" rokona: csak a célig hátralévő becslést nézi, a megtett út költségét nem. Emiatt gyakran a legkevesebb cellát járja be, de az útja nem garantáltan a legrövidebb vagy a legolcsóbb.
A kétirányú BFS a rajtból és a célból egyszerre indít egy-egy szélességi keresést. Két kis kör összterülete jóval kisebb, mint egyetlen nagy, ezért ugyanazt a legrövidebb lépésszámú utat lényegesen kevesebb cella bejárásával találja meg.
A falkövető nem épít térképet és nem emlékszik: a jobb kezét a falon tartva halad. Ez egy ember számára is kivitelezhető, de a tényleges útja gyakran sokkal hosszabb a legrövidebbnél, és hurkokat tartalmazó labirintusban csak akkor működik, ha a cél a rajttal azonos fal mentén van.
A zsákutca-kitöltés fordítva gondolkodik: nem az utat keresi, hanem a zsákutcákat tömi be, amíg csak a rajtot és a célt összekötő folyosók maradnak. Hurkoknál a kitöltés a köröket nem szünteti meg, ezért itt a megmaradt hálón még lefut egy BFS.
Ez az oldal Google Analytics-et használ a látogatottság méréséhez. Ehhez a hozzájárulásod szükséges - részletek az adatvédelmi tájékoztatóban. Adatvédelmi tájékoztató