Tip:
Highlight text to annotate it
X
Tu sú odpovede.
Prehľadávanie do šírky, ako už názov naznačuje, rozširuje uzly v nasledujúcom poradí.
1, 2, 3, 4, 5, 6, 7.
Takže v každom kroku prechádza jednou vrstvou, vyhľadávajúc naprieč.
Je to optimálne?
No, keďže sa vždy vydáva najprv po najkratšej ceste,
kdekoľvek sa cieľ ukrýva, nájde ho netestujúc
žiadnu dlhšiu cestu, preto je vskutku optimálny.
Pri vyhľadávaní najlacnejších, sme najprv vytvorili cestu dĺžky 0,
potom cestu dĺžky 2.
Teraz tu máme cestu dĺžky 4, cestu dĺžky 5,
cestu o dĺžke 6, o dĺžke 7, a konečne, cestu dĺžky 8.
Ako sme videli, je zaručené, že nájdeme najlacnejšiu cestu zo všetkých,
za predpokladu, že náklady na každý jednotlivý krok sú nezá***é.
Hľadanie do hĺbky sa najprv pokúsi dostať tak hlboko, ako len môže,
preto prechádza 1, 2, 3, potom na 4,
potom 5, 6, 7
A ako vidíte, nenájde nevyhnutne najkratšiu cestu.
Predpokladajme, že hľadané ciele by boli na pozícii 5 a na pozícii 3
Našiel by dlhšiu cestu do pozície 3 a našiel by tam cieľ
a nenašiel by cieľ v pozícii 5
Takže nie je optimálny.