Tip:
Highlight text to annotate it
X
Widzieliśmy dwa algorytmy przeszukujące
Pierwszy, przeszukiwanie wszerz, w którym zawsze najpierw rozwijamy
najpłytsze ścieżki, najkrótsze ścieżki.
Drugi, najpierw-najtańsze przeszukiwanie, w którym zawsze rozwijamy pierwszą ścieżkę
o najniższym całkowitym koszcie.
Zamierzam skorzystać z tej szansy aby przedstawić trzeci algorytm, przeszukiwanie w głąb,
który jest w pewnym sensie przeciwny do przeszukowania wszerz.
W przeszukiwaniu w głąb zawsze najpierw rozwijamy najdłuższą ścieżkę,
ścieżkę z największą liczbą połączeń.
Teraz chciałbym was poprosić, abyście dla każdego węzła w każdym z tych drzew
powiedzieli, w jakiej kolejności będą rozwijane,
pierwszy, drugi, trzeci, czwarty, piąty i tak dalej, wpisując numer w odpowiednie pole.
A jeżeli są jakieś remisy, wprowadźcie numer i rozwiążcie te remisy w kolejności od lewej do prawej.
Wtedy będę was prosił o odpowiedź na jeszcze jedno pytanie
które brzmi: czy te metody są optymalne?
To znaczy, czy gwarantują znalezienie najlepszego rozwiązania?
Dla przeszukiwania wgłąb najlepsze znaczy takie, które znajduje najkrótszą ścieżkę.
Jeżeli uważasz, że gwarantują znalezienie najkrótszej ścieżki, kliknij tutaj.
Dla poszukiwania "najpierw-najtańsze", oznaczałoby to znalezienie ścieżki, której łączny koszt jest najniższy.
Zaznacz tutaj, jeśli uważasz, że algorytm to gwarantuje
Można założyć, że wszystkie koszty muszą być dodanie.
A w przeszukiwaniu w głąb, najtańszy albo optymalny oznaczałoby,
podobnie jak w przeszukiwaniu wszerz, znalezienie najkrótszej możliwej ścieżki w sensie liczby połączeń.
Zaznacz tutaj, jeśli uważasz, że przeszukiwanie wgłąb zawsze dojdzie do czegoś takiego.