Please enable JavaScript.
Coggle requires JavaScript to display documents.
DYNAMIC PROGRAMMING, Approximation algorithms for NP-hard problem,…
DYNAMIC PROGRAMMING
-
THEORY
An algorithm design technique that does not have to be limited to special types of optimization problems, it solves problems with overlapping subproblems. This is, it suggests solving each of the smaller subproblems only once and recording the results in a table from which a solution to the original problem can then be obtained.
Dynamic programming algorithm can sometimes be refined to avoid extra space, even although a straightforward application of it can be interpreted as a special variety of space-for-time trade-off.´
PRINCIPLE OF OPTIMALITY: an optimal solution to any instance of an optimization problem is composed of optimal solutions to its subinstances.
-
Heuristic: common-sense rule drawn from experience rather than from a mathematically proved assertion.