Inden for datalogi er frynsesøgning en grafsøgealgoritme , der finder den billigste vej fra en given startknude til en enkelt destinationsknude .
I bund og grund er kantsøgning mellemvejen mellem A*-søgealgoritmen og den A* iterative uddybningsvariant ( IDA * [1] ).
Hvis g ( x ) er prisen for søgestien fra den første knude til den nuværende, og h ( x ) er omkostningsheuristikken fra den aktuelle knude til målet, så er ƒ ( x ) = g ( x ) + h ( x ) er de faktiske omkostninger ved vejen til mål. Overvej en IDA* , der udfører en rekursiv venstre-til-højre dybde-først-søgning fra rodknuden, og stopper rekursion, så snart målet er fundet, eller knuderne når deres maksimale ƒ -værdi . Hvis målet ikke findes ved den første iteration af ƒ , øges iterationen derefter, og algoritmen søger igen. Det vil sige, at det gentages i gentagelser.
IDA* har tre store ulemper. For det første vil IDA* gentage tilstande, når der er flere (nogle gange suboptimale) stier til målknuden - dette løses ofte ved at opretholde en cache af besøgte tilstande. En IDA* , der er modificeret på denne måde , omtales som en memory-extended IDA* ( ME-IDA* [2] ), fordi den bruger noget hukommelse. Derudover gentager IDA* alle tidligere opslag igen og igen, hvilket er nødvendigt for at fungere uden lagring. Ved at beholde bladknuderne fra den forrige iteration og bruge dem som startpositionen for den næste, forbedres effektiviteten af IDA* betydeligt (ellers ville den altid skulle besøge hver knude i træet i den sidste iteration).
Edge search implementerer disse forbedringer i IDA* ved at bruge en datastruktur bestående af mere eller mindre to lister til at iterere over grænsen eller kanten af søgetræet. En "nu" -liste gemmer den aktuelle iteration, og den anden "senere" -liste gemmer den nærmeste næste iteration. Således er rodnoden i søgetræet "nu" roden, og "senere" er tom. Algoritmen gør så en af to ting: Hvis ƒ ( hoved ) er større end tærskelværdien, fjerner hovedet fra "nu" og tilføjer det til slutningen af "senere" , dvs. gemmer hovedet til næste iteration. Ellers, hvis ƒ ( hoved ) er mindre end eller lig med tærsklen, udfolder og kasserer hovedet , overvejer dets efterkommere og tilføjer dem til begyndelsen af "nu" . Ved slutningen af iterationen øges tærsklen, den "senere" liste bliver til "nu" -listen og tømmes.
En vigtig forskel mellem kantsøgning og A* er, at indholdet af listerne i kantsøgning ikke skal sorteres - en væsentlig gevinst i forhold til A* , hvilket kræver den ofte omkostningstunge vedligeholdelse af orden i dens åbne liste. Dog skal kantsøgningen, i modsætning til A* , besøge de samme noder gentagne gange, men prisen for hvert sådant besøg er konstant sammenlignet med den logaritmiske sorteringstid for listen i A* i værste fald.
Implementeringen af begge lister i en enkelt dobbelt-linket liste, hvor noderne forud for den aktuelle node er den "senere" del , og alt andet er "nu" -listen . Ved at bruge et array af præ-allokerede noder i listen for hver node i gitteret, reduceres adgangstiden til noderne på listen til en konstant. På samme måde giver en række markører dig mulighed for at søge efter en node på en liste i konstant tid. g gemmes som en hash-tabel , og det sidste token-array gemmes for konstant at slå op, om noden tidligere har været besøgt, og om cache -indgangen er gyldig .
init ( start , mål ) frynse F = s cache C [ start ] = ( 0 , null ) flimit = h ( start ) fundet = falsk while ( fundet == falsk ) OG ( F ikke tomt ) fmin = ∞ for node i F , fra venstre mod højre ( g , overordnet ) = C [ node ] f = g + h ( knudepunkt ) hvis f > grænse fmin = min ( f , fmin ) Blive ved hvis node == mål fundet = sandt pause for barn hos børn ( node ), fra højre mod venstre g_barn = g + pris ( node , underordnet ) hvis C [ barn ] != null ( g_cached , overordnet ) = C [ barn ] if g_child >= g_cached Blive ved hvis barn i F fjern barnet fra F indsæt underordnet i F forbi node C [ barn ] = ( g_barn , node ) fjern node fra F grænse = fmin hvis målet er nået == sandt omvendt vej ( mål )Omvendt pseudokode.
omvendt sti ( knudepunkt ) ( g , overordnet ) = C [ node ] hvis forælder != null omvendt_sti ( forælder ) print nodeVed test i et gittermiljø, der er typisk for computerspil, inklusive uigennemtrængelige forhindringer, overgik kantsøgning A* med ca. 10-40 % afhængigt af brugen af fliser eller oktiler. Mulige yderligere forbedringer omfatter brug af en datastruktur, der er lettere at cache .
| Algoritmer til grafsøgning | ||
|---|---|---|
| Uoplyste metoder | ||
| Informerede metoder | ||
| Genveje | ||
| Minimumspændende træ | ||
| Andet | ||