Nalezení nejlepšího řešení
Abstrakt
Článek navazuje na předchozí výklad dynamického programování a zaměřuje se na jeho využití při řešení optimalizačních úloh. Základní princip spočívá v postupném řešení menších instancí problému, ukládání jejich výsledků a určování optimální hodnoty pomocí minima či maxima již vypočtených hodnot. První podrobně rozebranou úlohou je nalezení nejdelší cesty mezi dvěma vrcholy v topologicky uspořádaném orientovaném acyklickém grafu. Autor porovnává neefektivní prohledávání všech cest s řešením pomocí dynamického programování a ukazuje také rekonstrukci samotné optimální cesty pomocí pole předchůdců. Druhý příklad se týká optimálního výběru z posloupnosti časově ohodnocených úkolů. Jsou předvedeny dvě rovnocenné formulace dynamického programu a diskutována jejich časová a prostorová složitost.
Stahování
Publikováno
Jak citovat
Číslo
Sekce
Licence
Copyright (c) 2026 Matematika–Fyzika–Informatika
Tato práce je licencována pod Mezinárodní licencí Creative Commons Attribution 4.0 .
Autoři, kteří publikují v tomto časopise, souhlasí s následujícími body:
- Autoři si ponechávají copyright a garantují časopisu právo prvního publikování, přitom je práce zároveň licencována pod Creative Commons Attribution licencí, která umožňuje ostatním sdílet tuto práci s tím, že přiznají jejího autora a první publikování v tomto časopisu.
- Autoři mohou vstupovat do dalších samostatných smluvních dohod pro neexkluzivní šíření práce ve verzi, ve které byla publikována v časopise (například publikovat ji v knize), avšak s tím, že přiznají její první publikování v tomto časopisu.
Obsah časopisu podléhá licenci Creative Commons Uveďte autora 3.0 Česko
