Algorytm A*
A* to zestaw kroków (algorytm), które komputery mogą wykorzystać do określenia, jak szybko dostać się gdzieś pomiędzy dwoma miejscami. Jeśli masz listę lokalizacji i wiesz, jak trudno jest dostać się z jednej prosto do drugiej, użycie A* może szybko wskazać najszybszą drogę. Jest to algorytm podobny do algorytmu Dijkstry, ale zgaduje tak, że nie spędza tak dużo czasu próbując powolnych dróg. Jest to dobra seria kroków, jeśli chcesz tylko ścieżkę między dwoma miejscami. Jeśli zamierzasz poprosić o wiele ścieżek z tej samej mapy, to istnieją szybsze sposoby, które znajdują wszystkie odpowiedzi naraz, takie jak algorytm Floyda-Warshalla. A* nie zadziała, jeśli chcesz odwiedzić kilka miejsc podczas jednej podróży (Travelling salesman problem).
Kroki
A* najpierw potrzebuje listy wszystkich miejsc, do których można się udać, a następnie listy odległości między nimi. Następnie wskaże Ci najszybszy sposób dotarcia z miejsca A do miejsca Z.
Dla przykładu, powiemy, że A jest połączone z miejscami B i C, a B i C są połączone z D i E. D i E są połączone z Z. Istnieją 4 możliwe sposoby przejścia z A do Z. Można przejść A-B-D-Z, A-C-D-Z, A-B-E-Z lub A-C-E-Z. Komputer używający A* najpierw sprawdza, jak trudno jest dostać się z A do B i z A do C. Jest to "koszt" tych miejsc. Koszt danego miejsca oznacza, jak trudno jest dostać się z punktu A do tego miejsca. Po zapisaniu obu kosztów komputer sprawdza, jak trudno jest dostać się z B do D, i dodaje to do kosztu B. Zapisuje to jako koszt D. Zapisuje to jako koszt D. Następnie komputer sprawdza, jak trudno jest dostać się z C do D, i dodaje to do kosztu C. Jest to inny koszt dla D. Jest to inny koszt dla D i jeśli jest on niższy niż ten, który już ma, to zastąpi go starym. Komputer chce znać tylko najlepszą ścieżkę, więc ignoruje ścieżkę o wyższym koszcie. Zapamiętuje tylko jedną z A-B-D i A-C-D, w zależności od tego, która jest szybsza.
Komputer idzie dalej i znajduje najszybszy sposób dotarcia do E. W końcu przechodzi z D do Z i znajduje koszt, oraz z E do Z i znajduje koszt. Dostaje ostateczny koszt dla Z, i to jest najmniejszy koszt, jaki może uzyskać. Teraz komputer wie, która droga jest najszybsza, i ma odpowiedź. Komputer może wykonać podobną serię kroków, ale z o wiele większą liczbą miejsc. Za każdym razem będzie patrzył na miejsce, które jest najbliżej A, i będzie sumował koszty dla sąsiadów tego miejsca.
Ludzie nazywają powyższą serię kroków algorytmem Dijkstry. Algorytm Dijkstry może być powolny, ponieważ będzie sprawdzał wiele miejsc, które mogą być w złym kierunku od Z. Jeśli zapytasz komputer, jak dostać się z jednego miasta do innego, algorytm Dijkstry może skończyć się szukaniem w innym stanie.
A* rozwiązuje ten problem. A* pozwala podać komputerowi przypuszczenie, jak daleko będzie z każdego miejsca do końca. Komputer może użyć tego przypuszczenia, aby określić w przybliżeniu, jak daleko trzeba będzie dojść z danego miejsca do Z. Zamiast wybierać miejsce najbliższe A, aby je sprawdzić, komputer sprawdzi to, które prawdopodobnie będzie miało najniższą sumę. Znajduje tę sumę przez dodanie kosztu do oczekiwanej odległości w lewo. W ten sposób można patrzeć tylko w kierunku, w którym prawdopodobnie będzie lepiej. Nie ma problemu, jeśli zgadywanie nie jest idealne, ale nawet proste złe zgadywanie może sprawić, że program będzie działał o wiele szybciej. Jeśli próbujesz znaleźć ścieżkę między dwoma miejscami w prawdziwym świecie, dobrym przypuszczeniem jest po prostu odległość między nimi w linii prostej. Prawdziwa ścieżka po drogach będzie dłuższa, ale dzięki temu program może ją odgadnąć i nie pójdzie w złym kierunku.
W literaturze matematycznej lub informatycznej, to przypuszczenie jest często funkcją miejsca i jest nazywane heurystyką. Każde miejsce jest wierzchołkiem, a każda ścieżka między dwoma miejscami jest krawędzią. Są to słowa z teorii grafów.
