Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM16 - Coggle Diagram
MM16
Dynamic Programming
-
resolves each subproblem (typically in a recurrence relation) only once and records the results in a table from which a solution to the original problem can be obtained
principle of optimality
an optimal solution to any instance of an optimization problem is composed of optimal solutions to its substances
examples
Coin-row problem
In a row of n coins, pick up the maximum amount of money subject to the constraint that no two coins adjacent in the initial row can be picked up
-
-
Coin-collecting problem
Maximum number of coins collected, where each is in a n x m board, and the path to do it, where one can move either one cell to the right or one cell down from its current location
-
Knapsack Problem
The knapsack problem can be reduced to a recurrence relation and be solved through dynamic programming with time efficiency of Θ(nW)
Bottom-up and Top-down methods can be combined with memory functions (begins with an empty table which is filled every new calculation, where the first calculations are always top-down)
Approximations
To deal with difficult optimization problems, we need to solve them approximately by a fast algorithm
-
-
Travelling Salesman
If P != NP, there exists no c-approximation algorithm for the traveling salesman problem
-
-
-
-