Przeszukiwanie przestrzeni stanów

Przeszukiwanie przestrzeni stanów to proces stosowany w dziedzinie informatyki , w tym sztucznej inteligencji (AI), w którym rozważane są kolejne konfiguracje lub stany instancji, z zamiarem znalezienia stanu docelowego o pożądanej właściwości.

Problemy są często modelowane jako przestrzeń stanów , zbiór stanów , w których może znajdować się problem. Zbiór stanów tworzy graf, w którym dwa stany są połączone, jeśli istnieje operacja , którą można wykonać w celu przekształcenia pierwszego stanu w drugi.

Wyszukiwanie w przestrzeni stanów często różni się od tradycyjnych metod wyszukiwania w informatyce , ponieważ przestrzeń stanów jest niejawna : typowy wykres przestrzeni stanów jest o wiele za duży, aby można go było wygenerować i przechowywać w pamięci . Zamiast tego węzły są generowane podczas ich eksploracji, a następnie zazwyczaj odrzucane. Rozwiązanie wyszukiwania kombinatorycznego może składać się z samego stanu docelowego lub ze ścieżki od pewnego stanu początkowego do stanu docelowego.

Reprezentacja

${\ Displaystyle S: \ langle S, A, Akcja (e), Wynik (y, a), Koszt (s, a) \ rangle} ,$ krotka w którym:

• ${\ displaystyle S}$ to zbiór wszystkich możliwych stanów;
• jest zbiorem możliwych działań niezwiązanych z konkretnym stanem, ale dotyczących całej przestrzeni stanów; ${\ displaystyle A}$
• ${\ Displaystyle Akcja (a)}$ jest funkcją, która ustala, jakie działanie można wykonać w określonym stanie;
• ${\ Displaystyle Wynik (s, a)}$ jest funkcją, która zwraca stan osiągnięty wykonując akcję ${\ Displaystyle a}$ w stanie ${\ Displaystyle s}$
• ${\ Displaystyle Koszt (s, a)}$ to koszt wykonania czynności $Displaystyle$ stanie $a}$ . W wielu stanach przestrzenie są stałe, ale generalnie nie jest to prawdą.

Przykłady algorytmów przeszukiwania przestrzeni stanów

Niedoinformowane wyszukiwanie

Według Poole'a i Mackwortha następujące metody przeszukiwania przestrzeni stanów są niedoinformowane , co oznacza, że ​​nie mają żadnych wcześniejszych informacji o lokalizacji celu.

• Tradycyjne przeszukiwanie w głąb
• Wyszukiwanie wszerz
• Pogłębianie iteracyjne
• Wyszukiwanie według najniższego kosztu / Wyszukiwanie według jednolitego kosztu (UCS)

Metody te przyjmują lokalizację celu w postaci funkcji heurystycznej . Poole i Mackworth przytaczają następujące przykłady jako świadome algorytmy wyszukiwania:

• Informowane/heurystyczne przeszukiwanie w głąb
• Chciwe wyszukiwanie najlepiej najpierw
• Wyszukiwanie

Zobacz też

• Przestrzeń stanu
• Planowanie przestrzeni państwowej
• Gałąź i powiązanie - metoda zwiększania wydajności wyszukiwania w przestrzeni stanów poprzez przycinanie jej podzbiorów.

• Stuart J. Russell i Peter Norvig (1995). Sztuczna inteligencja: nowoczesne podejście . Sala Prentice'a.