Care sunt diferențele dintre A * și cea mai liniștită cea mai bună căutare?

Ambii algoritmi se încadrează în categoria „best-first search” algoritmi, care sunt algoritmi care pot folosi atât cunoștințele dobândite până acum în timp ce explorează spațiul de căutare, notate cu $ g (n) $ , și o funcție euristică, notată cu $ h (n) $ , care estimează distanța până la nodul obiectivului, pentru fiecare nod $ n $ în spațiul de căutare (adesea reprezentat ca un grafic).

Fiecare dintre acești algoritmi de căutare definește o „funcție de evaluare”, pentru fiecare nod $ n $ din grafic (sau spațiul de căutare), notat cu $ f (n) $ . Această funcție de evaluare este utilizată pentru a determina care nod, în timpul căutării, este „extins” mai întâi, adică ce nod este primul eliminat din „franjă” (sau „frontieră” sau „frontieră”) , pentru a-i „vizita” pe copii. În general, diferența dintre algoritmii din categoria „best-first” este în definiția funcției de evaluare $ f (n) $ .

În cazul algoritmul BFS lacom , funcția de evaluare este $ f (n) = h (n) $ , adică algoritmul BFS lacom extinde mai întâi nodul a cărui distanță estimată până la obiectiv este cea mai mică. Deci, BFS lacom nu folosește „cunoștințele anterioare”, adică $ g (n) $ . De aici conotația sa „lacomă”. În general, algoritmul lacom BST nu este complet , adică există întotdeauna riscul de a lua o cale care nu aduce la obiectiv. În algoritmul BFS lacom, toate nodurile de pe chenar (sau franjuri sau frontiere) sunt păstrate în memorie, iar nodurile care au fost deja extinse nu trebuie să fie stocate în memorie și, prin urmare, pot fi eliminate. În general, lacomul BFS este, de asemenea, nu optim , adică calea găsită poate să nu fie cea optimă. În general, complexitatea timpului este $ \ mathcal {O} (b ^ m) $ , unde $ b $ este factorul de ramificare (maxim) și $ m $ este adâncimea maximă a arborelui de căutare. Complexitatea spațiului este proporțională cu numărul de noduri din franj și cu lungimea căii găsite.

În cazul A * algoritm , funcția de evaluare este $ f (n) = g (n) + h (n) $ , unde $ h $ este o funcție euristică admisibilă . „Steaua”, des denotată de un asterisc, *, se referă la faptul că A * folosește o funcție euristică admisibilă, ceea ce înseamnă în esență că A * este optimal , adică găsește întotdeauna calea optimă între nodul de pornire și nodul obiectivului. A * este, de asemenea, complet (cu excepția cazului în care există infinit de multe noduri de explorat în spațiul de căutare). Complexitatea timpului este $ \ mathcal {O} (b ^ m) $ . Cu toate acestea, A * trebuie să păstreze toate nodurile în memorie în timpul căutării, nu doar pe cele din periferie, deoarece A *, în esență, efectuează o „căutare exhaustivă” (care este „informată”, în sensul că folosește o funcție euristică ).

În rezumat, BFS lacom nu este complet, nu este optim, are o complexitate de timp de $ \ mathcal {O} (b ^ m) $ și o complexitate spațială care poate fi polinomială. A * este complet, optim și are o complexitate de timp și spațiu de $ \ mathcal {O} (b ^ m) $ . Deci, în general, A * folosește mai multă memorie decât BFS lacom. A * devine impracticabil atunci când spațiul de căutare este imens. Cu toate acestea, A * garantează, de asemenea, că calea găsită între nodul de pornire și nodul obiectiv este cea optimă și că algoritmul se termină în cele din urmă. Greedy BFS, pe de altă parte, folosește mai puțină memorie, dar nu oferă garanțiile de optimitate și completitudine ale lui A *. Deci, care algoritm este „cel mai bun” depinde de context, dar ambele sunt „cele mai bune” – primele căutări.

Notă: în practică, nu puteți utiliza niciunul dintre acești algoritmi: puteți de ex. folosiți, în schimb, IDA * .

Comentarii

• Comentariile nu sunt pentru discuții extinse; această conversație a fost mutată în chat .

Conform cărții Inteligență artificială: O abordare modernă (ediția a 3-a), de Stuart Russel și Peter Norvig, în special, secțiunea 3.5.1 Greedy best-first search (p. 92)

Greedy best-first search încearcă să extindă nodul cel mai apropiat de obiectiv, pe motiv că acest lucru este probabil să ducă la o soluție rapidă. Astfel, evaluează nodurile utilizând doar funcția euristică; adică $ f (n) = h (n) $ .

În acest în aceeași secțiune, autorii oferă un exemplu care arată că cea mai liniștită căutare nu este nici optimă, nici completă.

În secțiunea 3.5.2 A * căutare: Minimizând costul total estimat al soluției al aceleiași cărți (p. 93), se precizează

A * căutarea evaluează nodurile combinând $ g (n) $ , costul pentru a ajunge la nod și $ h (n) $ , costul pentru a ajunge de la nod la obiectiv $$ f (n) = g (n) + h (n). $$

Deoarece $ g (n) $ oferă costul căii de la nodul de start la nod $ n $ și $ h (n) $ este costul estimat al celei mai ieftine căi din $ n $ până la obiectiv, avem $ f (n) $ = costul estimat al celei mai ieftine soluții prin $ n $ .

Astfel, dacă încercăm să găsim cea mai ieftină soluție, un lucru rezonabil de încercat mai întâi este nodul cu cea mai mică valoare de $ g (n) + h (n) $ . Se pare că această strategie este mai mult decât rezonabilă: cu condiția ca funcția euristică $ h (n) $ să îndeplinească anumite condiții, o căutare * este completă și optimă. Algoritmul este identic cu căutarea cu costuri uniforme, cu excepția faptului că A * folosește $ g + h $ în loc de $ g $

Ceea ce ai spus nu este complet greșit, dar algoritmul A * devine optim și complet dacă funcția euristică h este admisibilă, ceea ce înseamnă că această funcție nu supraestimează niciodată costul atingerii obiectivului. În acest caz, algoritmul A * este mult mai bun decât algoritmul de căutare lacom.

Comentarii

• dragă, îmi poți elabora răspunsul. Îmi pare rău, dar nu am primit punctul tău.
• @IramShah – TemmanRafk vorbește despre dovada că A * este optim și complet. Pentru a face acest lucru, se arată din cauza inegalității triunghiului că euristica care estimează distanța rămasă până la obiectiv nu este o supraestimare. Pentru a vedea o explicație mai completă, consultați en.wikipedia.org/wiki/Admissible_heuri stic