Przejdź do treści
Wróć do wyników wyszukiwania

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

Rozmiar czcionki

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

1

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.

2

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.

3

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

  1. 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 DOI
    Skopiowano.
  2. Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.

    ISBN: 978-0-13-604259-4
    Skopiowano.