Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dynamic Programming - Coggle Diagram
Dynamic Programming
Technique for solving problems with
overlapping subproblems
.
Example: Fibonacci numbers
can be seen as a variation of space-for-time trade-off
In some situations, it is even possible to avoid the extra space
Fibonacci: store only the last two elements
Approaches for implementing dynamic programming
Bottom-up
solves all subproblems
Top-down
solves all required subproblems
Approximation Algorithms
Sometimes it is even harder to find a solution NP-Complete ⊂ NP-hard
Approximation algorithms is alternative to "resolve" the problem
The solution does not need to be optimal, but only acceptable
greed approximation for TSP
Nearest-neighbour algorithm
MST-based algorithm
TSP: MST-based algorithm
Construct an MST
Perform a walk around the MST
(recording the order of nodes visited)
Eliminate all repeated occurrences except the initial node
(making shortcuts in a walk)
Problems Examples
Knapsack
Change-making
Coin-row