Tip:
Highlight text to annotate it
X
Takže jsme se podívali na dva vyhledávací algoritmy.
První pro prohledávání do šířky, ve kterém jsme vždy nejprve expandovali
nejmělčí cesty, nejkratší cesty.
A druhý, který nejdříve hledá nejlevnější, takže vždy expanduje nejprve cestu
s nejnižší celkovou cenou.
A já využiji této příležitosti k uvedení třetího algoritmu, prohledávání do hlobuky,
který je svým způsobem opakem prohledávání do šířky.
Při prohledávání do hloubky vždy nejprve expandujeme nejdelší cestu,
cestu s největším počtem propojení.
A teď bych vás chtěl požádat, abyste pro každý z těchto uzlů v každém stromu
řekli, v jakém pořadí budou expandovány.
První, druhý, třetí, čtvrtý, pátý a tak dále, zadáním čísla do kolonky.
A pokud jsou zde nerozhodné stavy, zadejte číslo a postupujte zleva doprava.
Pak bych se chtěl zeptat ještě na jednu otázku:
Jsou tyto metody prohledávání optimální?
Tedy, je zaručené, že najdou nejlepší řešení?
Pro prohledávání do šířky by optimální znamenalo, že najde nejkratší cestu.
Pokud si myslíte, že zaručeně nalezne nejkratší cestu, zaškrtněte zde.
Při hledání nejlevnějších cest by to znamenalo cestu s nejnižší celkovou cenou.
Zaškrtněte zde, pokud si myslíte že je to zaručeno.
Předpokládáme, že všechny ceny musí být kladné.
A pro prohledávání do hloubky by nejlevnější, nebo optimální, opět znamenalo,
stejně jako pro prohledávání do šířky, nalezení nejkratší cesty z hlediska počtu propojení.
Zaškrtněte zde, pokud si myslíte, že prohledávání do šířky takovou cestu vždy najde.