| [Member (365WT)]answers [Chinese ] | Time :2017-11-24 | All known NP-hard problem algorithms have exponential runtimes. However, polynomial algorithms sometimes exist if we are looking for a "good" rather than optimal solution.
Given a minimization problem and an approximation algorithm, we evaluate the algorithm as follows: First, give a lower bound of the optimal solution, and then compare the running result of the algorithm with the lower bound
Compare. For the maximization problem, give an upper bound first and then compare the running result of the algorithm with the upper bound.
The approximate algorithms include: minimum vertex coverage, travel salesman problem, set coverage and so on.
To date, all NP-complete problems have no polynomial-time algorithms.
For such problems, usually the following strategies can be taken.
(1) Solve only specific instances of the problem
(2) using dynamic programming or branch and bound method to solve
(3) solve with probability algorithm
(4) Only approximate solution
(5) Use heuristic method to solve
If the optimal value of an optimization problem is c *, the approximate objective function value of the approximate optimal solution obtained by an approximate algorithm for solving the problem is c,
The performance ratio of this approximation algorithm is defined as max (c / c *, c * / c). In general, this performance ratio is a function of the problem input size n
ρ (n), that is, max (c / c *, c * / c) ＜= ρ (n).
The relative error of the approximation algorithm is defined as Abs [(c-c *) / c *]. If the input size n of the problem has a function ε (n) such that Abs [(c-c *) / c *] ＜= ε (n), then ε (n) is the relative error bound of the approximation algorithm. The approximate performance ratio between ρ (n) and the relative error bound ε (n) is obviously as follows
Relationship: ε (n) ≤ρ (n) -1. |
|
