Czym jest dopuszczalna heurystyka (admissible heuristic)?
Dopuszczalna heurystyka to funkcja estymująca koszt dotarcia z danego stanu do celu w taki sposób, aby nigdy nie przeceniała rzeczywistego kosztu. Formalnie oznacza to, że dla każdego węzła n wartość heurystyki h(n) jest mniejsza lub równa najmniejszemu możliwemu kosztowi ścieżki prowadzącej z n do stanu docelowego. Własność ta zapewnia algorytmom opartym na przeszukiwaniu informowanym, takim jak A*, możliwość znalezienia rozwiązania najtańszego pod względem zdefiniowanej funkcji kosztu.
Jak dokładnie działa dopuszczalna heurystyka
Podczas działania algorytmu A* całkowity koszt ścieżki oszacowany dla węzła n wyraża się równaniem f(n) = g(n) + h(n), gdzie g(n) jest kosztem już przebytej trasy, a h(n) estymuje pozostały dystans. Jeśli h(n) jest dopuszczalna, wówczas f(n) nigdy nie przewyższa faktycznego minimalnego kosztu dotarcia do celu. Algorytm może dzięki temu bezpiecznie eliminować z dalszej analizy ścieżki o wyższej wartości f(n), mając pewność, że nie pominie rozwiązania optymalnego. Im bliżej rzeczywistego kosztu leży estymacja, tym mniej stanów trzeba odwiedzić, a więc tym szybciej uzyskuje się wynik.
Kontekst historyczny
Pojęcie dopuszczalnej heurystyki zyskało na znaczeniu w 1968 roku, kiedy to Peter Hart, Nils Nilsson i Bertram Raphael z Stanford Research Institute opisali algorytm A* w pracy „A Formal Basis for the Heuristic Determination of Minimum Cost Paths”. Autorzy wykazali, że warunek dopuszczalności heurystyki wystarcza do zagwarantowania optymalności znajdowanego rozwiązania. Od tamtej pory kryterium to stało się kamieniem węgielnym w badaniach nad planowaniem i przeszukiwaniem grafów.
Zastosowania w praktyce
Dopuszczalne heurystyki są wykorzystywane w planowaniu tras robotów mobilnych, wytyczaniu najkrótszych dróg w systemach nawigacji GPS, rozwiązywaniu łamigłówek logicznych (np. układanka 15-puzzle) oraz w generowaniu drzew ruchów w grach komputerowych. Przykładowo w nawigacji samochodowej funkcja heurystyczna bazuje często na odległości w linii prostej pomiędzy skrzyżowaniami. Jest to estymacja, która nigdy nie przeszacuje długości trasy prowadzącej drogami, dzięki czemu algorytm posiada gwarancję wyboru trasy najkrótszej pod względem czasu lub dystansu.
Zalety i ograniczenia
Największą korzyścią wynikającą z dopuszczalności jest pewność optymalności otrzymanego rozwiązania. W porównaniu z metodami nieinformowanymi, takimi jak przeszukiwanie BFS, heurystyka przyspiesza proces, zmniejszając liczbę eksplorowanych stanów. Jednocześnie nadmiernie zachowawcze estymacje – czyli zbyt niskie wartości h(n) – mogą prowadzić do eksplozji przestrzeni stanów porównywalnej z algorytmami pozbawionymi wiedzy dodatkowej. Aby zachować zarówno szybkość, jak i dokładność, projektanci starają się, by dopuszczalna heurystyka była możliwie dobrze dopasowana do specyfiki problemu.
Na co uważać?
Przy konstrukcji heurystyki należy upewnić się, że jej każda wartość spełnia warunek niedoszacowania. Naruszenie tej reguły grozi utratą gwarancji optymalności lub nawet poprawności rozwiązania. W praktyce problemem bywa również koszt obliczeniowy samej heurystyki: zbyt złożona funkcja potrafi wydłużyć pojedyncze kroki algorytmu do tego stopnia, że całkowity czas wykonania przestaje być korzystny. Optymalna strategia to kompromis pomiędzy dokładnością estymacji a jej kosztami obliczeniowymi.
Dodatkowe źródła
Szczegółową analizę właściwości heurystyk dopuszczalnych można znaleźć w oryginalnym artykule Harta, Nilssona i Raphaela dostępnym w repozytorium PDF. Rozszerzone omówienie pojawia się także w klasycznym podręczniku “Artificial Intelligence: A Modern Approach” Russella i Norviga. Ciekawą dyskusję na temat projektowania heurystyk dla zagadnień kombinatorycznych zawiera opracowanie opublikowane na arXiv. Definicję skrótową i przykłady znajdziesz również na Wikipedii.
