Tip:
Highlight text to annotate it
X
Oto odpowiedzi.
Przeszukiwanie wszerz, jak sama nazwa wskazuje, rozwija węzły w następującej kolejności.
1, 2, 3, 4, 5, 6, 7
Przechodzi zatem po kolei po jednej warstwie, przeszukując wszerz.
Czy jest optymalny?
Cóż, zawsze rozwija najpierw najkrótsze ścieżki,
zatem gdziekolwiek by się nie ukrywał poszukiwany węzeł, zostanie znaleziony przez przebadanie
najkrótszej ścieżki, zatem jest optymalny.
W przypadku poszukiwania najpierw-najtańszych, najpierw rozwijamy ścieżkę o długości 0,
następnie ścieżkę o długości 2,
później ścieżkę o długości 4, o długości 5,
ścieżkę o długości 6, o długości 7, i wreszcie ścieżkę o długości 8.
Jak widzieliśmy, gwarantuje znalezienie najtańszej ścieżki ze wszystkich,
zakładając, że koszt każdego pojedynczego kroku jest nieujemny.
Przeszukiwanie w głąb najpierw próbuje dojść tak głęboko, jak tylko może,
zatem bada 1, 2, 3, następne cofa się, 4,
cofa się, 5, 6, 7
I jak widzimy, niekoniecznie znajduje najkrótszą możliwą ścieżkę.
Załóżmy, że cele znajdowałyby się na pozycji 5 i na pozycji 3.
Znalazłby dłuższą ścieżkę do pozycji 3 i odnalazłby tam cel
i nie znalazłby celu na pozycji 5.
Zatem nie jest optymalny.