Rekurzív keresés az első legjobb találaton

RPPNS
algoritmusok grafikonokon való kereséshez
Valaki után elnevezve Keresés az első legjobb találat alapján
Szerző Richard E. Korf [d]
Adatstruktúra grafikon
legrosszabb idő

A Recursive Best - First Search (RBFS ) egy egyszerű rekurzív algoritmus , amely megpróbálja utánozni a szabványos első legjobb egyezés keresését, decsak lineáris  teret használ.

Általános rendelkezések

Az algoritmus egy példa megvalósítása pszeudokódban

A Recursive-Best-First-Search(problem) függvény a megoldás eredményét adja vissza vagy hibajelző hiba RBFS( probléma , Make-Node(kezdeti állapot[ probléma ]), ∞) Az RBFS (problem, node, f_limit) függvény a megoldás eredményét adja vissza vagy a hibajelző és az új f-költséghatár f_limit if Goal-Test[ probléma ](Állapot[ csomópont ]) , akkor adja vissza a csomópont utódokat ← Expand( node , problem ) ha az utódcsomópontok halmaza üres , akkor a hiba visszaadása , ∞ az utódokban lévő minden egyes s esetén tegye f[s] ← max ( g (s)+h(s) , f[ node ] ) ismétlés legjobban ← a legkisebb f-értékű csomópont az utódok halmazában, ha f[legjobb] > f_limit then return error , f[ best ] alternatív ← a másodiktól a legalacsonyabb f-értékig az utódok halmazában eredmény, f[legjobb] ← RBFS(probléma, legjobb, min{f_limit, alternatív)) ha az eredmény ≠ hiba, akkor adja vissza az eredményt

Felépítése hasonló a rekurzív mélység-első kereséshez , de ahelyett, hogy végtelenül végighaladna az aktuális útvonalon, ez az algoritmus az aktuális csomópont bármely ősétől elérhető legjobb alternatív útvonal f-értékét vezérli. Ha az aktuális csomópont túllépi a megadott határértéket, akkor a rekurzió aktuális szakasza megszakad, és a rekurzió egy alternatív útvonalon folytatódik. Az RPPN algoritmusban a rekurzió ezen szakaszának befejezése után az adott útvonalon lévő minden csomópont f-értékét a gyermekcsomópont legjobb f -értéke helyettesíti . Emiatt az RPPN algoritmus megjegyzi az elfelejtett részfából származó legjobb levélcsomópont f-értékét , és ezért egy következő időpontban el lehet dönteni, hogy ezt a részfát újra bővítsük-e [1] .

Előnyök és hátrányok

Az RPPNS algoritmus valamivel hatékonyabb, mint az IDA* , de még mindig szenved a csomópontok túl gyakran regenerálódásának hátrányától [2] . Ezek a döntési változások azért következnek be, mert minden alkalommal, amikor az aktuális legjobb útvonalat kigöngyöljük, jó eséllyel megnő az f-értéke , mivel a h függvény általában kevésbé lesz optimista, ahogy a célhoz közelebbi csomópontokat kigöngyöljük. Ha ez a helyzet bekövetkezik, különösen nagy keresési területeken, a második legjobb útvonal maga is a legjobb útvonallá válhat, ezért a keresési algoritmusnak vissza kell lépnie, hogy kövesse azt. Minden döntésmódosítás az IDA* algoritmus egy iterációjának felel meg, és előfordulhat, hogy az elfelejtett csomópontok többszöri bővítésére van szükség a legjobb útvonal reprodukálásához és az elérési út egy további csomópontra való kiterjesztéséhez.

Az A* keresési algoritmushoz hasonlóan az RPPN is egy optimális algoritmus, ha a h(n) heurisztikus függvény megengedett. Térbonyolultsága 0(bd) , de az időbonyolultságot meglehetősen nehéz jellemezni : ez egyrészt a heurisztikus függvény pontosságától, másrészt attól függ, hogy milyen gyakran változott a legjobb útvonal a csomópontok telepítése során. Mind az IDA* algoritmus, mind az RPPN algoritmus hajlamos a gráfkereséssel kapcsolatos bonyolultság potenciális exponenciális növekedésére, mivel ezek az algoritmusok nem képesek észlelni az aktuális útvonalon kívüli ismétlődő állapotok jelenlétét. Ezért ezek az algoritmusok képesek ismételten feltárni ugyanazt az állapotot.

Az IDA* és RPPNS algoritmusok hátránya, hogy túl kevés memóriát használnak. Az iterációk között az IDA* algoritmus csak egyetlen számot ment el, az aktuális f-költségkorlátot . Az RPPN algoritmus több információt tárol a memóriában, de a benne felhasznált memória mennyiségét csak 0(bd) értékkel méri : ha több memória lenne is elérhető, az RPPN algoritmus nem tudja használni.

Jegyzetek

  1. ↑ Az Alkalmazás rész nincs teljesen megírva az eredeti cikkben, ezért még nincs értelme belefoglalni ebbe a cikkbe.
  2. ↑ Itt kell lennie egy részletnek

    ábrán látható példában. Az 1., 2. és 3. ábra szerint az RPPNS algoritmus először a RimnicuVilcea csomóponton keresztül követi az utat , majd „meggondolja magát” és megpróbál átmenni a Fogarasi csomóponton , majd visszatér a korábban elutasított megoldáshoz,

    de az eredeti cikkben egy befejezetlen Alkalmazás részre hivatkozik.

Irodalom

 Grafikon keresési algoritmusok
Tájékozatlan módszerek
Tájékozott módszerek
Parancsikonok
Minimálisan átívelő fa
Egyéb