Algorytm wyszukiwania A*
- Autor metody
- Peter E. Hart, Nils J. Nilsson, and Bertram Raphael
- Rok
- 1968
- Typ
- algorithm
- Rodzina
- Graph Algorithms
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Algorytm wyszukiwania A*, opracowany przez Petera E. Harta, Nilsa J. Nilsona i Bertrama Raphaela w 1968 roku, jest optymalnym algorytmem znajdowania ścieżki, który łączy zalety algorytmu Dijkstry z kierownictwem heurystycznym.
Efektywnie znajduje najkrótszą ścieżkę, równoważąc rzeczywistą odległość od początku z szacowaną odległością do celu.
Intuicja stojąca za metodą
A* wykorzystuje funkcję oceny f(n) = g(n) + h(n), gdzie g(n) to rzeczywisty koszt od początku do węzła n, a h(n) to heurystyczne oszacowanie pozostałego kosztu do celu. Eksplorując węzły o najniższej wartości f(n), algorytm efektywnie zawęża przestrzeń poszukiwań w kierunku celu, zachowując optymalność, gdy heurystyka jest dopuszczalna (nigdy nie przeszacowuje). To sprawia, że A* jest znacznie szybszy niż metody niekierowanego wyszukiwania, jednocześnie gwarantując znalezienie optymalnej ścieżki.
Historia
Hart, Nilsson i Raphael opublikowali A* w 1968 roku, pokazując, że dodanie informacji heurystycznych do algorytmu Dijkstry może dramatycznie poprawić efektywność wyszukiwania przy zachowaniu optymalności. Algorytm stał się podstawą sztucznej inteligencji i badań operacyjnych. Kolejne rozwinięcia obejmują dwukierunkowy A*, IDA* (iteracyjne pogłębianie) i różne ulepszenia heurystyczne. A* pozostaje standardowym wyborem do znajdowania ścieżek w nowoczesnych silnikach gier i systemach robotycznych.
Kiedy stosować
Zastosuj A*, gdy potrzebujesz znaleźć optymalne ścieżki w grafach, dla których dostępna jest dobra funkcja heurystyczna. Jest szczególnie skuteczny w znajdowaniu ścieżek w grach, robotyce i planowaniu tras, gdzie wyszukiwanie kierowane może znacznie zmniejszyć obliczenia. Używaj go, gdy liczy się szybkość, ale wymagana jest optymalność. W przypadkach bez wiarygodnej heurystyki użyj zamiast tego algorytmu Dijkstry.
Ograniczenia i uwagi
- Optymalność zależy od dopuszczalności funkcji heurystycznej
- Wydajność znacznie spada przy słabych lub niedopuszczalnych heurystykach
- Zużycie pamięci może być znaczne w dużych przestrzeniach poszukiwań (utrzymuje otwarty i zamknięty zbiór)
- Wymaga jawnej wiedzy dziedzinowej do projektowania dobrych funkcji heurystycznych
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Optymalne znajdowanie ścieżek, gdy heurystyka jest dopuszczalna
- Znacznie szybszy niż algorytm Dijkstry lub przeszukiwanie wszerz, gdy dostępne są dobre heurystyki
- Elastyczny: działa z każdą dopuszczalną funkcją heurystyczną
- Dobrze nadaje się do problemów znajdowania ścieżek z jednym celem
- Obszerne walidacje w świecie rzeczywistym w grach, robotyce i systemach nawigacyjnych
Zastosowania
- Znajdowanie ścieżek w grach wideo: nawigacja NPC w czasie rzeczywistym w dynamicznych środowiskach gier
- Planowanie ruchu robotów: optymalne planowanie ścieżek dla robotów autonomicznych unikających przeszkód
- Nawigacja GPS: obliczanie efektywnych tras z uwzględnieniem sieci drogowej i ruchu
- Rozwiązywanie łamigłówek: znajdowanie optymalnych rozwiązań w problemach kombinatorycznych, takich jak łamigłówka 15
- Routing sieciowy: określanie efektywnych tras pakietów z heurystykami jakości połączeń
- Bioinformatyka: wyszukiwania w dopasowywaniu sekwencji i przewidywaniu struktury białek
Jak to działa
Jak to działa
Utwórz otwarty zbiór z węzłem początkowym, ustaw jego wartość g (koszt od początku) na zero i oblicz jego wartość h za pomocą funkcji heurystycznej.
Wybierz węzeł o najniższej wartości f ze zbioru otwartego, oblicz wartości f dla jego nieodwiedzonych sąsiadów i dodaj obiecujących sąsiadów do zbioru otwartego.
Kontynuuj rozszerzanie węzłów, aż cel zostanie osiągnięty z najniższą wartością f, co gwarantuje optymalną ścieżkę; odtwórz ścieżkę, śledząc wskaźniki rodziców.
Częste pułapki
- Użycie niedopuszczalnej heurystyki, która przeszacowuje koszty, prowadząc do suboptymalnych ścieżek
- Wybór heurystyki, która jest zbyt prosta lub niezwiązana z problemem, zmniejszając efektywność wyszukiwania
- Nieefektywna implementacja otwartego zbioru (powinna używać kolejki priorytetowej), powodująca powolny wybór węzła
Najczęściej zadawane pytania
Czym jest dopuszczalna heurystyka i dlaczego ma znaczenie?
Dopuszczalna heurystyka nigdy nie przeszacowuje rzeczywistego kosztu do celu. Ta właściwość gwarantuje, że A* znajduje optymalną ścieżkę. Jeśli heurystyka przeszacowuje, A* może pominąć krótsze ścieżki i zwrócić suboptymalne rozwiązania.
Jak zaprojektować dobrą heurystykę dla problemu?
Dobre heurystyki opierają się na wiedzy dziedzinowej i strukturze problemu. W przypadku znajdowania ścieżek w siatce dobrze działa odległość Manhattan lub euklidesowa. W bardziej złożonych problemach rozważ złagodzenie ograniczeń lub użycie baz danych wzorców do obliczenia dopuszczalnych heurystyk.
Jaka jest różnica między algorytmem A* a algorytmem Dijkstry?
Oba znajdują optymalne ścieżki, ale A* wykorzystuje heurystykę do priorytetyzacji eksploracji w kierunku celu, co czyni go znacznie szybszym, gdy dostępna jest dobra heurystyka. Dijkstra eksploruje równomiernie we wszystkich kierunkach i jest bezpieczniejszy, gdy heurystyki są niewiarygodne.
Czy A* może zagwarantować znalezienie najkrótszej ścieżki?
Tak, A* gwarantuje najkrótszą ścieżkę, gdy heurystyka jest dopuszczalna (nigdy nie przeszacowuje rzeczywistego kosztu). Przy niedopuszczalnych heurystykach optymalność nie jest gwarantowana.
Pokrewne metody
Źródła
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
Otwórz odnośnik DOISkopiowano.Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.
ISBN: 978-0-13-604259-4Skopiowano.