Inom datavetenskap är franssökning en grafsökningsalgoritm [ som hittar den lägsta kostnadsvägen från en given startnod till en enda destinationsnod .
I huvudsak är kantsökning mellanvägen mellan A*-sökalgoritmen och A* iterativ fördjupningsvariant ( IDA * [1] ).
Om g ( x ) är kostnaden för sökvägen från den första noden till den nuvarande, och h ( x ) är kostnadsheuristiken från den aktuella noden till målet, då ƒ ( x ) = g ( x ) + h ( x ) är den faktiska kostnaden för vägen till mål. Tänk på en IDA* som utför en rekursiv vänster-till-höger- djup-först-sökning från rotnoden, och stoppar rekursionen så snart målet hittas eller noderna når sitt maximala ƒ- värde . Om målet inte hittas vid första iterationen ƒ, inkrementeras sedan iterationen och algoritmen söker igen. Det vill säga, det upprepas i iterationer.
IDA* har tre stora nackdelar. För det första kommer IDA* att upprepa tillstånd när det finns flera (ibland suboptimala) vägar till målnoden - detta löses ofta genom att upprätthålla en cache med besökta tillstånd. En IDA* som modifierats på detta sätt kallas för en minnesförlängd IDA* ( ME-IDA* [2] ) eftersom den använder en del minne. Dessutom upprepar IDA* alla tidigare uppslagningar om och om igen, vilket är nödvändigt för att fungera utan lagring. Genom att behålla lövnoderna från föregående iteration och använda dem som startposition för nästa, förbättras effektiviteten av IDA* avsevärt (annars skulle den alltid behöva besöka varje nod i trädet i den senaste iterationen).
Edge search implementerar dessa förbättringar i IDA* genom att använda en datastruktur som består av mer eller mindre två listor för att iterera över gränsen eller kanten på sökträdet. En "nu" -lista lagrar den aktuella iterationen, och den andra "senare" -listan lagrar närmaste nästa iteration. Således är rotnoden för sökträdet "nu" roten och "senare" är tom. Algoritmen gör sedan en av två saker: Om ƒ ( huvud ) är större än tröskelvärdet, tar huvudet bort från "nu" och lägger till det i slutet av "senare" , dvs. sparar huvudet för nästa iteration. Annars, om ƒ ( huvud ) är mindre än eller lika med tröskeln, vecklas ut och kastar huvudet , tar hänsyn till dess avkomlingar och lägger till dem i början av "nu" . I slutet av iterationen ökas tröskeln, listan "senare" blir listan "nu" och töms.
En viktig skillnad mellan edge-searching och A* är att innehållet i listorna i edge-search inte behöver sorteras – en betydande vinst jämfört med A* , vilket kräver det ofta kostsamma underhållet av ordningen i sin öppna lista. Emellertid kommer kantsökningen att behöva besöka, till skillnad från A* , samma noder upprepade gånger, men kostnaden för varje sådant besök är konstant jämfört med den logaritmiska sorteringstiden för listan i A* i värsta fall.
Implementeringen av båda listorna i en enda dubbellänkad lista, där noderna som föregår den aktuella noden är den "senare" delen och allt annat är "nu" -listan . Genom att använda en array av förallokerade noder i listan för varje nod i rutnätet reduceras åtkomsttiden till noderna i listan till en konstant. På samma sätt låter en uppsättning markörer dig söka efter en nod i en lista i konstant tid. g lagras som en hashtabell , och den sista token-arrayen lagras för att ständigt leta upp om noden tidigare har besökts och om cache- posten är giltig .
init ( start , mål ) frans F = s cache C [ start ] = ( 0 , null ) flimit = h ( start ) hittat = falskt while ( found == false ) AND ( F inte tomt ) fmin = ∞ för nod i F , från vänster till höger ( g , förälder ) = C [ nod ] f = g + h ( nod ) om f > gräns fmin = min ( f , fmin ) Fortsätta om nod == mål funnen = sant ha sönder för barn hos barn ( nod ), från höger till vänster g_barn = g + kostnad ( nod , barn ) om C [ barn ] != null ( g_cached , parent ) = C [ child ] if g_child >= g_cached Fortsätta om barn i F ta bort barnet från F infoga underordnat i F tidigare nod C [ barn ] = ( g_barn , nod ) ta bort noden från F gräns = fmin om nått mål == sant omvänd väg ( mål )Omvänd pseudokod.
omvänd väg ( nod ) ( g , förälder ) = C [ nod ] om förälder != null omvänd_sökväg ( förälder ) skriva ut nodNär den testades i en rutnätsmiljö som är typisk för datorspel, inklusive ogenomträngliga hinder, överträffade kantsökning A * med cirka 10-40 % , beroende på användningen av brickor eller oktiler. Möjliga ytterligare förbättringar inkluderar att använda en datastruktur som är lättare att cache .
| Algoritmer för grafsökning | ||
|---|---|---|
| Oinformerade metoder | ||
| Informerade metoder | ||
| Genvägar | ||
| Minsta spännträd | ||
| Övrig | ||