Question

近似算法的基本概念

Answer 1

所有已知的解决NP-难问题算法都有指数型运行时间。但是，如果我们要找一个“好”解而非最优解，有时候多项式算法是存在的。
给定一个最小化问题和一个近似算法，我们按照如下方法评价算法：首先给出最优解的一个下界，然后把算法的运行结果与这个下界
进行比较。对于最大化问题，先给出一个上界然后把算法的运行结果与这个上界比较。
近似算法比较经典的问题包括：最小顶点覆盖、旅行售货员问题、集合覆盖等。
迄今为止，所有的NP完全问题都还没有多项式时间算法。
对于这类问题，通常可采取以下几种解题策略。
(1)只对问题的特殊实例求解
(2)用动态规划法或分支限界法求解
(3)用概率算法求解
(4)只求近似解
(5)用启发式方法求解
若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c，
则将该近似算法的性能比定义为max(c/c*, c*/c)。在通常情况下，该性能比是问题输入规模n的一个函数
ρ(n)，即 max(c/c*, c*/c) <= ρ(n)。
该近似算法的相对误差定义为Abs[(c-c*)/c*]。若对问题的输入规模n，有一函数ε(n)使得Abs[(c-c*)/c*] <= ε(n)，则称ε(n)为该近似算法的相对误差界。近似算法的性能比ρ(n)与相对误差界ε(n)之间显然有如下
关系：ε(n)≤ρ(n)-1。