Vyhľadávací algoritmus A*
A* je súbor krokov (algoritmus), ktorý môžu počítače použiť na zistenie, ako sa rýchlo dostať medzi dvoma miestami. Ak máte zoznam miest a ako ťažko sa dostanete z jedného priamo na druhé, pomocou A* môžete rýchlo zistiť najrýchlejšiu cestu. Je príbuzný Dijkstrovmu algoritmu, ale robí inteligentné odhady, takže netrávi toľko času skúšaním pomalých ciest. Je to dobrá séria krokov, ak chcete len cestu medzi dvoma miestami. Ak sa budete pýtať na veľa ciest z tej istej mapy, potom existujú rýchlejšie spôsoby, ktoré nájdu všetky odpovede naraz, ako napríklad Floyd-Warshallov algoritmus. A* nebude fungovať, ak chcete počas jednej cesty navštíviť niekoľko miest (problém obchodného cestujúceho).
Kroky
A* potrebuje najprv zoznam všetkých miest, na ktoré môžete ísť, a potom potrebuje zoznam, ako ďaleko je cesta medzi jednotlivými miestami. Potom vám povie najrýchlejšiu cestu z miesta A do miesta Z.
Ako príklad uvedieme, že A je spojené s miestami B a C a B a C sú spojené s miestami D a E. D a E sú spojené s miestom Z. Existujú 4 možné spôsoby, ako ísť z A do Z. Môžete ísť A-B-D-Z, A-C-D-Z, A-B-E-Z alebo A-C-E-Z. Počítač, ktorý používa A*, sa najprv pozrie, aké ťažké je dostať sa z A do B a z A do C. To sú "náklady" na tieto miesta. Náklady na miesto znamenajú, aké ťažké je dostať sa z A na toto miesto. Po zapísaní oboch nákladov sa počítač pozrie, aké ťažké je dostať sa z miesta B do miesta D, a pripočíta to k nákladom miesta B. Zapíše to ako náklady D. Potom sa počítač pozrie, aké ťažké je dostať sa z C do D, a pripočíta to k nákladom C. Toto sú iné náklady pre D, a ak sú menšie ako tie, ktoré už má, nahradí tie staré. Počítač chce poznať len najlepšiu cestu, takže cestu s vyššími nákladmi ignoruje. Zapamätá si len jednu z možností A-B-D a A-C-D, podľa toho, ktorá je rýchlejšia.
Počítač pokračuje ďalej a nájde najrýchlejšiu cestu do E. Nakoniec prejde z D do Z a nájde náklady a z E do Z a nájde náklady. Získa konečnú cenu pre Z, a to je najmenšia cena, ktorú môže získať. Teraz počítač vie, ktorá cesta je najrýchlejšia, a má odpoveď. Počítač môže urobiť podobnú sériu krokov, ale s oveľa oveľa väčším počtom miest. Zakaždým sa pozrie na miesto, ktoré je najbližšie k A, a sčíta náklady na susedné miesta tohto miesta.
Uvedenú sériu krokov ľudia nazývajú Dijkstrov algoritmus. Dijkstrov algoritmus môže byť pomalý, pretože sa pozrie na mnoho miest, ktoré môžu ísť nesprávnym smerom zo Z. Ak by ste sa spýtali počítača, ako sa dostať z jedného mesta do blízkeho, Dijkstrov algoritmus by mohol skončiť hľadaním v inom štáte.
A* tento problém rieši. A* umožňuje počítaču odhadnúť, ako ďaleko to bude z každého miesta na koniec. Počítač môže tento odhad použiť na to, aby približne určil, ako ďaleko bude trvať cesta z určitého miesta do miesta Z. Namiesto toho, aby si vybral len miesto, ktoré je najbližšie k miestu A, pozrie sa na to, ktoré bude mať pravdepodobne najnižší celkový súčet. Túto celkovú sumu zistí tak, že k očakávanej zostávajúcej vzdialenosti pripočíta náklady. Takto sa môže pozerať len smerom, kde sa situácia pravdepodobne zlepší. Nevadí, ak odhad nie je dokonalý, ale aj jednoduchý zlý odhad môže program urýchliť. Ak sa snažíte nájsť cestu medzi dvoma miestami v reálnom svete, dobrým odhadom je práve vzdialenosť medzi nimi po priamke. Skutočná cesta po cestách bude dlhšia, ale vďaka tomu ju program odhadne a nepôjde zlým smerom.
V matematickej alebo informatickej literatúre je tento odhad často funkciou miesta a nazýva sa heuristika. Každé miesto je vrchol a každá cesta medzi dvoma miestami je hrana. Ide o slová z teórie grafov.
