Edge keresés

A számítástechnikában a peremkeresés egy gráfkereső algoritmus , amely megtalálja a legolcsóbb utat egy adott kezdő csomóponttól egyetlen célcsomópontig .

Lényegében az élkeresés a középút az A* keresési algoritmus és az A* iteratív mélyítési változat ( IDA* [1] ) között.

Ha g ( x ) az első csomóponttól az aktuálisig tartó keresési útvonal költsége, és h ( x ) a költségheurisztika az aktuális csomóponttól a célig, akkor ƒ ( x ) = g ( x ) + h ( x ) a célokhoz vezető út tényleges költsége. Tekintsünk egy IDA-t* , amely rekurzív balról jobbra irányú mélységi keresést hajt végre a gyökércsomópontból, és leállítja a rekurziót, amint a célpont megtalálható, vagy a csomópontok elérik a maximális ƒ értéküket . Ha a cél nem található az ƒ első iterációjánál , akkor az iteráció növekszik, és az algoritmus újra keres. Azaz ismétlődik iterációkban.

Az IDA* -nak három fő hátránya van. Először is, az IDA* megismétli azokat az állapotokat, amikor több (néha az optimálistól eltérő) útvonal van a célcsomóponthoz – ezt gyakran a meglátogatott állapotok gyorsítótárának karbantartásával oldják meg. Az így módosított IDA* -ra memóriabővített IDA-nak* ( ME-IDA* [2] ) hivatkozunk, mert némi memóriát használ. Ezenkívül az IDA* újra és újra megismétli az összes korábbi keresést, ami a tárolás nélküli működéshez szükséges. Ha az előző iteráció levélcsomópontjait megtartjuk és a következő kiindulópontjaként használjuk, az IDA* hatékonysága nagymértékben javul (különben az utolsó iterációban mindig a fa minden csomópontját meg kellene látogatnia).

Az Edge Search ezeket a fejlesztéseket az IDA* -ban úgy valósítja meg , hogy többé-kevésbé két listából álló adatszerkezetet használ a keresési fa határain vagy szélén áthaladó iterációhoz. Az egyik „most” lista az aktuális iterációt, a másik „később” lista pedig a legközelebbi következő iterációt tárolja. Így a keresési fa "most" gyökércsomópontja a gyökér, a "később" pedig üres. Az algoritmus ezután két dolog egyikét teszi: Ha ƒ ( fej ) nagyobb, mint a küszöbérték, eltávolítja a fejet a "most" -ból , és hozzáadja a "később" végéhez , azaz elmenti a fejet a következő iterációhoz. Ellenkező esetben, ha ƒ ( fej ) kisebb vagy egyenlő, mint a küszöb, kibontja és eldobja a fejet , figyelembe veszi a leszármazottait, és hozzáadja őket a "most" elejéhez . Az iteráció végén a küszöbérték növekszik, a „később” lista „most” listává válik , és kiürül.

Fontos különbség az élkeresés és az A* között, hogy a listák tartalmát éles keresésben nem kell rendezni – ez jelentős nyereség az A* -hoz képest , ami gyakran költséges sorrend fenntartását teszi szükségessé a nyílt listában. Az élkeresésnek azonban az A*-tól eltérően ugyanazokat a csomópontokat kell ismételten meglátogatnia, de minden ilyen látogatás költsége állandó az A* -beli lista logaritmikus rendezési idejéhez képest a legrosszabb esetben.

Pszeudokód

Mindkét lista egyetlen duplán linkelt listában való megvalósítása, ahol az aktuális csomópontot megelőző csomópontok a "későbbi" rész , minden más pedig a "most" lista . A listában a rács minden egyes csomópontjához előre lefoglalt csomópontok tömbjének használatával a lista csomópontjaihoz való hozzáférési idő konstansra csökken. Hasonlóképpen, a markerek tömbje lehetővé teszi, hogy állandó időben keressen egy csomópontot a listában. g hash táblaként tárolódik , és az utolsó token tömb tárolódik , hogy folyamatosan nézze meg , hogy a csomópontot korábban meglátogatták e , és hogy a gyorsítótár bejegyzés érvényes - e .