A* nie szuka wszędzie — próbuje zgadnąć, gdzie warto szukać
Algorytm A* znajduje ścieżki w grafie, łącząc dwa rodzaje informacji: koszt drogi już przebytej oraz heurystyczne oszacowanie kosztu pozostałego do celu. Dzięki temu nie musi rozwijać w równym stopniu wszystkich kierunków, lecz może skupić pracę tam, gdzie obiecująco wygląda suma „ile już kosztowało” i „ile prawdopodobnie jeszcze zostało”. Klucz tkwi w jakości heurystyki. Jeżeli dla problemu najkrótszej ścieżki nie zawyża ona rzeczywistego kosztu do celu, A* może zachować gwarancję znalezienia rozwiązania minimalnego przy odpowiednich założeniach, jednocześnie często badając znacznie mniej stanów niż wyszukiwanie pozbawione takiej wskazówki.
Dwie liczby zamiast jednej
W zwykłym przeszukiwaniu grafu można kierować się wyłącznie kosztem drogi, którą już przebyto. A* dodaje drugi składnik: ocenę tego, jak daleko prawdopodobnie pozostało do celu. Dla węzła n zapisuje się to często jako f(n)=g(n)+h(n), gdzie g(n) oznacza znany koszt dojścia od startu do n, a h(n) jest heurystycznym oszacowaniem kosztu z n do celu. Algorytm rozwija w pierwszej kolejności węzły o obiecującej wartości f.
To pozornie niewielka zmiana. Jej skutkiem jest jednak możliwość wykorzystania wiedzy specyficznej dla problemu. W wyszukiwaniu trasy na mapie heurystyką może być np. odległość geometryczna do celu, o ile jest dobrana tak, aby spełniała potrzebne własności. W przestrzeni układanki może nią być miara tego, jak daleko elementy są od położenia docelowego. Algorytm nie „wie”, którędy prowadzi najlepsza droga; dostaje jedynie wskazówkę, które części przestrzeni wydają się bardziej obiecujące.
Heurystyka ma pomagać, ale nie może oszukiwać
Oryginalna praca Petera Harta, Nilsa Nilssona i Bertrama Raphaela z 1968 roku zbudowała formalne podstawy takiego przeszukiwania i nazwała algorytm A*. Jednym z kluczowych warunków jest dopuszczalność heurystyki: h(n) ma być dolnym oszacowaniem rzeczywistego minimalnego kosztu z n do celu, czyli nie powinna go zawyżać. W późniejszej korekcie autorzy precyzowali również warunki związane z własnością spójności heurystyki i twierdzeniami o optymalności sposobu rozwijania węzłów.
Intuicja jest prosta. Jeśli heurystyka jest zbyt optymistyczna, A* może wykonać więcej pracy, ale nie zostaje przez nią skłoniony do odrzucenia prawdziwie najlepszej drogi. Jeśli natomiast pozwolimy heurystyce zawyżać koszty bez odpowiedniej kontroli, możemy uzyskać szybsze wyszukiwanie kosztem gwarancji optymalnego wyniku. Dlatego „dobry skrót myślowy” w algorytmie nie oznacza dowolnego zgadywania.
Co się dzieje, gdy heurystyka jest słaba
A* pokazuje ciekawy ciąg pomiędzy wyszukiwaniem niemal ślepym a bardzo dobrze ukierunkowanym. Jeśli h(n)=0 dla każdego węzła, funkcja f redukuje się do samego g i algorytm zachowuje się jak wyszukiwanie według dotychczasowego kosztu, bliskie algorytmowi Dijkstry dla odpowiednich wag. Gdy heurystyka trafnie przybliża pozostały koszt, kolejka priorytetowa kieruje obliczenia ku znacznie mniejszej części grafu.
Nie oznacza to jednak, że A* zawsze odwiedzi mało węzłów. W skomplikowanej przestrzeni, przy słabej heurystyce albo przy wielu niemal równie dobrych trasach, liczba rozważanych stanów nadal może być ogromna. Dochodzi też koszt pamięci: klasyczne A* przechowuje informacje o wielu odkrytych stanach. W praktycznych systemach planowania stosuje się dlatego różne odmiany i techniki ograniczania pamięci. Sednem pozostaje ten sam pomysł: użyć wiedzy o celu, aby zdecydować, gdzie najpierw inwestować czas obliczeń.
Dlaczego to więcej niż „algorytm do GPS-u”
A* jest często kojarzony z nawigacją, ale jego znaczenie jest szersze. Formalizuje ogólną ideę przeszukiwania przestrzeni stanów z przewodnikiem. Stanem może być skrzyżowanie dróg, pozycja robota, konfiguracja układanki albo częściowe rozwiązanie zadania. Krawędzie opisują dopuszczalne przejścia, a heurystyka wykorzystuje dodatkową wiedzę, której sam abstrakcyjny graf nie zawiera.
To szczególnie dobry przykład granicy między „dokładnym” a „heurystycznym” myśleniem w informatyce. Heurystyka może być przybliżeniem, ale cały algorytm nie musi przez to być niedokładny. Przy właściwych warunkach przybliżona informacja służy wyłącznie do ustalania kolejności pracy, podczas gdy matematyczne reguły algorytmu chronią poprawność wyniku. Dzięki temu zgadywanie staje się nie zamiennikiem dowodu, lecz narzędziem do szybszego znalezienia rozwiązania, którego jakość nadal można zagwarantować.
Heurystyka może płynnie zmieniać charakter wyszukiwania
A* można traktować jako rodzinę zachowań zależnych od jakości heurystyki. Jeśli h(n)=0 dla każdego węzła, priorytet f(n)=g(n)+h(n) sprowadza się do samego kosztu dojścia g(n), czyli do wyszukiwania w stylu Dijkstry dla nieujemnych kosztów. Im więcej bezpiecznej informacji o pozostałym dystansie wnosi h, tym mocniej algorytm potrafi skierować uwagę ku celowi. Gdybyśmy dysponowali idealną wartością rzeczywistego kosztu do celu, heurystyka zawierałaby niemal całą informację potrzebną do wyboru obiecujących stanów. W praktyce takiej wartości właśnie szukamy, dlatego heurystyka jest tańszym oszacowaniem. Cała sztuka polega na uzyskaniu informacji wystarczająco użytecznej, ale na tyle taniej i odpowiednio ograniczonej, by nie zniszczyć gwarancji optymalności.