Algoritmul A *

Algoritmul A *

Clasă	Algoritm de căutare
Structură de date	Grafic
Cel mai rău caz din punct de vedere temporal	$O(\|E\|)=O(b^{d})$ ${\ displaystyle O (\| E \|) = O (b ^ {d})}$ ${\ displaystyle O (\| E \|) = O (b ^ {d})}$
Cel mai rău caz spațial	$O(\|V\|)=O(b^{d})$ ${\ displaystyle O (\| V \|) = O (b ^ {d})}$ ${\ displaystyle O (\| V \|) = O (b ^ {d})}$
Optim	da
Costum de afaceri	da
Manual

În informatică , A * (pronunțat / eɪ stɑːr / în engleză ) este un algoritm de căutare a graficului care găsește o cale de la un nod inițial dat la un nod obiectiv dat (sau trece un test obiectiv dat). Folosește o „estimare euristică” care clasifică fiecare nod prin estimarea celei mai bune rute prin acel nod. Vizitați nodul pe baza acelei estimări euristice. Algoritmul A * este, de asemenea, un exemplu de primă căutare .

Algoritmul a fost descris pentru prima dată în 1968 de Peter Hart , Nils Nilsson și Bertram Raphael .

Intuiţie

Să luăm în considerare un exemplu motivant. Suntem la o intersecție A și am dori să mergem la o intersecție B care, din fericire, știm că se află la nord de noi. În acest caz, intersecțiile sunt vârfurile unui grafic, iar drumurile sunt arcurile.

Dacă efectuați o primă căutare, așa cum este ilustrat de algoritmul lui Dijkstra , vom căuta fiecare punct cu o rază circulară fixă, treptat vom extinde acest cerc pentru a căuta intersecțiile cele mai îndepărtate de punctul nostru de plecare. Aceasta poate fi o strategie eficientă dacă nu știți unde este destinația, așa cum fac poliția în căutarea unui criminal ascuns.

Cu toate acestea, veți pierde timpul dacă aveți mai multe informații. O strategie mai bună este explorarea intersecțiilor situate la nord de prima, deoarece acestea vor fi probabil vârfurile cele mai apropiate de B. Cu toate acestea, trebuie remarcat faptul că drumurile ar putea fi închise obligându-ne să mergem spre sud pentru a ajunge la destinație cu o cale modelată. de C. Deci, dacă drumurile o permit, vom merge și vom explora intersecțiile din ce în ce mai aproape de intersecția obiectivului B. Vom avea nevoie de o retragere ocazională, dar intuitiv aceasta este o strategie care are șanse mari de găsind rapid obiectivul. În plus, se poate dovedi că această strategie va găsi, în orice caz, cea mai bună cale posibilă, adică soluția optimă, la fel ca și căutarea în primul rând. Aceasta este esența cercetării A *.

Cu toate acestea, nu există nicio garanție că A * va funcționa mai bine decât algoritmii simpli de căutare. Într-un mediu foarte complicat, singura modalitate de a ajunge la destinație ar putea fi să ne îndreptăm spre sud și apoi să ne plimbăm în jurul lui. În aceste cazuri, testarea nodurilor cele mai apropiate de destinația noastră ar putea fi o pierdere de timp.

Vedere de ansamblu

Se spune că este admisibil un algoritm de căutare care garantează întotdeauna găsirea celei mai scurte căi către un obiectiv. Dacă A * folosește o euristică, atunci distanța (sau, în general, costul) față de obiectiv nu trebuie niciodată supraestimată, deci se poate verifica dacă A * va fi admisibilă. O euristică care face căutarea A * admisibilă se numește euristică admisibilă .

Dacă estimarea returnează pur și simplu zero, ceea ce nu va fi niciodată o supraestimare, atunci A * va efectua algoritmul lui Dijkstra și va găsi în continuare o soluție optimă, deși nu rapid. Cea mai bună euristică posibilă, deși nu este de obicei practic să o calculăm, este distanța minimă efectivă până la obiectiv. Un exemplu de euristică practică acceptabilă este distanța în care cioara zboară de la destinație pe o hartă.

Se poate verifica că A * nu ia în considerare mai multe noduri decât orice alt algoritm de căutare fezabil, cu excepția cazului în care algoritmul alternativ are o estimare euristică mai precisă. În acest sens, A * este algoritmul cel mai eficient din punct de vedere al calculului, care garantează căutarea celei mai scurte căi.

Descriere

A * începe de la nodul selectat. Un cost de intrare este definit pentru fiecare nod (de obicei zero pentru nodul inițial). A * evaluează apoi distanța de la meta-nod de la cel curent. Această estimare și costul formează împreună euristica care va fi atribuită căii care trece prin acest nod. Nodul este apoi adăugat la o listă , numită adesea „deschis”.

Algoritmul elimină apoi primul nod din listă (deoarece va avea cea mai mică valoare a funcției euristice). Dacă lista este goală, nu vor exista căi de la nodul de pornire la meta nod și algoritmul se va opri. Dacă nodul este meta nodul, A * reconstruiește și transmite calea obținută și se oprește. Această reconstrucție a căii pornind de la cele mai apropiate noduri înseamnă că nu este necesară memorarea căii în fiecare nod.

Dacă nodul nu este meta nodul, vor fi create noi noduri pentru toate nodurile vecine admisibile; cum se face acest lucru depinde de problemă. Pentru fiecare nod ulterior A * calculează „costul” intrării în nod și îl salvează cu nodul. Acest cost este calculat din suma cumulativă a greutăților stocate în strămoși, plus costul operațiunii pentru a ajunge la acest nou nod.

Algoritmul gestionează, de asemenea, o listă „închisă”, o listă de noduri care au fost deja verificate. Dacă un nou nod generat este deja în listă cu un cost egal sau mai mic, nu va exista nicio investigație viitoare a acelui nod sau a căii sale asociate. Dacă un nod din lista închis este același cu unul nou, dar a fost stocat la un cost mai mare, atunci acesta va fi eliminat din lista închisă, iar procesul va continua începând de la noul nod.

Apoi, o estimare a distanței de la noul nod la obiectiv este adăugată la cost pentru a-și forma valoarea euristică. Acest nod este apoi adăugat la lista „deschisă”, cu excepția cazului în care există un nod identic cu valoare euristică mai mică sau egală.

Algoritmul va fi adoptat la fiecare nod vecin, după care nodul original este preluat din listă și plasat în lista „închis”. Următorul nod va fi obținut din lista deschisă și odată cu acesta se va repeta procesul descris.

Deoarece A * este admisibil și optim din punct de vedere al calculului

Animația algoritmului A * care explorează America de Nord în căutarea unei rute între Washington DC și Los Angeles.

Există o explicație intuitivă a motivului pentru care A * este admisibil și optim în comparație cu alți algoritmi de căutare admisibili. A * are o estimare optimistă a costului căii prin fiecare nod luat în considerare, optimismul constă și în a ști că adevăratul cost al căii prin fiecare nod până la nodul obiectiv va merita cel puțin ceea ce este estimarea noastră. Totul se bazează pe cât de mult „știe” A *.

Când A * și-a terminat căutarea, prin definiție va fi găsit o cale al cărei cost actual este mai mic decât costul estimat pentru fiecare cale prin toate nodurile rămase deschise. Dar fiind această estimare optimistă, A * poate ignora în siguranță aceste noduri. Cu alte cuvinte, A * nu va neglija niciodată posibilitatea de a găsi o rută mai ieftină și, prin urmare, va fi eligibil.

Acum, să presupunem că un alt algoritm de căutare A își termină căutarea cu o cale al cărei cost nu este mai mic decât costul estimat pentru un nod aparținând deschiderii. Algoritmul A nu poate elimina posibilitatea, pe baza informațiilor euristice pe care le deține, ca o cale printr-un astfel de nod să aibă un cost mai mic decât cel estimat. Deci, chiar dacă A poate considera mai puține noduri decât A *, nu poate fi admisibil. Prin urmare, A * consideră că numărul de noduri este mai mic decât orice alt algoritm de căutare fezabil care utilizează o funcție euristică nu mai precisă decât cea adoptată de A *.

Monotonie

Dacă se poate garanta că prima cale găsită de A * către orice nod este cea optimă, atunci lista ÎNCHIS nu va fi necesară. Va fi necesară doar o listă a nodurilor deja vizitate (DESCHIS), astfel încât aceste noduri nu vor fi revizuite (deoarece nu va fi necesar să se facă acest lucru). Această garanție poate fi obținută dacă funcția euristică este nu numai admisibilă, ci și monotonă (sau consecventă), adică dacă diferența dintre valorile euristice pentru fiecare pereche de noduri conectate nu depășește costul real asociat arcului care le conectează. (h (n1) ≤ c (n1, n2) + h (n2)). Aceasta este o formă de inegalitate triunghiulară și garantează că nodurile de-a lungul oricărei căi din spațiul de căutare au întotdeauna f (n) nedescrescând ( funcția de evaluare ). Se arată că A *, cu această euristică, extinde nodurile în ordinea descrescătoare a f (n), deoarece datorită cerinței de monotonie nu va fi niciodată generat un nod cu f (n) mai mic decât cel al părintelui. Dacă A * extinde nodurile în ordine non-descrescătoare, atunci chiar și atunci când se găsește o nouă cale spre un nod deja în ÎNCHIS, ar putea fi ignorată deoarece ar avea cu siguranță f (n) mai mare sau egal cu cea a deja extinsă nod, și având aceeași valoare estimativă euristică (este același nod) calea parcursă până la acel punct va avea cu siguranță un cost mai mare sau egal. Prin urmare, îl putem arunca și putem afirma că prima cale găsită de A * către un nod este calea optimă până la acel nod.

Se arată că o euristică monotonă este admisibilă și, prin urmare, dacă se respectă restricția de monotonie, se obține și calea optimă către obiectiv. Intuitiv, dacă prima cale găsită către un nod este cea optimă (spre acel nod) atunci acest lucru este valabil și pentru nodul obiectiv și, prin urmare, dacă algoritmul se termină, o face cu soluția optimă. Este util să ne amintim că A *, cu euristică admisibilă, se termină întotdeauna pe grafice finite și cu costuri strict pozitive.

Restricția asupra monotoniei este o cerință mai strictă decât admisibilitatea, dar pentru multe probleme clasice se poate observa că o euristică admisibilă este de obicei și monotonă. Un foarte bun exemplu de euristică admisibilă și consecventă este cel al distanței în care cioara zboară între două puncte, utilizat la calcularea traseului rutier optim între orașele unei hărți. Această euristică ne permite să „vedem” ce înseamnă a fi admisibil și consecvent. Este cu siguranță admisibil, deoarece niciun drum între două puncte nu poate fi mai scurt decât distanța dintre linia dreaptă dintre ele și, prin urmare, euristica nu supraestimează niciodată costul de la un nod la obiectiv. Este consecvent, așa cum se poate observa ușor desenând un triunghi în care vârfurile sunt trei orașe pe o hartă mică. Alegem orașul de plecare și orașul de sosire, imaginându-ne că drumul trece prin al treilea oraș. Dacă desenăm orice drum între start și sosire, lungimea acestuia este mai mare sau egală cu cea a laturii care le unește și fiecare latură a unui triunghi este la rândul ei mai mare sau egală cu diferența dintre celelalte două laturi. Prin urmare, restricția de monotonie este respectată.

Pseudo cod

Următorul pseudocod descrie algoritmul:

 funcția A * ( start , obiectiv )
     closedset: = mulțimea vidă% Setul de noduri deja evaluate.     
     cu carcasa: = set care conține inițial nod% Setul de noduri tentative de a fi evaluate.
     g_score [ start ] : = 0 % Distanța de la început de -a lungul căii optime .
     came_from: = vida map% Harta nodurilor navigau.
     h_score [ start ] : = heuristic_estimate_of_distance ( start , goal )
     f_score [ start ] : = h_score [ start ] % Distanța totală estimată de la început până la obiectiv până la y .
     în timp ce deschiderea nu este goală
         x: = nodul în care are valoarea cu carcasa cea mai mică f_score []
         dacă x = obiectiv
             returnează cale reconstituire ( venit_de , gol )
         eliminați x din deschidere
         adăugați x la setul închis
         y foreach în neighbor_nodes (x)
             dacă y în closetset
                 continua
             tentativ_g_score : = g_score [ x ] + dist_between ( x , y )
             
             în cazul în care nu y în cu carcasa
                 adăugați y la deschidere
                
                 tentativ_este_mai bun : = adevărat
             elseif tentativ_g_score < g_score [ y ]
                 tentativ_este_mai bun : = adevărat
             altceva
                 tentativ_este_mai bun : = false
             dacă tentativ_este_mai bun = adevărat
                 venit_de [ y ] : = x
                 g_score [ y ] : = tentativ_g_score
                 h_score [ y ] : = heuristic_estimate_of_distance ( y , goal )
                 f_score [ y ] : = g_score [ y ] + h_score [ y ]
     eșecul de întoarcere

 funcție reconstruct_path ( came_from , current_node )
     dacă este setat came_from [ current_node ]
         p = reconstruct_path ( came_from , came_from [ current_node ])
         returnare ( p + curent_nod )
     altceva
         a reveni calea goală

Bibliografie

PE Hart, NJ Nilsson, B. Raphael: O bază formală pentru determinarea euristică a căilor de cost minim , Tranzacții IEEE pe știința sistemelor și cibernetică SSC4 (2), pp. 100-107, 1968.
PE Hart, NJ Nilsson, B. Raphael: Corecție la „O bază formală pentru determinarea euristică a căilor de cost minim” , SIGART Newsletter, 37, pp. 28-29, 1972.
NJ Nilsson, Principiile inteligenței artificiale , Tioga Publishing Company, Palo Alto, California, 1980.

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe A *

linkuri externe

(RO) Tutorialul algoritmului A * al lui Justin Heyes-Jones
(RO) Un alt A * Pathfinding pentru începători , pe policyalmanac.org. Adus la 28 ianuarie 2006 (arhivat din original la 24 decembrie 2005) .
( RO ) Gândurile lui Amit despre căutarea căilor și A *
( EN ) Demonstrația lui Sven Koenig de planificare pe tot parcursul vieții A * și A *
(RO) Remko Troncon și Joost Vennekens lui JSearch demo Filed 11 februarie 2006 Internet Arhiva :. Demonstrează diferite algoritmi de căutare, inclusiv A *.
(EN) Căutarea Sune Trudslev în articolul C #

Portal IT

Portalul de matematică