Data Structures Algorithms 简明教程
Approximation Algorithms
Approximation Algorithms
近似算法是专为解决不能在多项式时间内求解以获得近似解的问题而设计的。这些问题被称为 NP 完全问题。这些问题对解决现实世界问题非常有效，因此，使用不同的方法来解决它们变得很重要。
Approximation algorithms are algorithms designed to solve problems that are not solvable in polynomial time for approximate solutions. These problems are known as NP complete problems. These problems are significantly effective to solve real world problems, therefore, it becomes important to solve them using a different approach.
NP 完全问题仍然可以在三种情况下得到解决：输入非常小以至于执行时间减少、某些问题仍然可以归类为可以在多项式时间内解决的问题，或者使用近似算法为问题找到近似最优解。
NP complete problems can still be solved in three cases: the input could be so small that the execution time is reduced, some problems can still be classified into problems that can be solved in polynomial time, or use approximation algorithms to find near-optima solutions for the problems.
这就引出了近似问题的性能比率的概念。
This leads to the concept of performance ratios of an approximation problem.
Performance Ratios
计算近似算法的 performance ratio （也称为 approximation ratio ）背后的主要思想是找出近似解与最优解的接近程度。
The main idea behind calculating the performance ratio of an approximation algorithm, which is also called as an approximation ratio, is to find how close the approximate solution is to the optimal solution.
近似比率用 ρ(n) 表示，其中 n 是算法的输入大小，C 是算法获得的近似最优解，C* 是问题的最优解。当且仅当算法具有近似比率 ρ(n) 时，
The approximate ratio is represented using ρ(n) where n is the input size of the algorithm, C is the near-optimal solution obtained by the algorithm, C* is the optimal solution for the problem. The algorithm has an approximate ratio of ρ(n) if and only if −
max\left\{\frac{C}{C^{\ast} },\frac{C^{\ast }}{C} \right\}\leq \rho \left ( n \right )
然后，算法称为 ρ(n) 近似算法。近似算法可以应用于两种类型的优化问题：最小化问题和最大化问题。如果问题的最优解是找到最大成本，则该问题称为最大化问题；如果问题的最优解是找到最小成本，则该问题称为最小化问题。
The algorithm is then called a ρ(n)-approximation algorithm. Approximation Algorithms can be applied on two types of optimization problems: minimization problems and maximization problems. If the optimal solution of the problem is to find the maximum cost, the problem is known as the maximization problem; and if the optimal solution of the problem is to find the minimum cost, then the problem is known as a minimization problem.
对于最大化问题，近似比率由 C*/C 计算，因为 0 ≤ C ≤ C*。对于最小化问题，近似比率由 C/C* 计算，因为 0 ≤ C* ≤ C。
For maximization problems, the approximation ratio is calculated by C*/C since 0 ≤ C ≤ C*. For minimization problems, the approximation ratio is calculated by C/C* since 0 ≤ C* ≤ C.
假设近似算法的成本都是正的，那么性能比率是明确定义的，并且不会小于 1。如果值为 1，则表示近似算法生成了精确的最优解。
Assuming that the costs of approximation algorithms are all positive, the performance ratio is well defined and will not be less than 1. If the value is 1, that means the approximate algorithm generates the exact optimal solution.