Ugrás a tartalomhoz

Peremkeresés

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

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]

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.

További információk

[szerkesztés]
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Peremkeresés&oldid=26003680”