Căutarea neinformată (de asemenea căutarea oarbă , metoda forței brute , ing. căutarea neinformată, căutarea oarbă, căutarea în forța brută ) este o strategie de găsire a soluțiilor în spațiul stărilor , care nu utilizează informații suplimentare despre stări, cu excepția celor prezentate în definirea sarcinii. Tot ceea ce este capabilă metoda căutării neinformate este de a dezvolta succesori și de a distinge starea țintă de cea non-țintă [1] [2] [3] .
Breadth-first search ( BFS ) este o strategie de căutare a soluției în spațiul de stare care extinde mai întâi nodul rădăcină, apoi toți succesorii nodului rădăcină, apoi extinde succesorii acelor succesori și așa mai departe. Înainte ca orice nod să fie extins la nivelul următor, toate nodurile la o anumită adâncime din arborele de căutare sunt extinse.
Algoritmul este complet. Dacă toate acțiunile au același cost, căutarea pe lățime este optimă.
Numărul total de noduri generate (complexitatea timpului) este O( b d +1 ), unde b este factorul de ramificare, d este adâncimea de căutare. Complexitatea spațiului este de asemenea O( b d +1 ) [1] .
O implementare de căutare amplă poate folosi o coadă FIFO . La început, coada conține doar nodul rădăcină. La fiecare iterație a buclei principale, nodul curr este preluat din capul cozii . Dacă nodul curr este nodul țintă, căutarea se oprește, în caz contrar nodul curr este derulat și toți succesorii săi sunt adăugați la sfârșitul cozii [4] [5] .
funcţia BFS ( v : Nod ) : Boolean ; începe coada ( v ) ; în timp ce coada nu este goală , începe curr := scoate la coadă () ; if is_goal ( curr ) atunci începe BFS := true ; ieșire ; sfârşitul ; marca ( curr ) ; pentru next in succesors ( curr ) do if nu este marcat ( next ) apoi începe coda ( next ) ; sfârşitul ; sfârşitul ; BFS := false ; sfârşitul ;
Căutarea de cost (cautare uniform-cost, UCS ) este o generalizare a algoritmului de căutare pe lățimea întâi care ia în considerare costul acțiunilor (marginile graficului de stare). Căutarea bazată pe costuri extinde nodurile în ordinea crescătoare a costului celei mai scurte căi de la nodul rădăcină. La fiecare pas al algoritmului, este implementat nodul cu cel mai mic cost g ( n ). Nodurile sunt stocate într- o coadă de prioritate [6] .
Acest algoritm este complet și optim dacă costurile etapelor sunt strict pozitive. Dacă costurile tuturor etapelor sunt egale, căutarea costurilor este identică cu căutarea pe lățimea întâi.
Procedura de căutare a costurilor poate intra într-o buclă infinită dacă se întâmplă să aibă un nod implementat care are o acțiune cu cost zero care indică din nou către aceeași stare. Este posibil să se garanteze integralitatea și optimitatea căutării, cu condiția ca costurile tuturor acțiunilor să fie strict pozitive [1] .
Căutarea bazată pe costuri este echivalentă din punct de vedere logic cu algoritmul cu cea mai scurtă cale de la Dijkstra . În special, ambii algoritmi implementează aceleași noduri în aceeași ordine. Principala diferență este legată de prezența nodurilor în coada de prioritate: în algoritmul lui Dijkstra, toate nodurile sunt adăugate la coadă în timpul inițializării, în timp ce în algoritmul de căutare bazat pe cost, nodurile sunt adăugate „on-the-fly” ( ing . .în mers , leneș ) în timpul căutării. De aici rezultă că algoritmul lui Dijkstra este aplicabil graficelor explicite, în timp ce algoritmul UCS poate fi aplicat atât graficelor explicite, cât și implicite [7] .
Căutarea în profunzime ( DFS ) este o strategie de căutare a deciziei în spațiul de stare care extinde întotdeauna cel mai adânc nod din periferia curentă a arborelui de căutare. Căutarea în profunzime analizează primul succesor al nodului curent din listă, apoi primul său succesor și așa mai departe. Nodurile extinse sunt eliminate de la periferie, așa că căutarea ulterioară „reia” de la următorul nod cel mai puțin adânc, care încă nu a fost explorat. succesori [1] .
Strategia de căutare depth-first poate fi implementată cu o stivă LIFO sau cu o funcție recursivă [8] .
funcţia DFS ( v : Nod ; adâncime : Integer ) : Boolean ; începe dacă is_goal ( v ) apoi începe DFS := adevărat ; ieșire ; sfârşitul ; pentru next in succesorii ( v ) do if DFS ( următorul , adâncimea + 1 ) atunci începe DFS := true ; ieșire ; sfârşitul ; DFS := fals ; sfârşitul ;
Căutarea limitată în adâncime ( DLS ) este o variantă a căutării în primul rând în adâncime care aplică o limită de adâncime predefinită l pentru a rezolva problema căii infinite.
Căutarea limitată la adâncime nu este completă, deoarece pentru l < d ținta nu va fi găsită și nu este optimă pentru l > d . Complexitatea sa în timp este O( b l ), iar complexitatea sa în spațiu este O( b · l ) [1] [9] .
Căutarea limitată la adâncime este utilizată în algoritmul iterativ de căutare de aprofundare.
funcţia DLS ( v : Nod ; adâncime , limită : Integer ) : Boolean ; începe dacă ( adâncime < limită ) apoi începe dacă is_goal ( v ) apoi începe DLS := adevărat ; ieșire ; sfârşitul ; pentru următorii succesori ( v ) începe dacă DLS ( următorul , adâncimea + 1 , limită ) atunci începe DLS : = true ; _ ieșire ; sfârşitul ; sfârşitul ; sfârşitul ; DLS := false ; sfârşitul ;
Căutarea depth-first cu aprofundare iterativă (iterative-deepening depth-first search, IDDFS , DFID ) este o strategie care vă permite să găsiți cea mai bună limită de adâncime pentru căutarea DLS. Acest lucru se realizează prin creșterea progresivă a limitei l până la găsirea țintei.
Căutarea iterativă de adâncire combină avantajele căutării în adâncime (complexitatea spațiului O( b · l )) și a căutării pe lățime (completitudine și optimitate pentru ponderi finite b și margini nenegative).
Deși căutarea profundă iterativă generează aceleași stări de mai multe ori, majoritatea nodurilor se află în partea de jos a arborelui de căutare, astfel încât timpul petrecut pentru re-extinderea nodurilor poate fi de obicei ignorat. Complexitatea temporală a algoritmului este O( b l ) [1] [9] [10] .
funcția IDDFS ( v : Nod ) : Întregul ; var lim : Integer ; începe lim := 0 ; în timp ce nu DLS ( v , 0 , lim ) do lim := lim + 1 ; IDDFS := lim ; sfârşitul ;
Căutarea bidirecțională pe lățime (sau adâncime) este un algoritm sofisticat de căutare pe lățime (sau adâncime), ideea căruia este că două căutări pot fi efectuate simultan (în direcția înainte, din starea inițială și în direcția opusă, din target), oprindu-se după ce cele două procese de căutare se întâlnesc la mijloc.
Căutarea bidirecțională se poate baza pe o strategie iterativă de aprofundare. O iterație include o căutare la adâncimea k în direcția înainte și două căutări la adâncimea k și k + 1 în direcția înapoi. Deoarece numai stările găsite prin căutare directă la adâncimea k sunt stocate în memorie , complexitatea spațială a căutării este definită ca O ( b d /2 ). Verificarea dacă un nod găsit printr-o căutare înapoi aparține periferiei unui arbore de căutare înainte poate fi efectuată în timp constant, astfel încât complexitatea de timp a unei căutări bidirecționale este definită ca O ( b d /2 ) [1] [9] [ 11] .
| Algoritmi de căutare grafică | ||
|---|---|---|
| Metode neinformate | ||
| Metode informate | ||
| Comenzi rapide | ||
| Arborele de întindere minim | ||
| Alte | ||