为什么使用近似算法
无法找到一个NP难问题的多项式时间普适算法，因此我们思考牺牲算法的精确度，以在可计算时间内找到一个近似解。对于一个近似算法，满足：
- 在多项式时间内完成
- 具有普适性（能解决这类问题的任何实例）
- 有一个确切的近似程度（准确解的多少倍）
找一个NP难问题的近似算法，只需要证明其近似程度（多少倍地接近精确值），而不用知道这个精确值究竟是多少。
近似算法举例
Ⅰ. 负载均衡问题
台相同的机器，
个不同的工作及完成它所需的时间
，问满足如下条件的最短工作时长。
- 一个工作必须连续执行直到完成；
- 一台机器一次只能处理一个工作。
2倍近似算法——List Scheduling
List Scheduling 是一种贪心策略，它的核心思想是将各个工作依次安排到累计工作时长最短的机器中，下面的动图显示了这一过程。可以发现，这种贪心的初衷只考虑了眼前的最小值，而局部最优解并不一定是最终的最优解。
LS算法fail
我们假设完成所有工作的最短工作时长，来自第i台机器，证明前，先确定两个结论。设完成所有工作的最短时间跨度（makespan）为
，结束时各台机器的时间跨度为
，有：
-
，
不小于完成最长的工作所需时间
-
，
（机器平分工作）
设最后一个加入到第台机器运行的是工作
（注意：不一定是所有工作的最后一个），那么有
①
②
③
所以。
3/2倍近似算法——LPT Rule
上述贪心策略存在一个很明显的漏洞，当最后加入的工作所花时间最长时，效果很差，直逼2倍TT。因此我们希望先安排长工作，将所有工作按花费时间降序排列，再执行上述贪心算法，这就是LPT(Longest Processing Time) Rule的核心思想。
当时，则每台机器最多安排一个工作，容易找到最优解。当
时，先将m个工作安排到m台机器，那么对第
个工作，有
. 则对③，
Graham在1969年，计算出LPT Rule是负载均衡问题的一个4/3近似算法。太复杂了，老师都放弃了···
Ⅱ. 中心选择问题
给定平面（或空间）上的n个点和中心个数k，问如何放置这k个中心，使得所有点被以这k个点为中心的圆盘覆盖且最大的圆盘半径最小（不是所有圆盘的半径之和）。对所有点，被相距最近的中心点形成的圆盘覆盖。
贪心策略——依次选择离其中心最远的点为新的中心
因为中心选择的目标是最小化离其中心最远的点与该中心的距离，所以每次加入新的中心时，直接贪心选择这样离其中心最远的点。
依次选择离其中心最远的点为新的中心，这样的贪心算法是一个2倍近似算法。
设集合和
分别是贪心算法和真实的最佳中心，
和
分别是贪心算法和真实情况里离中心最远的距离（最小覆盖半径）。需要证明结论
≤2
Ⅲ. 带权点覆盖问题
对于点覆盖问题（一个点的集合使得图中所有边至少有一个端点在集合内），带权点覆盖问题中，需要满足这个集合中所有点的权值之和最小。
竞价法是带权点覆盖问题的2倍近似算法
竞价简单理解为边给相邻的点支付保护费，以保证自己能被至少一个点保护（覆盖）；而点收到来自各条相邻边支付的保护费之和刚好是它的权值，才能保护它们。这样，那些收到保护费刚好是自身权值的点构成一个顶点覆盖。下面证明用竞价法是带权点覆盖问题的2倍近似算法。
引理 对于任意点覆盖和边
给出的价格
，有
.
可通过两个恒等变换简单证明，因为很多点共用了边支付的价格，所以一定有所有点给出的竞价不大于点覆盖权值之和。
竞价法过程
选出还未被保护的边，提最少的价使得其相邻点至少有一个能保护它，这些能保护（覆盖）临近边的点称其为紧（tight）的，将其加入点覆盖集合。循环操作，直至所有边都能被保护。伪代码如下：
竞价法算法流程
竞价法求解点覆盖问题，举例如下：
竞价法过程
上图中，最后tight的点{a, b, d}，即为最小的带权点覆盖，权为10. 注意：边给出的竞价之和不是点覆盖的权。
竞价法2倍近似的证明
设最优点覆盖和竞价法获得的点覆盖
，有
.
倒数第二个恒等变换的依据是每条边计算了两次，最后到的放缩依据是，每条边给出的价格不大于其任一相邻点的权值（给钱的事都是达到目的后越少越好）。注意 并不是所有的边都会出钱，因为点一旦具备保护（覆盖）能力后，与其相邻的所有边均被保护（覆盖），从上面的图也能看出。
网友评论