Algoritmul de căutare A*
A* este un set de pași (un algoritm) pe care computerele îl pot folosi pentru a afla cum să ajungă rapid între două locuri. Dacă aveți o listă de locații și știți cât de greu este să ajungeți de la una la alta, folosind A* puteți afla rapid care este cea mai rapidă cale. Este înrudit cu algoritmul lui Dijkstra, dar face presupuneri inteligente, astfel încât nu pierde atât de mult timp încercând căi lente. Este o serie bună de pași dacă doriți doar drumul dintre două locuri. Dacă aveți de gând să cereți mai multe trasee din aceeași hartă, există metode mai rapide, care găsesc toate răspunsurile dintr-o dată, cum ar fi algoritmul Floyd-Warshall. A* nu va funcționa dacă doriți să vizitați mai multe locuri într-o singură călătorie (problema comis-voiajorului călător).
Etapele
A* are nevoie mai întâi de o listă cu toate locurile în care poți merge, apoi de o listă cu distanța dintre fiecare dintre ele. Apoi vă va spune care este cea mai rapidă cale de a ajunge din locul A în locul Z.
De exemplu, să spunem că A este conectat la locurile B și C, iar B și C sunt conectate la D și E. D și E sunt conectate la Z. Există 4 moduri posibile de a merge de la A la Z. Puteți merge A-B-D-Z, A-C-D-Z, A-B-E-Z sau A-C-E-Z. Un computer care utilizează A* analizează mai întâi cât de greu este să ajungi din A în B și din A în C. Acesta este "costul" pentru acele locuri. Costul unui loc înseamnă cât de greu este să ajungi din A în acel loc. După ce a notat ambele costuri, calculatorul analizează cât de greu este să ajungi de la B la D și adaugă acest lucru la costul lui B. Acesta notează acest rezultat ca fiind costul lui D. Apoi, calculatorul analizează cât de greu este să ajungi de la C la D și adaugă acest lucru la costul lui C. Acesta este un cost diferit pentru D și, dacă este mai mic decât cel pe care îl are deja, îl va înlocui pe cel vechi. Calculatorul vrea doar să știe care este cea mai bună cale, așa că ignoră calea cu un cost mai mare. Își va aminti doar una dintre A-B-D și A-C-D, oricare dintre ele este mai rapidă.
Calculatorul continuă și găsește cea mai rapidă cale de a ajunge la E. În cele din urmă, merge de la D la Z și găsește un cost, iar de la E la Z și găsește un cost. Obține un cost final pentru Z, iar acesta este cel mai mic cost pe care îl poate obține. Acum calculatorul știe care este cel mai rapid drum și are răspunsul. Calculatorul poate face o serie similară de pași, dar cu mult mai multe locuri. De fiecare dată, se va uita la locul care este cel mai apropiat de A și va aduna costurile pentru vecinii acelui loc.
Această serie de pași se numește algoritmul lui Dijkstra. Algoritmul lui Dijkstra poate fi lent, deoarece va căuta în multe locuri care ar putea merge în direcția greșită față de Z. Dacă ați întrebat computerul cum să ajungeți dintr-un oraș într-unul apropiat, algoritmul lui Dijkstra ar putea ajunge să caute în alt stat.
A* rezolvă această problemă. A* vă permite să indicați calculatorului o estimare a distanței dintre fiecare loc și final. Calculatorul poate folosi această presupunere pentru a determina aproximativ cât de mult va dura să ajungă dintr-un anumit loc la Z. În loc să aleagă doar locul cel mai apropiat de A pentru a se uita la el, se va uita la cel care va avea probabil cel mai mic total. Acest total se obține prin adăugarea costului la distanța estimată rămasă. În acest fel, se poate căuta doar în direcția în care lucrurile se vor îmbunătăți probabil. Este în regulă dacă presupunerea nu este perfectă, dar chiar și o simplă presupunere greșită poate face ca programul să meargă mult mai repede. Dacă încercați să găsiți o cale între două locuri din lumea reală, o presupunere bună este doar distanța dintre ele în linie dreaptă. Calea reală pe drumuri va fi mai lungă, dar acest lucru permite programului să o ghicească, iar acesta nu va merge în direcția greșită.
În literatura matematică sau informatică, această presupunere este adesea o funcție a locului și se numește euristică. Fiecare loc este un vertex, iar fiecare cale între două locuri este o muchie. Acestea sunt cuvinte din teoria grafurilor.
