A* otsingu algoritm
A* on sammude kogum (algoritm), mida arvutid saavad kasutada, et leida, kuidas kahe koha vahel kiiresti kuhugi jõuda. Kui teil on nimekiri kohtadest ja sellest, kui raske on ühest kohast otse teise jõuda, saab A* abil kiiresti välja selgitada kiireima tee. See on seotud Dijkstra algoritmiga, kuid teeb arukaid oletusi, nii et see ei kuluta nii kaua aega aeglaste viiside proovimiseks. See on hea sammude rida, kui soovite ainult teed kahe koha vahel. Kui te tahate küsida palju teid samalt kaardilt, siis on olemas kiiremad viisid, mis leiavad kõik vastused korraga, näiteks Floyd-Warshalli algoritm. A* ei tööta, kui tahate ühe teekonnaga külastada mitut kohta (reisiv müügimehe probleem).
Sammud
A* vajab kõigepealt nimekirja kõigist kohtadest, kuhu saab minna, ja seejärel nimekirja sellest, kui kaugel on tee iga koha vahel. Seejärel ütleb see teile, milline on kõige kiirem tee, et jõuda kohast A kohani Z.
Näitena ütleme, et A on ühendatud kohtadega B ja C ning B ja C on mõlemad ühendatud kohtadega D ja E. D ja E on mõlemad ühendatud kohtadega Z. A-st Z-sse saab minna 4 võimalust: A-B-D-Z, A-C-D-Z, A-B-E-Z või A-C-E-Z. Arvuti, mis kasutab A*, vaatab kõigepealt, kui raske on jõuda A-st B-sse ja A-st C-sse. See on nende kohtade "kulu". Koha maksumus tähendab seda, kui raske on jõuda kohast A sinna. Pärast mõlema kulu üleskirjutamist vaatab arvuti, kui raske on jõuda B-st D-sse, ja lisab selle B maksumusele. Ta kirjutab selle üles D maksumuseks. Seejärel vaatab arvuti, kui raske on jõuda C-st D-sse, ja lisab selle C maksumusele. See on teistsugune kulu D jaoks ja kui see on väiksem kui see, mis tal juba on, siis asendab ta vana. Arvuti tahab teada ainult parimat teed, seega ignoreerib ta suurema maksumusega teed. Ta jätab meelde ainult ühe A-B-D või A-C-D, olenevalt sellest, kumb neist on kiirem.
Arvuti läheb edasi ja leiab kõige kiirema tee, et jõuda E. Lõpuks läheb ta D-st Z-sse ja leiab maksumuse ning E-st Z-sse ja leiab maksumuse. Ta saab lõpliku maksumuse Z jaoks ja see on väikseim maksumus, mille ta saab. Nüüd teab arvuti, milline tee on kõige kiirem, ja tal on vastus. Arvuti võib teha samasuguse sammude seeria, kuid palju palju rohkemate kohtadega. Iga kord vaatab ta koha, mis on A-le kõige lähemal, ja liidab selle koha naabrite kulud kokku.
Inimesed nimetavad ülaltoodud sammude seeriat Dijkstra algoritmiks. Dijkstra algoritm võib olla aeglane, sest ta vaatab palju kohti, mis võivad minna Z-st valesse suunda. Kui te küsisite arvutilt, kuidas jõuda ühest linnast lähedasse linna, võib Dijkstra algoritm sattuda otsima teise riiki.
A* lahendab selle probleemi. A* laseb teil öelda arvutile, kui kaugele on igast kohast lõpuni. Arvuti saab arvamise põhjal öelda, kui kaugele on vaja minna teatud kohast Z. Selle asemel, et lihtsalt valida A-le lähim koht, vaatab ta seda, mille summa on tõenäoliselt kõige väiksem. Ta leiab selle kogusumma, lisades maksumuse eeldatavale järelejäänud vahemaale. Nii saab ta vaadata ainult selles suunas, kus asjad tõenäoliselt paremaks lähevad. See on okei, kui arvamine ei ole täiuslik, kuid isegi lihtne halb arvamine võib programmi palju kiiremini käima panna. Kui te püüate leida teed kahe koha vahel reaalses maailmas, on hea arvamine lihtsalt nende vaheline kaugus sirgjoonel. Tegelik tee üle teede on pikem, kuid see laseb programmil seda ära arvata ja ta ei lähe vales suunas.
Matemaatika- või arvutiteaduse kirjanduses on see arvamine sageli koha funktsioon ja seda nimetatakse heuristikaks. Iga koht on tipp ja iga tee kahe koha vahel on serv. Need on sõnad graafiteooriast.
