Peremkeresés
A számítástechnikában a peremkeresés egy gráfbejáró útkereső algoritmus, amely megtalálja a legrövidebb utat az adott kezdeti csomóponttól egy célcsomópontig.
Lényegében a peremkeresés egy középút az A* algoritmus és az iteratívan mélyülő A* algoritmus (IDA*) között.
Ha g(x) az első csomóponttól az aktuális csomópontig tartó keresési út költsége, és h(x) az aktuális csomóponttól a célig tartó út költségének heurisztikus becslése, akkor ƒ(x) = g(x) + h(x), és h* a cél elérésének tényleges költsége. Vegyük IDA* -ot, amely egy rekurzív balról jobbra haladó első mélységi keresést hajt végre a gyökércsomóponttól, és megállítja a rekurziót, miután megtalálja a célt, vagy a csomópontok elérték a maximális ƒ értéket. Ha az ƒ küszöbértékig nem találta meg a célt, akkor megnöveljük a küszöbértéket, és újraindul a kereső algoritmus. A küszöbön iterál.
Az IDA-val szemben három fő előnye van. Az első, hogy az IDA* megismétli a kereséseket, ha nem talál megfelelő utat a célcsomóponthoz - ezt gyakran úgy oldja meg, hogy a látogatott állapotokat a gyorsítótárban tárolja. Az így megváltoztatott IDA* memóriát javított IDA*-nak (ME-IDA*) nevezzük, mivel némi tárolót igényel. Ezen túlmenően az IDA* megismétli az összes korábbi keresési műveletet az új küszöbértékkel, amely a tárolás nélküli működéshez szükséges. Az előző iteráció levélcsomóinak tárolásával és a következő kiindulási helyzetének felhasználásával az IDA* hatékonysága jelentősen javul (különben az utolsó iteráció során mindig meg kell látogatnia a fában lévő összes csomópontot).
A peremkeresés ezeket a fejlesztéseket hajtja végre az IDA*-on azzal, hogy egy olyan adatszerkezetet használ, amely valójában két lista, ahol a keresés a fa határán vagy szélén iterál. Az egyik most az aktuális iterációt, a másik pedig a következő iterációt tárolja. Tehát a keresési fa gyökércsomópontja most a gyökér lesz, később pedig üres.
Ezután az algoritmus a két művelet egyikét ƒ(head) hajtja végre: Ha ƒ(head) meghaladja az aktuális küszöböt, eltávolítja a fejet az aktuálisból, és beilleszti a következő végére; azaz menti a fejet a következő iterációhoz. Ellenkező esetben, ha ƒ(head) kisebb vagy egyenlő, mint a küszöb, a kibővített csomópont generálja gyermekeit. Az iteráció végén megnő a küszöb, a következő lista az aktuális listává válik, és később kiürül.
Fontos különbség a perem és az A* között az, hogy az A* az első legjobb keresést hajtja végre, míg az IDA* az első mélységit. Az A* kisebb keresési fákat épít, mint az IDA*, mivel előnye van a tárolás használatának (nyitott és zárt Listák), míg az IDA* olyan tárolást használ, amely csak a legrövidebb út hosszát tárolja. A peremlisták tartalmát nem feltétlenül kell tárolni, ami az A*-hoz viszonyítva jelentős nyereség, mert az A* nyitott listájában a rend gyakran költséges fenntartást igényel. Az IDA* alacsony tárhelyű megoldása azonban nincs ingyen. Az A* -gal ellentétben a peremkeresésnek a csomópontokat ismételten meg kell látogatnia, de minden ilyen látogatás költsége állandó, összehasonlítva az A* listájában való keresés legrosszabb logaritmikus idejével. Másrészt az IDA* egyszerűen megvalósítható, míg az A* gyors verziói sok erőfeszítést igényelnek a megvalósításhoz.
Pszeudokód[szerkesztés]
Mindkét lista végrehajtása egy kétszeresen összekapcsolt listában történik, ahol az aktuális csomópontot megelőző csomópontok a későbbi rész, az összes többi az aktuális listában vannak. A listában az előre kiosztott csomópontok tömbjének felhasználásával a rács minden egyes csomópontjára a lista csomópontjaihoz való hozzáférési idő állandóra csökken. Hasonlóképpen, egy markertömb lehetővé teszi a listában lévő csomópontok állandó időben történő keresését. A g tárolása hash-tábla formájában történik, mely az utolsó markertömb tárolására szolgál az állandó időtartamú kereséshez, függetlenül attól, hogy egy csomópontot korábban meglátogattak-e, és a gyorsítótár-bejegyzés érvényes.
init(start, goal)
fringe F = s
cache C[start] = (0, null)
flimit = h(start)
found = false
while (found == false) AND (F not empty)
fmin = ∞
for node in F, from left to right
(g, parent) = C[node]
f = g + h(node)
if f > flimit
fmin = min(f, fmin)
continue
if node == goal
found = true
break
for child in children(node), from right to left
g_child = g + cost(node, child)
if C[child] != null
(g_cached, parent) = C[child]
if g_child >= g_cached
continue
if child in F
remove child from F
insert child in F past node
C[child] = (g_child, node)
remove node from F
flimit = fmin
if reachedgoal == true
reverse_path(goal)
Fordított pszeudokód
reverse_path(node)
(g, parent) = C[node]
if parent != null
reverse_path(parent)
print node
Kísérletek[szerkesztés]
Ha a peremkeresést számítógépes játékokra jellemző, átjárhatatlan akadályokkal rendelkező, rácsalapú környezetben tesztelték, a peremkeresés 10–40%-kal haladta meg az A* algoritmus hatékonyságát, a lapok vagy az oktílok használatától függően. A lehetséges további fejlesztések között szerepel egy olyan adatszerkezet használata, amely könnyebben hozzáférhetővé teszi a gyorsítótárakat.
Jegyzetek[szerkesztés]
Irodalom[szerkesztés]
- Björnsson, Yngvi; Enzenberger, Markus; Holte, Robert C.; Schaeffer, Johnathan. Béren kívüli keresés: A *-verés a Pathfindingen a Game Mapsen. A 2005. évi IEEE számítógépes intelligencia és játékok szimpóziumának folyóiratai (CIG05). Essex, Colchester, Essex, Egyesült Királyság; 4 – 6 április 2005. IEEE 2005. https://web.archive.org/web/20090219220415/http://www.cs.ualberta.ca/~games/pathfind/publications/cig2005.pdf
Fordítás[szerkesztés]
Ez a szócikk részben vagy egészben a Fringe search című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.