Tip:
Highlight text to annotate it
X
Zde jsou odpovědi.
Prohledávání do šířky, jak naznačuje název, expanduje uzly v tomto pořadí.
1, 2, 3, 4, 5, 6, 7.
Takže jde po jednotlivých vrstvách, nejprve do šířky.
Je to optimální?
Vždy expanduje nejprve nejkratší cesty,
takže ať je cíl schovaný kdekoliv, algoritmus ho najde,
protože nezkoumá delší cesty, a je tedy optimální.
Při hledání nejlevnějších nejprve expandujeme cestu délky 0,
pak cestu délky 2.
Pak je zde cesta délky 4, cesta délky 5,
cesta déky 6, a cesta délky 7, a nakonec cesta délky 8.
A jak jsme viděli, je zaručené, že najde nejlevnější cestu ze všech,
za předpokladu, že cena žádného z kroků není zá***á.
Prohledávání do hloubky se nejprve snaží dostat tak hluboko, jak jen může,
takže projde 1, 2, 3, pak se vrátí nahoru, 4,
pak se vrátí nahoru, 5, 6, 7.
A je vidět, že nemusí nutně najít nejkratší cestu ze všech.
Řekněme, že tu byly cíle na pozici 5 a na pozici 3.
Našel by delší cestu na pozici 3, kde by našel cíl,
a nenašel by cíl na pozici 5.
Takže to není optimální.