This HTML5 document contains 16 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
wikipedia-huhttp://hu.wikipedia.org/wiki/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-huhttp://hu.dbpedia.org/resource/
prop-huhttp://hu.dbpedia.org/property/
n8https://github.com/pywirrarika/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n9https://web.archive.org/web/20090219220415/http:/www.cs.ualberta.ca/~games/pathfind/publications/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n11http://hu.dbpedia.org/resource/Sablon:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n13http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Peremkeresés
rdfs:label
Peremkeresés
dct:subject
n13:Gráfalgoritmusok n13:Keresőalgoritmusok
dbo:wikiPageID
1704906
dbo:wikiPageRevisionID
22644136
dbo:wikiPageExternalLink
n8:fringesearch n9:cig2005.pdf
prop-hu:wikiPageUsesTemplate
n11:Jegyzetek n11:Fordítás n11:Math
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.
prov:wasDerivedFrom
wikipedia-hu:Peremkeresés?oldid=22644136&ns=0
dbo:wikiPageLength
6526
foaf:isPrimaryTopicOf
wikipedia-hu:Peremkeresés
Subject Item
dbpedia-hu:Perem_keresés
dbo:wikiPageRedirects
dbpedia-hu:Peremkeresés
Subject Item
wikipedia-hu:Peremkeresés
foaf:primaryTopic
dbpedia-hu:Peremkeresés