Tip:
Highlight text to annotate it
X
Wiedząc o nieoptymalności metody przeszukiwania wgłąb, można zapytać,
dlaczego ktokolwiek chciałby z niej korzystać?
Odpowiedź ma związek ze zużyciem pamięci.
Tutaj zilustrowałem przestrzeń stanu
składającą się z bardzo dużego, a może nawet nieskończonego drzewa binarnego.
Gdy schodzimy na poziom 1, 2, 3, aż do poziomu n,
drzewo staje się coraz większe i większe.
Rozważmy teraz granicę każdego z tych algorytmów wyszukiwania.
W przypadku wyszukiwania wgłąb wiemy, że granica wygląda tak,
a zatem kiedy schodzimy do poziomu n, ilość potrzebnej pamięci wynosi
dwa do potęgi n, w przypadku przeszukiwania wszerz.
W przypadku poszukiwania najpierw-najtańszego, granica będzie bardziej skomplikowana.
Metoda będzie tworzyć mniej więcej taki kontur kosztów,
ale będzie zajmowała podobną ilość węzłów.
Ale w przypadku przeszukiwania w głąb, wraz ze schodzeniem w dół drzewa, zaczniemy schodzić po tej gałęzi,
a potem wrócimy, ale w każdym punkcie nasza granica będzie zawierała jedynie n węzłów
a nie 2 do potęgi n-tej, co stanowi olbrzymią oszczędność.
Oczywiście jeżeli również śledzimy zbiór zbadanych węzłów,
to nie otrzymamy aż tak dużych oszczędności,
ale bez zbioru zbadanych węzłów, przeszukiwanie wgłąb posiada wielką przewagę
jeżeli idzie o zużycie pamięci.
Inną godną rozważenia własnością algorytmów
jest własność kompletności, oznaczający, że jeżeli gdzieś pojawia się cel,
to czy nasz algorytm go znajdzie?
Przejdźmy z bardzo dużych drzew do nieskończonych drzew,
i powiedzmy, że gdzieś tam głęboko na dole drzewa ukryty jest nasz cel.
Pytanie brzmi: czy każdy z tych algorytmow jest kompletny?
To znaczy, czy gwarantują one znalezienie ścieżki prowadzącej do celu?
Zaznacz, które algorytmy są Twoim zdaniem kompletne w przedstawionym przed chwilą sensie.