Vyhledávací algoritmus A*
A* je soubor kroků (algoritmus), který počítače používají k tomu, aby zjistily, jak se rychle dostat někam mezi dvěma místy. Pokud máte seznam míst a víte, jak obtížné je dostat se z jednoho přímo na druhé, pomocí A* můžete rychle zjistit nejrychlejší cestu. Je příbuzný Dijkstrovu algoritmu, ale provádí chytré odhady, takže netráví tolik času zkoušením pomalých cest. Je to dobrá série kroků, pokud chcete pouze cestu mezi dvěma místy. Pokud se hodláte ptát na mnoho cest z jedné mapy, pak existují rychlejší způsoby, které najdou všechny odpovědi najednou, jako například Floyd-Warshallův algoritmus. A* nebude fungovat, pokud chcete během jedné cesty navštívit několik míst (problém obchodního cestujícího).
Kroky
A* nejprve potřebuje seznam všech míst, kam se můžete dostat, a pak potřebuje seznam, jak daleko je cesta mezi jednotlivými místy. Pak vám řekne, jak se nejrychleji dostanete z místa A do místa Z.
Pro příklad řekneme, že A je spojeno s místy B a C a B a C jsou spojeny s D a E. D a E jsou spojeny se Z. Existují 4 možné způsoby, jak se dostat z A do Z. Můžete jít A-B-D-Z, A-C-D-Z, A-B-E-Z nebo A-C-E-Z. Počítač používající A* se nejprve podívá, jak obtížné je dostat se z A do B a z A do C. To jsou "náklady" pro tato místa. Náklady místa znamenají, jak obtížné je dostat se z místa A do tohoto místa. Po zapsání obou nákladů se počítač podívá, jak obtížné je dostat se z místa B do místa D, a přičte to k nákladům na místo B. To zapíše jako náklady na D. Pak se počítač podívá, jak obtížné je dostat se z místa C do místa D, a přičte to k nákladům místa C. To jsou jiné náklady pro D, a pokud jsou menší než ty, které už má, nahradí ty staré. Počítač chce znát pouze nejlepší cestu, takže cestu s vyššími náklady ignoruje. Zapamatuje si pouze jednu z cest A-B-D a A-C-D, podle toho, která je rychlejší.
Počítač pokračuje a najde nejrychlejší cestu do E. Nakonec se vydá z D do Z a najde náklady a z E do Z a najde náklady. Získá konečnou cenu pro Z, a to je nejmenší cena, kterou může získat. Nyní počítač ví, která cesta je nejrychlejší, a zná odpověď. Počítač může provést podobnou sérii kroků, ale s mnoha a mnoha dalšími místy. Pokaždé se podívá na místo, které je nejblíže k místu A, a sečte náklady na sousedy tohoto místa.
Lidově se výše uvedené sérii kroků říká Dijkstrův algoritmus. Dijkstrův algoritmus může být pomalý, protože se podívá na mnoho míst, která mohou jít špatným směrem ze Z. Pokud byste se počítače zeptali, jak se dostat z jednoho města do blízkého, Dijkstrův algoritmus by mohl skončit hledáním v jiném státě.
A* tento problém řeší. A* umožňuje počítači odhadnout, jak daleko to bude z každého místa na konec. Počítač může tento odhad použít k tomu, aby přibližně určil, jak daleko bude trvat cesta z určitého místa do místa Z. Místo toho, aby se podíval jen na místo, které je nejblíže k místu A, podívá se na to, které bude mít pravděpodobně nejnižší celkový součet. Tuto celkovou hodnotu zjistí tak, že k očekávané zbývající vzdálenosti přičte náklady. Tímto způsobem se může podívat pouze tím směrem, kde to bude pravděpodobně lepší. Nevadí, když odhad není dokonalý, ale i pouhý špatný odhad může program urychlit. Pokud se snažíte najít cestu mezi dvěma místy v reálném světě, je dobrým odhadem právě vzdálenost mezi nimi po přímce. Skutečná cesta přes silnice bude delší, ale díky tomu ji program odhadne a nepůjde špatným směrem.
V matematické nebo informatické literatuře je tento odhad často funkcí místa a nazývá se heuristika. Každé místo je vrchol a každá cesta mezi dvěma místy je hrana. Jedná se o slova z teorie grafů.
