Please enable JavaScript.
Coggle requires JavaScript to display documents.
M16 - Coggle Diagram
M16
Dynamic Programming
-
Example: In Fibonacci if we try to use recurrence directly to compute the nth Fibonacci number F (n), we would have to recompute the same values of this function many times
So we can simply fill elements of a one-dimensional array with the n + 1 consecutive values of F (n) by starting, in view of initial conditions, with 0 and 1 and using equation
principle of optimality = In terms somewhat different from its original formulation, it says that an optimal solution to any
instance of an optimization problem is composed of optimal solutions to its subinstances.
Three Basic Examples:
Coin-row problem: There is a row of n coins whose values are some positive integers c1, c2,...,cn, not necessarily distinct. The goal is to pick up the maximum amount of money subject to the constraint that no two coins adjacent in the initial row can be picked up.
Change-making problem: Consider the general instance of the following well-known problem. Give change for amount n using the minimum number of coins of denominations d1 < d2 < ... < dm.
Coin-collecting problem: Several coins are placed in cells of an n × m board, no more than one coin per cell. A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell
The Knapsack Problem: To design a dynamic programming algorithm, we need to derive a recurrence
relation that expresses a solution to an instance of the knapsack problem in terms
Memory Functions: The goal is to get a method that solves only subproblems that are necessary and does so only once. Such a method exists; it is based on using memory functions
Aproximation Algorithms for NP-Hard Problems: problems that are at least as hard as NP-complete problems
Although approximation algorithms run a gamut in level of sophistication, most of them are based on some problem-specific heuristic. A heuristic is a common-sense rule drawn from experience rather than from a mathematically proved assertion.
Traveling Salesman Problem: If P = NP, there exists no c-approximation algorithm for the traveling salesman problem, i.e., there exists no polynomial-time approximation algorithm for this problem so that for all instances
Greedy Algorithms for the TSP The simplest approximation algorithms for the traveling salesman problem are based on the greedy technique.
-
-
-
Knapsack problem: We can think of several greedy approaches to this problem. One is to select the items in decreasing order of their weights; however, heavier items may not be the most valuable in the set.
- Compute the value-to-weight ratios vi/wi, i = 1, . . . , n, for the items given
- Sort the items in nonincreasing order of the ratios computed in Step 1. (Ties can be broken arbitrarily.)
- Repeat the following operation until the knapsack is filled to its full capacity or no item is left in the sorted list: if the current item on the list fits into the knapsack in its entirety, take it and proceed to the next item; otherwise, take its largest fraction to fill the knapsack to its full capacity and stop.