A* meklēšanas algoritms
A* ir soļu kopums (algoritms), ko datori var izmantot, lai noteiktu, kā ātri nokļūt no vienas vietas uz otru. Ja jums ir saraksts ar vietām un to, cik grūti ir nokļūt no vienas vietas uz otru, izmantojot A*, jūs varat ātri atrast ātrāko ceļu. Tas ir saistīts ar Dijkstras algoritmu, bet veic gudrus minējumus, lai tas netērētu tik daudz laika, mēģinot atrast lēno ceļu. Tā ir laba soļu sērija, ja vēlaties tikai ceļu starp divām vietām. Ja vēlaties uzzināt daudzus ceļus no vienas kartes, tad ir ātrāki veidi, kas atrod visas atbildes uzreiz, piemēram, Floida-Varšala algoritms. A* nedarbosies, ja vienā ceļojumā vēlaties apmeklēt vairākas vietas (ceļojošā pārdevēja problēma).
Soļi
A* vispirms ir nepieciešams saraksts ar visām vietām, uz kurām var aizbraukt, un pēc tam - saraksts, cik tālu ir ceļš starp tām. Pēc tam tas jums pateiks ātrāko ceļu, kā nokļūt no vietas A uz vietu Z.
Piemēram, teiksim, ka A ir savienots ar vietām B un C, un B un C ir savienoti ar D un E. D un E ir savienoti ar Z. Ir četri iespējamie ceļi, kā nokļūt no A uz Z. Jūs varat doties A-B-D-Z, A-C-D-Z, A-B-E-Z vai A-C-E-Z. Dators, kas izmanto A*, vispirms aplūko, cik grūti ir nokļūt no A uz B un no A uz C. Tās ir šo vietu "izmaksas". Vietas izmaksas nozīmē, cik grūti ir nokļūt no A uz šo vietu. Pēc abu izmaksu pierakstīšanas dators noskaidro, cik grūti ir nokļūt no B uz D, un pieskaita to B izmaksām. Tas pieraksta to kā D izmaksas. Tad dators paskatās, cik grūti ir nokļūt no C uz D, un pieskaita to C izmaksām. Tās ir citas D izmaksas, un, ja tās ir mazākas par jau esošajām, tas nomaina vecās izmaksas. Dators vēlas zināt tikai labāko ceļu, tāpēc tas ignorē ceļu ar lielākām izmaksām. Tas atcerēsies tikai vienu no A-B-D un A-C-D, atkarībā no tā, kurš ir ātrāks.
Dators dodas tālāk un atrod ātrāko ceļu uz E. Visbeidzot, tas dodas no D uz Z un atrod izmaksas, un no E uz Z un atrod izmaksas. Tas iegūst galīgās Z izmaksas, un tās ir vismazākās izmaksas, ko tas var iegūt. Tagad dators zina, kurš ceļš ir ātrākais, un tam ir atbilde. Dators var veikt līdzīgu soļu virkni, bet ar daudz vairāk vietām. Katru reizi tas apskatīs vietu, kas ir vistuvāk A, un saskaitīs izmaksas šīs vietas kaimiņiem.
Iepriekš minēto soļu virkni sauc par Dijkstras algoritmu. Dijkstras algoritms var būt lēns, jo tas aplūko daudzas vietas, kas no Z var atrasties nepareizā virzienā. Ja datoram jautātu, kā nokļūt no vienas pilsētas uz tuvējo pilsētu, Dijkstras algoritms varētu beigties ar meklēšanu citā valstī.
A* atrisina šo problēmu. A* ļauj datoram norādīt, cik tālu būs no katras vietas līdz galam. Dators var izmantot šo minējumu, lai aptuveni noteiktu, cik tālu būs jānoiet no konkrētas vietas līdz Z. Tā vietā, lai izvēlētos tikai vietu, kas ir vistuvāk A, dators apskatīs to, kurā, iespējams, būs mazākais kopējais attālums. Šo kopsummu tā atrod, pieskaitot izmaksas paredzamajam atlikušajam attālumam. Šādā veidā tas var meklēt tikai virzienā, kurā situācija, iespējams, uzlabosies. Nekas, ja minējums nav perfekts, taču pat vienkāršs slikts minējums var padarīt programmu daudz ātrāku. Ja mēģināt atrast ceļu starp divām vietām reālajā pasaulē, labs minējums ir tikai attālums starp tām taisnā līnijā. Reālais ceļš pa ceļiem būs garāks, bet tas ļauj programmai to uzminēt, un tā neies nepareizā virzienā.
Matemātikas vai datorzinātņu literatūrā šis minējums bieži vien ir vietas funkcija, un to sauc par heiristiku. Katra vieta ir virsotne, un katrs ceļš starp divām vietām ir mala. Tie ir vārdi no grafu teorijas.
