Jakie są różnice między wyszukiwarką A * a chciwym wyszukiwaniem w pierwszej kolejności?

Oba algorytmy należą do kategorii „best-first search” algorytmy, czyli algorytmy, które mogą wykorzystywać zarówno wiedzę zdobytą do tej pory podczas eksploracji przestrzeni poszukiwań, oznaczone $ g (n) $ , oraz funkcję heurystyczną oznaczoną przez $ h (n) $ , która szacuje odległość do węzła celu dla każdego węzła $ n $ w przestrzeni wyszukiwania (często przedstawiane jako wykres).

Każdy z tych algorytmów wyszukiwania definiuje „funkcję oceny” dla każdego węzła $ n $ na wykresie (lub przestrzeni wyszukiwania), oznaczoną przez $ f (n) $ . Ta funkcja oceny służy do określenia, który węzeł podczas wyszukiwania jest najpierw „rozszerzany”, czyli który węzeł jest najpierw usuwany z „fringe” (lub „frontier”, lub „obramowanie”) , aby „odwiedzić” swoje dzieci. Ogólnie rzecz biorąc, różnica między algorytmami z kategorii „najpierw najlepsze” dotyczy definicji funkcji oceny $ f (n) $ .

W przypadku zachłannego algorytmu BFS , funkcją oceny jest $ f (n) = h (n) $ , czyli chciwy algorytm BFS najpierw rozszerza węzeł, którego szacowana odległość do celu jest najmniejsza. Dlatego chciwy BFS nie korzysta z „wiedzy z przeszłości”, tj. $ g (n) $ . Stąd jego konotacja „chciwy”. Ogólnie rzecz biorąc, zachłanny algorytm BST jest niekompletny , co oznacza, że zawsze istnieje ryzyko wyboru ścieżki, która nie doprowadzić do celu. W chciwym algorytmie BFS wszystkie węzły na granicy (lub na skraju lub granicy) są przechowywane w pamięci, a węzły, które zostały już rozszerzone, nie muszą być przechowywane w pamięci i dlatego mogą zostać odrzucone. Ogólnie rzecz biorąc, chciwy BFS jest również nieoptymalny , to znaczy znaleziona ścieżka może nie być optymalna. Ogólnie złożoność czasowa to $ \ mathcal {O} (b ^ m) $ , gdzie $ b $ to (maksymalny) współczynnik rozgałęzienia, a $ m $ to maksymalna głębokość drzewa wyszukiwania. Złożoność przestrzeni jest proporcjonalna do liczby węzłów na skraju i długości znalezionej ścieżki.

W przypadku A * algorytm , funkcja oceny to $ f (n) = g (n) + h (n) $ , gdzie $ h $ to dopuszczalna funkcja heurystyczna . „Gwiazda”, często oznaczana gwiazdką, *, odnosi się do faktu, że A * używa dopuszczalnej funkcji heurystycznej, co zasadniczo oznacza, że A * jest optymalna , to znaczy zawsze znajduje optymalną ścieżkę między węzłem początkowym a węzłem docelowym. Znak * jest również zakończony (chyba że w przestrzeni wyszukiwania jest nieskończenie wiele węzłów do zbadania). Złożoność czasowa to $ \ mathcal {O} (b ^ m) $ . Jednak A * musi zachować wszystkie węzły w pamięci podczas wyszukiwania, a nie tylko te na marginesie, ponieważ A * zasadniczo przeprowadza „wyszukiwanie wyczerpujące” (które jest „poinformowane” w tym sensie, że używa funkcji heurystycznej ).

Podsumowując, chciwy BFS nie jest kompletny, nie jest optymalny, ma złożoność czasową $ \ mathcal {O} (b ^ m) $ i złożoność przestrzeni, która może być wielomianowa. A * jest kompletne, optymalne i ma złożoność czasową i przestrzenną $ \ mathcal {O} (b ^ m) $ . Ogólnie rzecz biorąc, A * zużywa więcej pamięci niż chciwy BFS. * Staje się niepraktyczne, gdy przestrzeń wyszukiwania jest ogromna. Jednak A * gwarantuje również, że znaleziona ścieżka między węzłem początkowym a węzłem docelowym jest optymalna i że algorytm ostatecznie się zakończy. Z drugiej strony Greedy BFS zużywa mniej pamięci, ale nie zapewnia gwarancji optymalności i kompletności A *. Zatem, który algorytm jest „najlepszy”, zależy od kontekstu, ale oba są „najlepszymi” – pierwszymi wyszukiwaniami.

Uwaga: w praktyce nie możesz używać żadnego z tych algorytmów: możesz np. użyj zamiast tego IDA * .

Komentarze

• Komentarze nie są przeznaczone rozszerzona dyskusja; ta rozmowa została przeniesiona do czatu .

Zgodnie z książką Sztuczna inteligencja: A Modern Approach (wydanie trzecie), Stuart Russel i Peter Norvig, w szczególności sekcja 3.5.1 Chciwe wyszukiwanie w pierwszej kolejności (s. 92)

Chciwe wyszukiwanie w pierwszej kolejności próbuje rozszerzyć węzeł, który jest najbliżej celu, na tej podstawie, że prawdopodobnie szybko doprowadzi do rozwiązania. W związku z tym ocenia węzły, używając tylko funkcji heurystycznej; to znaczy $ f (n) = h (n) $ .

W tym W tej samej sekcji autorzy podają przykład, który pokazuje, że chciwe wyszukiwanie w pierwszej kolejności nie jest ani optymalne, ani kompletne.

W sekcji 3.5.2 A * wyszukiwanie: Minimalizacja całkowitego szacowanego kosztu rozwiązania tej samej książki (s. 93), stwierdza

A * wyszukiwanie ocenia węzły, łącząc $ g (n) $ , koszt dotarcia do węzła i $ h (n) $ , koszt przejścia od węzła do celu $$ f (n) = g (n) + h (n). $$

Ponieważ $ g (n) $ podaje koszt ścieżki od węzła początkowego do węzła $ n $ , a $ h (n) $ to szacunkowy koszt najtańszej ścieżki z $ n $ do celu, mamy $ f (n) $ = szacunkowy koszt najtańszego rozwiązania za pomocą $ n $ .

Zatem jeśli próbujemy znaleźć najtańsze rozwiązanie, rozsądną rzeczą do wypróbowania w pierwszej kolejności jest węzeł o najniższej wartości $ g (n) + h (n) $ . Okazuje się, że ta strategia jest więcej niż tylko rozsądna: pod warunkiem, że funkcja heurystyczna $ h (n) $ spełnia określone warunki, wyszukiwanie A * jest zarówno kompletne, jak i optymalne. Algorytm jest taki sam, jak w przypadku wyszukiwania według jednolitych kosztów, z tym wyjątkiem, że A * używa $ g + h $ zamiast $ g $

To, co powiedziałeś, nie jest całkowicie błędne, ale algorytm A * staje się optymalny i kompletny, jeśli funkcja heurystyczna h jest dopuszczalna, co oznacza, że funkcja ta nigdy nie przeszacowuje kosztu osiągnięcia celu. W takim przypadku algorytm A * jest o wiele lepszy niż algorytm chciwego wyszukiwania.

Komentarze

• kochanie, czy możesz rozwinąć swoją odpowiedź. Przykro mi to mówić, ale nie rozumiem.
• @IramShah – TemmanRafk mówi o dowodzie, że A * jest zarówno optymalne, jak i kompletne. Aby to zrobić, jest pokazane ze względu na nierówność trójkątów, że heurystyka szacująca odległość pozostałą do celu nie jest przeszacowana. Aby zobaczyć pełniejsze wyjaśnienie, zobacz en.wikipedia.org/wiki/Admiable_heuri stic