Sztuczna inteligencja/SI Moduł 5 - Wnioskowanie jako metoda przeszukiwania

Wprowadzenie

Jak mieliśmy okazję przekonać się w lekcji trzeciej, PROLOG jest językiem deklaratywnym, opisującym sposób sterowania algorytmem wnioskowania. Sama zasada wnioskowania polega na zastępowaniu stwierdzeń, których prawdziwość jest poddawana weryfikacji, przez inne stwierdzenia, zgodnie z zapisanymi definicjami predykatów. Proces ten kończy się wtedy, gdy algorytm wnioskowania dojdzie do stwierdzenia prawdziwego (gdyż zapisanego jako prawdziwe), bądź wtedy, gdy nie da się dopasować żadnej reguły wnioskowania.

Spróbujmy sobie wyobrazić graficznie schemat zależności między stwierdzeniami, poddawanymi weryfikacji, regułami i faktami. Dla przykładu rozważmy najpierw predykaty kr_ko, m_ko, m_kr, m_st, opisujące relacje: kraj położony na kontynencie, miasto położone na kontynencie, miasto położone w kraju oraz miasto będące stolicą kraju.

m_ko("Berlin", "Europa").
m_ko("Warszawa", "Europa").
m_ko("Kraków", "Europa").
m_ko("Irkuck", "Azja").
m_ko("Moskwa", "Europa").

m_kr("Kraków", "Polska").
m_kr("Irkuck", "Rosja").

m_st("Warszawa", "Polska").
m_st("Moskwa", "Rosja").

m_kr(Miasto, Kraj):-
  m_st(Miasto, Kraj).
kr_ko(Kraj, Kont):-
  m_kr(Miasto, Kraj),
  m_ko(Miasto, Kont).

Skonstruujmy graf skierowany w następujący sposób (patrz rysunek poniżej). Istnieją dwa wyróżnione węzły: „prawda” i „porażka”. Węzeł „prawda” jest połączony krawędziami z każdym z podanych faktów (ujętymi w pola prostokątne). Węzeł „porażka” jest połączony krawędziami z każdym stwierdzeniem, którego zmiennych nie da podstawić na wartości zgodne z żadnym faktem ani z konkluzją żadnej z reguł. Każda definicja predykatu, będąca regułą, jest połączona krawędziami ze stwierdzeniami (ujętymi w zaoblone prostokąty), które są wynikiem podstawień zmiennych z części przesłankowej reguły. W przypadku reguł, w których część przesłankowa jest koniunkcją warunków logicznych, wprowadzamy pomocniczy węzeł koniunkcyjny (ujęty w owal), w którym zapisujemy podstawienia wszystkich zmiennych pomocniczych (tj. nie występujących jako elementy konkluzji reguły). W naszym przykładzie dotyczy to definicji predykatu kr_ko, której argumentami są Kraj i Kont, zaś zmienną pomocniczą jest Miasto.

Śledzenie ścieżek prowadzących do węzłów „prawda” i „porażka” jest istotą wnioskowania. Jako prawdziwe uznaje się:

• Fakty (prostokąty), połączone bezpośrednio z węzłem prawda (jak np. w przypadku faktu m_kr("Kraków", "Polska")),
• Pomocnicze węzły koniunkcyjne (owale), połączone wyłącznie z prawdziwymi węzłami,
• Stwierdzenia (zaoblone prostokąty) połączone z co najmniej jednym węzłem prawdziwym.

Prześledźmy sposób wnioskowania związany z weryfikacją stwierdzenia:

kr_ko("Polska", "Europa").

W tym celu naszkicujmy wszystkie połączenia wiążące się z weryfikowanym stwierdzeniem (patrz rysunek poniżej).

Prawdziwość stwierdzenia kr_ko(Polska, Europa) wynika z tego, że węzeł, odpowiadający temu stwierdzeniu, łączy się z prawdziwymi węzłami, odpowiadającymi koniunkcjom:

m_kr("Warszawa", "Polska"), m_ko("Warszawa", "Europa").
m_kr("Kraków", "Polska"), m_ko("Kraków", "Europa").

Prawdziwość składników tych koniunkcji wynika albo znowu z wnioskowania, tak jak w przypadku stwierdzenia:

m_kr("Warszawa", "Polska")

albo też z bezpośredniego połączenia ich z węzłem „prawda”; dotyczy to stwierdzeń:

m_kr("Kraków", "Polska"),
m_ko("Kraków", "Europa"),
m_ko("Warszawa", "Europa")

Zauważmy, że w czasie wywodu będą sprawdzone również węzły, odpowiadające koniunkcjom:

m_kr("Irkuck", "Polska"), m_ko("Irkuck", "Europa").
m_kr("Moskwa", "Polska"), m_ko("Moskwa", "Europa").

przy czym co najmniej jeden z elementów każdej z powyższych koniunkcji jest bezpośrednio lub pośrednio połączony z węzłem „porażka”.

Podobne grafy połączeń można skonstruować dla każdego stwierdzenia:

m_kr(Miasto, Kraj)
m_st(Miasto, Kraj)
m_ko(Miasto, Kontynent)
kr_ko(Kraj, Kontynent)

Każdy z takich grafów jest podzbiorem grafu pełnego, który jest grafem całej przestrzeni przeszukiwań, w której prowadzone jest wnioskowanie. Tak więc wnioskowanie jest przeglądaniem przestrzeni przeszukiwań, ograniczonym do możliwie najmniejszej liczby węzłów pozwalających stwierdzić prawdziwość badanego stwierdzenia.

Sposoby wnioskowania

Graf wnioskowania jest grafem skierowanym, gdyż reguły wnioskowania mają wyróżnioną część przesłankową i konkluzję. Przeszukiwanie grafu, jako realizacja procesu wnioskowania, może być prowadzone na dwa sposoby – zgodnie lub przeciwnie do kierunku wskazywanego przez strzałki.

Wnioskowanie wstecz

Przyjęcie kierunku przeciwnego do strzałek oznacza, że wnioskowaniem kieruje stwierdzenie do weryfikacji. To stwierdzenie jest zastępowane przez wiele innych, tak, aby w końcu dojść do jednego z dwóch węzłów terminalnych – „prawda” albo „porażka”. Taki sposób postępowania jest wykorzystywany w maszynie wnioskującej PROLOGu i jest nazywany wnioskowaniem regresywnym (inaczej: wnioskowaniem sterowanym celem, albo wnioskowaniem wstecz).

Algorytm weryfikacji wstecz

Argument: stwierdzenie $S\,$

Dla każdej definicji $D\,$ predykatu unifikującej się ze stwierdzeniem

Jeśli $D\,$ jest faktem

zwróć wartość „prawda”

Jeśli $D\,$ jest regułą

powtarzaj

Wybierz stwierdzenie $S_{i}\,$ będące składnikiem części przesłankowej

Wykonaj unifikacje zmiennych pomocniczych

Wykonaj weryfikację wstecz ($S_{i}\,$)

dopóki są niezweryfikowane stwierdzenia $S_{i}\,$

Jeśli wszystkie $S_{i}\,$ są prawdziwe

zwróć wartość „prawda”

w przeciwnym przypadku

zwróć wartość „porażka”

Wnioskowanie w przód

Jednak można sobie wyobrazić inną metodę postępowania: posuwać się od węzła „prawda” w kierunku strzałek, generując nowe prawdziwe stwierdzenia, w nadziei wygenerowania tego stwierdzenia, które podlega weryfikacji. Ten sposób postępowania nosi nazwę wnioskowania progresywnego (inaczej: wnioskowania sterowanego danymi albo wnioskowania w przód).

Algorytm weryfikacji w przód

Argument: stwierdzenie $S\,$

Lista faktów $F=\emptyset$

Dopóki $S\,$ nie unifikuje się z żadnym faktem z $F\,$ powtarzaj

Zbiór definicji predykatu $D=\emptyset$

Dla każdej definicji $D_{i}\,$

Jeśli $D_{i}\,$ jest faktem lub

$D_{i}\,$ jest regułą i część przesłankowa unifikuje się z faktami z $F\,$

$D=D\cup \{D_{i}\}$

Wybierz definicję $D_{i}\,$ ze zbioru $D\,$

Jeśli $D_{i}\,$ jest faktem

$F=F\cup \{D_{i}\}$

Jeśli $D_{i}\,$ jest regułą

$F_{d}\,$ = zbiór podstawień konkluzji reguły $D_{i}\,$

$F=F+F_{d}\,$

Sterowanie wnioskowaniem

Przegląd grafu wnioskowania musi się z konieczności odbywać w sposób sekwencyjny, a zatem algorytm wnioskujący będzie wykonywać weryfikację stwierdzeń w ustalonym porządku. Stąd konieczność dokonywania pewnych wyborów w każdym z wymienionych wyżej algorytmów - konieczność sterowania wnioskowaniem. Sterowanie wnioskowaniem ma kluczowe znaczenie z punktu widzenia efektywności procesu przeszukiwania - nie trzeba chyba przekonywać, że im mniejsza liczba odwiedzanych węzłów grafu wnioskowania, tym szybszy proces wnioskowania.

Sterowanie wnioskowaniem wstecz

W przypadku wnioskowania wstecz, wybór dotyczy kolejności rozważania alternatywnych definicji predykatu, a także kolejności analizowania składników przesłanki reguły. Ta pierwsza decyzja ma wpływ na szybkość poruszania się w głąb grafu wnioskowania, co może przyspieszyć moment pierwszego dojścia do węzła „prawda” (a niekiedy zależy nam nie na wszystkich, lecz na jakimkolwiek sposobie udowodnienia prawdziwości stwierdzenia). Druga decyzja z kolei rzutuje na kolejność unifikacji zmiennych pomocniczych, a zatem na „szerokość” zbioru węzłów będących alternatywnymi unifikacjami. Przykładowo, w definicji predykatu kr_ko(Kraj, Kont) przyjęliśmy następującą kolejność rozważania składników części przesłankowej:

m_kr(Miasto, Kraj),
m_ko(Miasto, Kont).

Powoduje to, że w trakcie wnioskowania wykonana będzie najpierw próba unifikacji predykatu m_kr, a później m_ko. W efekcie, będzie 5 prób unifikacji m_kr i tylko dwie (Warszawa, Kraków) próby unifikacji m_ko (zresztą udane). Przy odwrotnej definicji predykatu:

kr_ko(Kraj, Kont):-
  m_ko(Miasto, Kont),
  m_kr(Miasto, Kraj).

mielibyśmy 5 prób unifikacji m_ko (w tym cztery udane) i cztery próby unifikacji m_kr. Tak więc umiejętnie sterując wnioskowaniem można ograniczyć pracochłonność tego procesu.

W PROLOGu, decyzje dotyczące kolejności rozważania definicji i kolejności rozważania składników koniunkcji przypadają w udziale programiście, gdyż maszyna wnioskująca dokonuje analizy w kolejności zapisanej w programie: od lewej do prawej, od góry do dołu. Można sobie jednak wyobrazić nieco bardziej zaawansowaną maszynę wnioskującą, która dokonywałaby tego wyboru w sposób automatyczny. Przykładowo, można w procesie oceny stwierdzeń części przesłankowej jako pierwsze wybierać te, których zmienne pomocnicze mają najmniej pomyślnych unifikacji.

Sterowanie wnioskowaniem w przód

W przypadku wnioskowania w przód, kluczową decyzją z punktu widzenia efektywności algorytmu jest wybór definicji predykatu do zastosowania. Ze względu na fakt, że przed pomyślnym zakończeniem wnioskowania nie jesteśmy w stanie określić, która definicja jest na którym etapie najlepsza, stosować można rozmaite zdroworozsądkowe zasady postępowania, takie jak stosowanie definicji najrzadziej dotychczas wykorzystywanej, definicji najbardziej ogólnej (o możliwie największej liczbie podstawień zmiennych), najbardziej szczegółowej itp. Podobnymi kryteriami można się kierować również przy wyborze definicji we wnioskowaniu wstecz.

Sterowanie wyborem reguł musi być wykonywane z duża ostrożnością, gdyż przy niefortunnych zasadach sterowania, łatwo o wejście w nieskończoną ścieżkę wnioskowania. Wbrew pozorom nie jest to sytuacja trudno wyobrażalna – wystarczy rozważyć predykat member zdefiniowany następująco:

member(X,[X,_]).
member(X,[_|T]):-
  member(X,T).

Weryfikacja prawdziwości stwierdzenia w PROLOGu:

member("a",L).

spowoduje generację w nieskończoność coraz to dłuższej listy.

Wybór metody wnioskowania

Jeśli mamy do wyboru dwa schematy wnioskowania - wstecz i w przód - który z nich powinien być wybrany? Odpowiedź na to pytanie powinna być oparta na przewidywaniu co do wielkości stopnia rozgałęziania grafu wnioskowania w kierunku, w którym następuje wnioskowanie. Przez stopień rozgałęziania będziemy rozumieć średnią liczbę krawędzi, wychodzących z węzła w kierunku wykorzystywanym w schemacie wnioskowania (tj. zgodnie z kierunkiem wynikania reguł w przypadku wnioskowania w przód, a przeciwnie do tego kierunku w schemacie wnioskowania wstecz). Jeśli odległość (rozumiana jako najkrótsza liczba strzałek do przejścia) między prawdziwym stwierdzeniem a węzłem „prawda” wynosi $n\,$, zaś stopień rozgałęzienia wynosi Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle a\,} , wówczas przy odpowiednim sposobie sterowania wnioskowaniem zostanie wykonana weryfikacja Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle a^n\,} stwierdzeń. Mogąc zatem wybierać kierunek wnioskowania, wybierzemy ten o mniejszym stopniu rozgałęziania, co poskutkuje krótszym czasem wnioskowania.

Rozwiązywanie problemów przez przeszukiwanie przestrzeni

Wnioskowanie nie jest jedynym i na pewno nie najprostszym przykładem zastosowania przeszukiwania do rozwiązywania problemów. Obecnie zajmiemy się zagadnieniem przeszukiwania przestrzeni odrywając się od specyfiki tej przestrzeni, podyktowanej przez specyfikę rozwiązywanego zadania. Zadanie to sprowadza się w swej ogólnej postaci do pełnego przeglądu przestrzeni – odwiedzenia wszystkich węzłów.

Schemat przeszukiwania przestrzeni zapiszemy w postaci podstawowego algorytmu przeszukiwania, którego warianty, związane z pewnymi właściwości przestrzeni przeszukiwań, będziemy rozważać w tym i kolejnym rozdziale.

Algorytm przeszukiwania przestrzeni przetwarza zbiór węzłów do odwiedzenia Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A_t\,} , zbiór węzłów odwiedzonych Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle V_t\,} i bieżący węzeł Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s_t\,} . Zasada działania jest prosta. Algorytm rozpoczyna pracę od wyróżnionego węzła Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s_0\,} . Węzeł ten staje się węzłem odwiedzonym, zaś wszystkie węzły z jego sąsiedztwa są dodawane do zbioru Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle V_t\,} . Rozpoczyna się dalej pętla główna, w której wykonywane są następujące czynności. Ze zbioru Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A_t\,} jest wybierany kolejny węzeł i jest od dodawany do zbioru odwiedzonych Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle V_t\,} . Wszystkie węzły z jego sąsiedztwa, które nie były jeszcze odwiedzone, są dodawane do zbioru Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A_t\,} . Pętla jest wykonywana do osiągnięcia kryterium zatrzymania, którym może być np. opróżnienie zbioru Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A_t\,} bądź też znalezienie węzła Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s_t\,} o szczególnych, interesujących nas właściwościach.

Algorytm przeszukiwania przestrzeni

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle t = 0\,}

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle V_0 = \{s_0\}\,}

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A_t = N(s_0)\,}

Powtarzaj

Wybierz Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s_{t+1}\,} z Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A_t\,}

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle V_{t+1} = V_t \cup \{s_{t+1}\}\,}

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A_{t+1} = A_t \cup N(s_{t+1}) - V_t\,}

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle t = t + 1\,}

Dopóki niespełniony warunek zatrzymania

W praktycznych realizacjach algorytmu przeszukiwania zbiór Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A_t\,} jest realizowany jako kolejka. Wybór węzła z kolejki Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A_t\,} może być dokonywany na podstawie kolejności dodawania – wówczas uzyskuje się ślepe strategie przeszukiwania – bądź też wybór ten jest wykonywany na podstawie dodatkowych właściwości węzła – prowadzi to do tzw. poinformowanych strategii przeszukiwania (tzw. strategie „najpierw najlepszy” – best first). W ramach ślepych strategii przeszukiwania, wybór węzła Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s_t\,} z kolejki $A_{t}\,$ oraz dodawanie nowych węzłów może być wykonywane według reguły rządzącej kolejką LIFO albo FIFO. Uzyskuje się odmienny sposób sterowania przeszukiwaniem, prowadzący do dwóch różnych realizacji algorytmu: przeszukiwania w głąb i wszerz.

Ślepe strategie przeszukiwania

Ślepymi strategiami przeszukiwania nazywane są takie sposoby sterowania przeszukiwaniem, w których zbiór $A_{t}$ jest uporządkowany w kolejności określonej sekwencją dodawania do niego kolejnych elementów.

Strategia w głąb

W strategii „w głąb”, zbiór $A_{t}\,$ jest reprezentowany jako kolejka LIFO. Oznacza to, że po wyborze węzła $s_{t}\,$ i usunięciu go z kolejki $A_{t}\,$, elementy z sąsiedztwa $N(s_{t})\,$ wchodzą niejako „na miejsce” $s_{t}\,$ (patrz rysunek). W konsekwencji, węzeł ostatnio dodany do listy będzie pierwszym z niej wybranym.

Strategia wszerz

Z kolei w strategii „wszerz”, zbiór $A_{t}\,$ jest kolejką FIFO. Po wybraniu węzła $s_{t}\,$ i usunięciu go z kolejki $A_{t}\,$, elementy z sąsiedztwa $N(s_{t})\,$ są wstawiane na koniec kolejki. Powoduje to, że kolejnym rozważanym węzłem będzie ten, który był najdawniej dodany (a zatem był dodany bezpośrednio po $s_{t}\,$).

Dyskusja

Jeśli celem przeszukiwania jest odnalezienie docelowego węzła o pożądanych cechach, wówczas strategia w głąb ma szanse znaleźć ten węzeł szybciej niż metoda wszerz. Jeśli w przestrzeni przeszukiwań istnieją ścieżki nieskończonej długości, nie można zagwarantować, że strategia w głąb nie „pójdzie” taką właśnie ścieżką.

Natomiast jeśli celem przeszukiwania jest znalezienie najkrótszej ścieżki, łączącej węzeł początkowy z docelowym, wówczas stosując strategię wszerz mamy gwarancję jej wyznaczenia. Unikamy w ten sposób ryzyka ścieżki nieskończonej.

Przykład

Jako ilustrację sposobu działania strategii wszerz i w głąb, rozważmy następujący prosty przykład. Załóżmy, że zamierzamy odnaleźć drogę w labiryncie, prowadzącą z kratki A do kratki B. Każda kratka ma co najwyżej czterech sąsiadów (brak sąsiada jest zaznaczony grubą linią – „ścianą” labiryntu).

Tak więc kratki labiryntu będą węzłami przestrzeni przeszukiwań.

Poszukiwanie wyjścia polega na tym, że wpisujemy do kratek numery iteracji, w których były one węzłem rozwijanym przez algorytm przeszukiwania. Po odnalezieniu rozwiązania drogę będziemy odtwarzać, idąc od węzła B do węzła A w kierunku sąsiedniej kratki o najmniejszym numerze.

Załóżmy, że obie metody przeszukiwania rozważają kratki sąsiadujące w kolejności: góra, lewo, dół, prawo. Dostajemy wówczas dla obu metod kolejność odwiedzania kratek labiryntu jak na poniższych rysunkach.

Metoda w głąb

Metoda wszerz

Zauważmy skutki efektu odwrócenia kolejności rozważania węzłów sąsiedztwa wynikającego z działania kolejki LIFO. Widać także, że pierwsza ścieżka, znaleziona przez algorytm przeszukiwania w głąb, nie jest ścieżką najkrótszą. Z drugiej jednak strony, w tym akurat zadaniu metoda wszerz wymaga odwiedzenia wszystkich pól labiryntu, aby znaleźć pierwsze (i zarazem najlepsze) rozwiązanie.