| dbo:abstract
|
- 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. (hu)
- 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. (hu)
|
