Teorie-emm ke žkoušce EMM
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
gradientní algoritmus - uspořádané prohledávání, hledání nejkratší cesty
algoritmus A - modifikovaná hodnotící funkce
-
f(i) = g(i) + h(i)
-
problém: obvykle přesně neznáme, nutno nahradit odhady
5) Charakterizujte úlohu o hledání minimální kostry grafu, stručně popište princip
jejího řešení. = najít kostru s minimálním součtem ohodnocených hran
seřadíme hrany podle hodnocení neklesajícím způsobem
podle takto získaného pořadí zkoumáme postupně hrany
hranu přidáme do kostry, pokud netvoří s dříve zařazenými hranami uzavřený obvod
algoritmus končí, jakmile zařazené hrany utvoří kostru
6) Charakterizujte úlohu o hledání nejkratší cesty v grafu, stručně popište princip
jejího řešení. - nalezení nejkratší cesty mezi dvěma místy - síť cest
- některé cesty nemusí existovat
vypočteme délku tras od počátku do všech uzlů, do nichž se lze dostat z uzlu aktuálního;
začneme u uzlu, ve kterém chceme začínat, tam je počáteční délka rovna nule)
přesuneme se do uzlu, který je nejblíže počátku a v němž jsme ještě nebyli; a má pro nás
nejkratší délku - hodnoty jednotlivých uzlů sčítáme
např. do uzlu C je vzdálenost od A = 1, přes B = 5+2 = 7, přes D= 5+7 = 12… tedy do uzlu C
půjdeme nejkratší cestou a to je A-C, a takto pokračujeme i u ostatních uzlů až k tomu
konečnému
algoritmus končí, jakmile se dostaneme do cílového místa.
7) Charakterizujte úlohu o hledání maximálního toku v síti, stručně popište princip
jejího řešení. - propustnost produktovodů
Ford Fulkersonova věta: Maximální tok v síti je roven jejímu minimálnímu řezu
- algoritmus k nalezení maximálního toku v síti