Finding the Optimal Solution
Abstract
The article continues an earlier introduction to dynamic programming and focuses on its use in optimisation problems. The basic idea is to solve progressively smaller instances of a problem, store their results, and determine the optimal value by taking the minimum or maximum of previously computed values. The first problem analysed in detail is that of finding the longest path between two vertices in a topologically ordered directed acyclic graph. An inefficient enumeration of all possible paths is compared with a dynamic-programming solution, and the reconstruction of the optimal path itself using predecessor information is also demonstrated. The second example concerns an optimisation problem involving a sequence of tasks. Two equivalent dynamic-programming formulations are presented together with an analysis of their time and space complexity.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 MATHEMATICS–PHYSICS–INFORMATICS
This work is licensed under a Creative Commons Attribution 4.0 International License.
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
