Najlepsze pierwsze wyszukiwanie

Najlepsze pierwsze wyszukiwanie to klasa algorytmów wyszukiwania , które eksplorują graf , rozszerzając najbardziej obiecujący węzeł wybrany zgodnie z określoną regułą.

Judea Pearl opisał najlepsze pierwsze wyszukiwanie jako oszacowanie obietnicy węzła n za pomocą „heurystycznej funkcji oceny która ogólnie może zależeć od opisu n , opisu węzła fa celu, informacje zebrane podczas wyszukiwania do tego momentu, a co najważniejsze, na wszelkiej dodatkowej wiedzy na temat dziedziny problemu”.

Niektórzy autorzy używali „najlepszego pierwszego wyszukiwania”, aby odnieść się konkretnie do wyszukiwania za pomocą heurystyki, która próbuje przewidzieć, jak blisko jest koniec ścieżki do rozwiązania (lub celu), tak aby ścieżki, które są oceniane jako bliższe rozwiązanie (lub cel) są rozszerzane jako pierwsze. Ten specyficzny typ wyszukiwania nazywany jest zachłannym wyszukiwaniem najpierw najlepiej lub czystym wyszukiwaniem heurystycznym .

Efektywny wybór obecnie najlepszego kandydata do rozszerzenia jest zwykle realizowany przy użyciu kolejki priorytetowej .

Algorytm wyszukiwania A* jest przykładem algorytmu wyszukiwania najlepiej najpierw, podobnie jak algorytm B* . Algorytmy „najpierw najlepszy” są często używane do znajdowania ścieżki w wyszukiwaniu kombinatorycznym . Ani A*, ani B* nie są zachłannym wyszukiwaniem typu „najlepiej najpierw”, ponieważ uwzględniają odległość od początku oprócz szacowanej odległości do celu.

Chciwy BFS

Korzystając z algorytmu zachłannego , rozwiń pierwszego następcę rodzica. Po wygenerowaniu następcy:

  1. Jeśli heurystyka następnika jest lepsza niż jego rodzica, następnik jest ustawiany na początku kolejki (a rodzic jest ponownie wstawiany bezpośrednio za nim), a pętla uruchamia się ponownie.
  2. W przeciwnym razie następnik jest wstawiany do kolejki (w miejscu określonym przez jego wartość heurystyczną). Procedura oceni pozostałych spadkobierców (jeśli istnieją) rodzica.

Poniżej znajduje się pseudokodowy przykład tego algorytmu, gdzie kolejka reprezentuje kolejkę priorytetową, która porządkuje węzły na podstawie ich heurystycznych odległości od celu. Ta implementacja śledzi odwiedzane węzły i dlatego może być używana do grafów nieskierowanych . Można go zmodyfikować, aby pobrać ścieżkę. 

   procedura  GBS(start, cel)  to  : zaznacz początek jako odwiedzony dodaj początek do kolejki  dopóki  kolejka  nie  jest  pusta  do  : bieżący_węzeł ← wierzchołek kolejki z minimalną odległością do celu usuń bieżący_węzeł z kolejki  dla każdego  sąsiada n bieżącego_węzła  wykonaj  :  jeśli  n  nie  jest  odwiedzane  then  :  jeśli  n  jest  celem:  zwróć  n  else  : zaznacz n jako odwiedzone dodaj n do kolejki  powrót  błąd

Zobacz też

  1. ^ Pearl, J. Heuristics: inteligentne strategie wyszukiwania do rozwiązywania problemów komputerowych . Addison-Wesley, 1984. s. 48.
  2. ^ ab J Russell, Stuart   .; Norvig, Peter (2003), Sztuczna inteligencja: nowoczesne podejście (wyd. 2), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2 . s. 94 i 95 (przypis 3).
  3. ^   Korf, Richard E. (1999). „Algorytmy wyszukiwania sztucznej inteligencji”. W Atallah, Michaił J. (red.). Podręcznik algorytmów i teorii obliczeń . Prasa CRC. ISBN 0849326494 .
  4. ^ https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Chciwe najlepsze pierwsze wyszukiwanie, gdy EHC zawiedzie, Carnegie Mellon

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Best-first_search&oldid=1141983823 ”