A*

Căutare A * (pronunțat „A star” sau „A star”, din engleză  A star ) - în informatică și matematică , un algoritm de căutare pentru prima potrivire cea mai bună pe un grafic care găsește ruta cu cel mai mic cost dintr-un vârf ( initial) la altul (tinta, finala).

Ordinea în care sunt parcurse vârfurile este determinată de funcția euristică distanță + cost (notată în mod obișnuit ca f(x) ). Această funcție este suma altor două: funcția de cost pentru atingerea vârfului considerat ( x ) de la cel inițial (notat de obicei cu g(x) și poate fi fie euristică, fie nu) și funcția de estimare euristică a distanței. de la vârful considerat până la cel final (notat cu h (x) ).

Funcția h(x) trebuie să fie o estimare euristică validă , adică nu trebuie să supraestimeze distanțele până la vârful țintă. De exemplu, pentru o problemă de rutare, h(x) ar putea fi distanța până la țintă într-o linie dreaptă, deoarece este cea mai mică distanță fizică posibilă între două puncte.

Acest algoritm a fost descris pentru prima dată în 1968 de Peter Hart , Nils Nilsson și Bertram Raphael . A fost în esență o extensie a algoritmului lui Dijkstra , creat în 1959. Noul algoritm a obținut performanțe mai mari (în timp) folosind euristica. În munca lor, este denumit „Algoritmul A”. Dar, deoarece calculează cea mai bună rută pentru o anumită euristică, a fost numit A*.

O generalizare a acestuia este algoritmul de căutare euristică bidirecțională .

Istorie

În 1964, Nils Nilsson a inventat o abordare euristică pentru a accelera algoritmul lui Dijkstra . Acest algoritm a fost numit A1 . În 1967, Bertram Raphael a adus îmbunătățiri semnificative acestui algoritm, dar nu a reușit să atingă optimitatea. El a numit acest algoritm A2 . Apoi, în 1968, Peter E. Hart a prezentat argumente care susțin că A2 era optim atunci când se folosește euristica secvenţială cu doar modificări minore. Dovada sa a algoritmului a inclus și o secțiune care a arătat că noul algoritm A2 a fost, probabil, cel mai bun algoritm, având în vedere condițiile. Astfel, a marcat noul algoritm în sintaxă cu un asterisc, începe cu A și a inclus toate numerele de versiune posibile.

Descrierea algoritmului

A* iterează prin toate căile care duc de la vârful de început până la vârful final până îl găsește pe cel mai mic. La fel ca toți algoritmii de căutare informată , se analizează mai întâi rutele care „par” să conducă la obiectiv. Diferă de algoritmul greedy , care este, de asemenea, un algoritm de căutare pentru prima potrivire cea mai bună, prin faptul că atunci când alegeți un vârf, ia în considerare, printre altele, întreaga cale parcursă până la acesta. Componenta g(x)  este costul căii de la vârful inițial, și nu din cel anterior, ca în algoritmul greedy.

La începutul lucrării se examinează nodurile adiacente celui inițial; se selectează cel care are valoarea minimă a f(x) , după care se extinde acest nod. În fiecare etapă, algoritmul operează pe un set de căi de la punctul de plecare până la toate vârfurile (frunze) încă neexplorate ale graficului - un set de soluții particulare - care este plasat într- o coadă de prioritate . Prioritatea traseului este determinată de valoarea f(x) = g(x) + h(x) . Algoritmul își continuă activitatea până când valoarea f(x) a vârfului țintă este mai mică decât orice valoare din coadă sau până când întregul arbore a fost scanat. Din setul de soluții se selectează soluția cu cel mai mic cost.

Cu cât este mai mică euristica h(x) , cu atât este mai mare prioritatea, astfel încât arborii de sortare pot fi folosiți pentru a implementa coada .

Setul de vârfuri vizualizate este stocat în closed, iar căile care trebuie luate în considerare sunt în coada de prioritate open. Prioritatea căii este calculată folosind funcția f(x) din implementarea cozii de prioritate.

Pseudo cod:

funcția A* ( început, obiectiv, f ) % set de vârfuri deja trecute var inchis : = multimea goala % set de soluții particulare var deschis := make_queue ( f ) coadă ( deschis , cale ( start )) în timp ce deschis nu este gol var p := remove_first ( deschidere ) var x : = ultimul nod al p dacă x închis _ continua dacă x = obiectiv întoarce p adaugă ( închis , x ) % adaugă vârfuri adiacente pentru fiecare y în succesori ( x ) coadă ( deschidere , adăugare_la_cale ( p , y )) eșecul de întoarcere

Setul de vârfuri deja trecute poate fi omis (în acest caz, algoritmul se va transforma într-o căutare în arbore de decizie), dacă se știe că soluția există, sau dacă successorspoate întrerupe cicluri .

Exemplu

Un exemplu de algoritm A* în acțiune, unde nodurile sunt orașe conectate prin drumuri și H(x) este cea mai scurtă distanță până la punctul țintă:

Cheie: verde - start, albastru - țintă, portocaliu - noduri vizitate.

Proprietăți

La fel ca Breadth First Search , A* este complet în sensul că găsește întotdeauna o soluție dacă există una.

Dacă funcția euristică h este admisibilă, adică nu supraestimează niciodată costul minim real al atingerii scopului, atunci A* este ea însăși admisibilă (sau optim ), de asemenea, cu condiția să nu tăiem vârfurile traversate. Dacă facem acest lucru, atunci pentru optimitatea algoritmului este necesar ca h(x) să fie și o euristică monotonă sau succesivă . Proprietatea monotonității înseamnă că, dacă există căi A-B-C și A-C (nu neapărat prin B ), atunci estimarea costului căii de la A la C trebuie să fie mai mică sau egală cu suma estimărilor căilor A-B și B-C . (Monotonitatea este cunoscută și sub numele de inegalitatea triunghiului : o latură a unui triunghi nu poate fi mai lungă decât suma celorlalte două laturi.) Matematic, pentru toate căile x , y (unde y  este un copil al lui x ) este:

A* este, de asemenea, optim eficient pentru o dată euristică h . Aceasta înseamnă că orice alt algoritm explorează cel puțin la fel de multe noduri ca A* (cu excepția cazului în care există mai multe soluții particulare cu aceeași euristică care corespunde exact costului căii optime).

În timp ce A* este optim pentru graficele date „aleatoriu”, nu există nicio garanție că va face o treabă mai bună decât algoritmii mai simpli, dar mai conștienți de domeniu . De exemplu, într-un anumit labirint , poate fi necesar să mergeți mai întâi în direcția de la ieșire și abia apoi să vă întoarceți. În acest caz, sondajul de la începutul acelor vârfuri care sunt mai aproape de ieșire (în linie dreaptă) va fi o pierdere de timp.

Ocazii speciale

În general vorbind, adâncimea - prima căutare și lățimea-prima căutarea sunt două cazuri speciale ale algoritmului A*. Pentru căutarea în profunzime, să luăm un numărător de variabile global C , inițialându-l cu o valoare mare. De fiecare dată când extindem un vârf, vom atribui valoarea contorului vârfurilor adiacente, decrementând-o cu unul după fiecare atribuire. Astfel, cu cât un vârf este deschis mai devreme, cu atât valoarea lui h(x) va fi mai mare, ceea ce înseamnă că va fi văzut ultimul. Dacă punem h(x) = 0 pentru toate vârfurile, atunci obținem un alt caz special - algoritmul lui Dijkstra .

Detalii de implementare

Există mai multe caracteristici și tehnici de implementare care pot afecta semnificativ eficiența algoritmului. Primul lucru la care nu strică să acordați atenție este modul în care coada de prioritate gestionează conexiunile dintre vârfuri. Dacă se adaugă vârfuri în așa fel încât coada să funcționeze conform principiului LIFO , atunci în cazul nodurilor cu aceeași evaluare, A* va „merge” la adâncime. Dacă, totuși, la adăugarea nodurilor, principiul FIFO este implementat , atunci pentru nodurile cu aceeași estimare, algoritmul, dimpotrivă, va implementa o căutare pe lățime. În unele cazuri, această circumstanță poate avea un impact semnificativ asupra performanței .

Dacă, la sfârșitul lucrării, este necesară o rută de la algoritm, o legătură către nodul părinte este de obicei stocată împreună cu fiecare vârf. Aceste legături vă permit să reconstruiți traseul optim. Dacă da, atunci este important ca același vârf să nu apară de două ori în coadă (în timp ce are propriul traseu și propria estimare a costurilor). De obicei, pentru a rezolva această problemă, atunci când adaugă un vârf, ei verifică dacă există o intrare despre acesta în coadă. Dacă este, atunci înregistrarea este actualizată astfel încât să corespundă costului minim al celor două. Pentru a găsi un vârf într-un arbore de sortare, mulți algoritmi standard iau timp O(n). Dacă îmbunătățiți arborele cu un tabel hash , atunci puteți reduce acest timp.

De ce A* este valid și optim

Algoritmul A* este atât admisibil cât și parcurge numărul minim de vârfuri, datorită faptului că funcționează cu o estimare „optimistă” a drumului prin vârf. Optimist în sensul că dacă trece prin acest vârf, algoritmul „are șansa” ca costul real al rezultatului să fie egal cu această estimare, dar nu mai puțin. Dar, deoarece A* este un algoritm informat, o astfel de egalitate ar putea fi posibilă.

Când A* finalizează căutarea, a găsit, prin definiție, o cale al cărei cost adevărat este mai mic decât costul estimat al oricărei căi prin orice nod deschis. Dar, deoarece aceste estimări sunt optimiste, nodurile corespunzătoare pot fi aruncate fără îndoială. Cu alte cuvinte, A* nu pierde niciodată o oportunitate de a minimiza lungimea unei căi și, prin urmare, este legal.

Să presupunem acum că un algoritm B a returnat ca rezultat o cale a cărei lungime este mai mare decât costul estimat al căii printr-un vârf. Pe baza informațiilor euristice, pentru algoritmul B , nu poate fi exclusă posibilitatea ca această cale să aibă o lungime reală mai mică decât rezultatul. În consecință, în timp ce algoritmul B a analizat mai puține vârfuri decât A*, acesta nu va fi valid. Deci, A* parcurge cel mai mic număr de vârfuri de grafic dintre algoritmii validi folosind aceeași euristică exactă (sau mai puțin precisă).

Evaluare de dificultate

Complexitatea temporală a algoritmului A* depinde de euristica. În cel mai rău caz, numărul de vârfuri explorate de algoritm crește exponențial în comparație cu lungimea căii optime, dar complexitatea devine polinomială atunci când euristica satisface următoarea condiție:

;

unde h* este euristica optimă, adică o estimare precisă a distanței de la x la țintă. Cu alte cuvinte, eroarea h(x) nu ar trebui să crească mai repede decât logaritmul euristicii optime.

Dar o problemă și mai mare decât complexitatea timpului este resursele de memorie consumate de algoritm . În cel mai rău caz, trebuie să-și amintească un număr exponențial de noduri. Pentru a combate acest lucru, au fost propuse mai multe variații ale algoritmului, cum ar fi algoritmul A* cu adâncire iterativă (aprofundare iterativă A*, IDA*), A* cu A*, MA*, MA* simplificat (MA simplificat) *, SMA*) și recursive best-first search (RBFS).

Literatură

  • Laurier J.-L. Sisteme de inteligență artificială / Per. din fr. şi ed. V. L. Stefanyuk. - M . : Mir, 1991. - S. 238-244. — 20.000 de exemplare. copie.  — ISBN 5-03-001408-X .
  • Russell S.J., Norvig, P. Artificial Intelligence: A Modern Approach = Artificial Intelligence: A Modern Approach / Per. din engleza. şi ed. K. A. Ptitsyna. - Ed. a 2-a - M . : Williams, 2006. - S. 157-162. - 3000 de exemplare. copie.  — ISBN 5-8459-0887-6 .
  • Nilson N. Artificial Intelligence: Methods for Finding Solutions = Problem-solving Methods in Artificial Intelligence / Per. din engleza. V. L. Stefanyuk; ed. S. V. Fomina. - M . : Mir, 1973. - S. 70 - 80.
  • Dechter, R., Pearl, J. Generalized best-first search strategies and optimity of A*  // Journal of the ACM. - 1985. - T. 32 , nr 3 . - S. 505 - 536 .
  • Hart PE, Nilsson, NJ, Raphael, B. O bază formală pentru determinarea euristică a căilor de cost minim // Tranzacții IEEE privind știința sistemelor și cibernetica SSC4. - 1968. - Nr 2 . - S. 100 - 107 .
  • Hart PE, Nilsson, NJ, Raphael, B. Corecție la „O bază formală pentru determinarea euristică a căilor de cost minim” // Buletin informativ SIGART. - 1972. - T. 37 . - S. 28 - 29 .
  • Pearl J. Euristică: Strategii inteligente de căutare pentru rezolvarea problemelor computerizate. - Addison-Wesley, 1984. - ISBN 0-201-05594-5 .

Link -uri

 Algoritmi de căutare grafică
Metode neinformate
Metode informate
Comenzi rapide
Arborele de întindere minim
Alte