A* paieškos algoritmas
A* - tai veiksmų rinkinys (algoritmas), kuriuo naudodamiesi kompiuteriai gali nustatyti, kaip greitai nuvykti iš vienos vietos į kitą. Jei turite vietovių sąrašą ir žinote, kaip sunku nuvykti iš vienos vietos tiesiai į kitą, naudodami A* galite greitai rasti greičiausią kelią. Jis susijęs su Dijkstros algoritmu, tačiau daro protingus spėjimus, kad nereikėtų taip ilgai bandyti lėtų kelių. Tai gera žingsnių serija, jei jums reikia tik kelio tarp dviejų vietų. Jei ketinate prašyti daug kelių iš to paties žemėlapio, yra greitesnių būdų, kurie randa visus atsakymus iš karto, pavyzdžiui, Floyd-Warshall algoritmas. A* neveiks, jei vienos kelionės metu norite aplankyti kelias vietas (keliaujančio pardavėjo uždavinys).
Žingsniai
A* pirmiausia reikia visų vietų, į kurias galite nuvykti, sąrašo, o tada reikia nurodyti, koks atstumas iki kiekvienos iš jų. Tada jis nurodys greičiausią kelią iš vietos A į vietą Z.
Pavyzdžiui, sakysime, kad A yra sujungta su vietomis B ir C, o B ir C yra sujungtos su D ir E. D ir E yra sujungtos su Z. Yra 4 galimi keliai iš A į Z. Galima eiti A-B-D-Z, A-C-D-Z, A-B-E-Z arba A-C-E-Z. Kompiuteris, naudojantis A*, pirmiausia žiūri, kaip sunku nuvykti iš A į B ir iš A į C. Tai yra tų vietų "kaina". Vietos kaina reiškia, kaip sunku nuvykti iš A į tą vietą. Užrašęs abi sąnaudas, kompiuteris pažiūri, kaip sunku nuvykti iš B į D, ir prideda tai prie B sąnaudų. Jis tai užrašo kaip D kainą. Tada kompiuteris pažiūri, kaip sunku nuvykti iš C į D, ir prideda tai prie C išlaidų. Tai yra kitos D išlaidos, ir jei jos yra mažesnės už jau turimas, jis pakeis senąsias. Kompiuteris nori žinoti tik geriausią kelią, todėl jis ignoruoja kelią, kurio sąnaudos yra didesnės. Jis įsimins tik vieną iš A-B-D ir A-C-D, priklausomai nuo to, kuris yra greitesnis.
Kompiuteris toliau ieško greičiausio kelio į E. Galiausiai jis eina iš D į Z ir randa sąnaudas, o iš E į Z ir randa sąnaudas. Jis gauna galutinę Z kainą, ir tai yra mažiausia kaina, kurią jis gali gauti. Dabar kompiuteris žino, kuris kelias yra greičiausias, ir turi atsakymą. Kompiuteris gali atlikti panašią veiksmų seriją, tačiau su daug daug daugiau vietų. Kiekvieną kartą jis ieškos vietos, kuri yra arčiausiai A, ir sudės tos vietos kaimynų išlaidas.
Pirmiau aprašyta veiksmų seka vadinama Dijkstros algoritmu. Dijkstros algoritmas gali būti lėtas, nes jis ieškos daugybės vietų, kurios gali būti nukreiptos ne į tą pusę nuo Z. Jei paklausėte kompiuterio, kaip nuvykti iš vieno miesto į šalia esantį, Dijkstros algoritmas gali baigti ieškoti kitoje valstybėje.
A* išsprendžia šią problemą. A* leidžia kompiuteriui atspėti, koks bus atstumas nuo kiekvienos vietos iki galo. Kompiuteris, remdamasis spėjimu, gali apytiksliai pasakyti, kiek reikės nueiti nuo tam tikros vietos iki Z. Užuot rinkęsis artimiausią A vietą, kompiuteris pažiūrės į tą vietą, kurios bendra suma tikriausiai bus mažiausia. Šią bendrą sumą jis randa prie tikėtino likusio atstumo pridėdamas išlaidas. Tokiu būdu jis gali ieškoti tik ta kryptimi, kur tikriausiai bus geriau. Nieko baisaus, jei spėjimas nėra tobulas, tačiau net ir paprastas blogas spėjimas gali priversti programą veikti daug greičiau. Jei bandote rasti kelią tarp dviejų vietų realiame pasaulyje, geras spėjimas yra tiesiog atstumas tarp jų tiesia linija. Tikrasis kelias per kelius bus ilgesnis, bet tai leidžia programai jį atspėti ir ji nenueis klaidinga kryptimi.
Matematikos ar informatikos literatūroje šis spėjimas dažnai būna vietos funkcija ir vadinamas euristika. Kiekviena vieta yra viršūnė, o kiekvienas kelias tarp dviejų vietų - briauna. Tai žodžiai iš grafų teorijos.
