Căutare recurstivă pe primul cel mai bun meci

Algoritmi RPPNS pentru căutarea pe grafice
Numit după	Căutați după prima potrivire
Autor	Richard E. Korf [d]
Structură de date	grafic
cel mai rău moment	${\mathcal {O}}(b^{2d-1})$

Recursive Best -First Search (RBFS ) este un algoritm recursiv simplu care încearcă să imite munca unei căutări standard de prima cea mai bună potrivire, darfolosinddoar spațiu liniar .

Dispoziții generale

Un exemplu de implementare a algoritmului în pseudocod

funcția Recursive-Best-First-Search(problema) returnează rezultatul soluției sau eșec indicator de eroare RBFS( problemă , Make-Node (Initial-State[ problem ] ) , ∞) funcția RBFS (problemă, nod, f_limit) returnează rezultatul soluției sau indicatorul de eșec și noua limită f-cost f_limit dacă Goal-Test[ problem ](State[ node ]) atunci returnează succesorii nodului ← Expand( node , problem ) dacă setul de noduri succesoare este gol , atunci returnează eșecul, ∞ pentru fiecare s în succesori face f[s] ← max ( g (s)+h(s) , f[ nod ] ) repetă cel mai bine ← nodul cu cea mai mică f-valoare din setul de succesori dacă f[cel mai bun] > f_limită atunci returnează eșec , f[ cel mai bun ] alternativă ← a doua la cea mai mică valoare f din setul de succesori rezultat, f[cel mai bun] ← RBFS(problemă, cel mai bun, min{f_limit, alternativă)) dacă rezultat ≠ eșec , returnați rezultatul

Are o structură similară căutării recursive prin adâncime , dar în loc să parcurgă la infinit pe calea curentă, acest algoritm controlează valoarea f a celei mai bune căi alternative disponibile de la orice strămoș al nodului curent. Dacă nodul curent depășește limita dată, atunci etapa curentă a recursiei este încheiată și recursiunea continuă pe o cale alternativă. După terminarea acestei etape de recursivitate în algoritmul RPPN , valoarea f a fiecărui nod de-a lungul căii date este înlocuită cu cea mai bună valoare f a nodului său copil. Datorită acestui fapt, valoarea f a celui mai bun nod frunză din subarborele uitat este amintită în algoritmul RPPN și, prin urmare, la un moment următor, se poate lua o decizie dacă să se extindă din nou acest subarbore [1] .

Avantaje și dezavantaje

Algoritmul RPPNS este puțin mai eficient decât IDA* , dar suferă totuși de dezavantajul regenerării prea des a nodurilor [2] . Aceste schimbări de decizie apar deoarece de fiecare dată când cea mai bună cale curentă este derulată, există șanse mari ca valoarea sa f să crească, deoarece funcția h devine de obicei mai puțin optimistă pe măsură ce nodurile mai apropiate de țintă sunt derulate. Odată ce apare această situație, în special în spațiile mari de căutare, calea care a fost cea mai potrivită poate deveni ea însăși cea mai bună cale, așa că algoritmul de căutare trebuie să efectueze backtracking pentru a o urma. Fiecare modificare a deciziei corespunde unei iterații a algoritmului IDA* și poate necesita mai multe re-extindere a nodurilor uitate pentru a reproduce cea mai bună cale și a extinde calea către încă un nod.

Ca și algoritmul de căutare A* , RPPN este un algoritm optim dacă funcția euristică h(n) este admisibilă. Complexitatea sa spațială este 0(bd) , dar este destul de dificil de caracterizat complexitatea timpului : depinde atât de acuratețea funcției euristice, cât și de cât de des s-a schimbat calea cea mai bună pe măsură ce nodurile au fost implementate. Atât algoritmul IDA* , cât și algoritmul RPPN sunt predispuși la o potențială creștere exponențială a complexității asociate cu căutările grafice, deoarece acești algoritmi nu pot detecta prezența unor stări repetate, altele decât cele din calea curentă. Prin urmare, acești algoritmi sunt capabili să exploreze în mod repetat aceeași stare.

Algoritmii IDA* și RPPNS suferă de dezavantajul că folosesc prea puțină memorie. Între iterații, algoritmul IDA* salvează doar un singur număr, limita actuală a costului f . Algoritmul RPPN stochează mai multe informații în memorie, dar cantitatea de memorie folosită în acesta este măsurată doar cu valoarea 0(bd) : chiar dacă ar fi mai multă memorie disponibilă, algoritmul RPPN nu este capabil să o folosească.

Note

↑ Secțiunea Aplicație nu este complet scrisă în articolul original, așa că nu are sens să o includeți încă în acest articol.
↑ Ar trebui să existe un fragment aici
În exemplul prezentat în fig. 1, 2 și 3, algoritmul RPPNS urmează mai întâi calea prin nodul RimnicuVilcea , apoi „se răzgândește” și încearcă să treacă prin nodul Făgăraș , după care revine la soluția respinsă anterior,
dar se referă la o secțiune de aplicație neterminată din articolul original.

Literatură

Stuart Russell , Peter Norvig : Inteligența artificială: o abordare modernă , 2004, Prentice Hall , ISBN 3-8273-7089-2

Algoritmi de căutare grafică
Metode neinformate	Căutare bidirecțională Căutare fascicul Prima căutare a lățimii lexicografice Lățimea prima căutare Căutare după criteriul de cost Profunzime prima căutare Căutare înapoi Caută prin urcare în vârf Căutare limitată la profunzime Căutare în profunzime cu aprofundare iterativă
Metode informate	Decuparea alfa beta Ramura și metoda legată Căutați după prima potrivire A* B* D* Găsirea unui punct de tranziție IDA* Căutare recurstivă pe primul cel mai bun meci SMA*
Comenzi rapide	Algoritmul undelor Algoritmul Bellman-Ford algoritmul lui Dijkstra Algoritmul Johnson algoritmul lui Levit Algoritmul Floyd-Warshall Căutare margine
Arborele de întindere minim	algoritmul lui Boruvka algoritmul lui Prim algoritmul lui Kruskal
Alte	Algoritmul British Museum Algoritmul Edmonds Traversarea copacilor Algoritmul celui mai apropiat vecin în problema vânzătorului ambulant