一、近似算法的概念
1、为啥要研究近似算法?
目前大规模的NPC问题我们无法通过计算得到,因此我们需要通过损失一部分精度的做法来找到多项式的近似算法。
2、近似算法精度的评价
用近似算法得到的解与原问题的最优解比值不超过ρ,则称该算法是ρ−近似算法。难点在于在不知道最优解的情况下证明近似解与最优解的近似程度。
二、几个经典的近似问题
1、负载均衡问题
负载均衡问题:给出m个机器,n个任务,设任务j处理时长为tj。要求如下:
- 每个任务只能在一个机器上不间断的完成
- 每个机器不能同时处理多个任务
设S[i]表示给机器i处理的任务集合,则机器i的处理时长为L[i]=∑j∈S[i]tj。负载均衡问题的目标就是 找到一种任务分配方案使得min(max(L[i])),即让每个机器处理的任务的时长尽可能均衡。
这个问题是NPC问题,因为Partiton问题≤P负载均衡问题。
近似策略1
贪心策略:每次在机器中选出当前处理时长最短的机器处理下一个任务。时间复杂度为O(nlogm),对于每个任务都需要从m个机器中选出处理时长最短的机器,这个用优先队列维护即可。这个近似算法是2-近似的,证明如下:
-
引理1:设最优解为L∗,则L∗≥maxjtj,因为至少一个机器要处理一个任务,所有任务中花费时间最长的任务所需时间为maxjtj,故得到此不等式。
-
引理2:L∗≥m1∑jtj。当每个机器处理任务的时长相同时L∗=m1∑jtj,显然其他情况下L∗>m1∑jtj。
- 假设最后一个任务j给了机器i,说明在此之前,机器i的负载时长最小,即L[i]−tj≤L[k](对任意k满足1≤k≤m)。
- 因为对任意一个机器k都满足L[i]−tj≤L[k],因此m(L[i]−tj)≤∑kL[k],即L[i]−tj≤m1∑kL[k]=m1∑jtj≤L∗(引理2)
- 到这里,该近似算法求解的结果L=L[i]=(L[i]−tj)+tj≤L∗+L∗=2L∗,即L≤2L∗,该贪心策略是该问题的2-近似算法。
该近似算法能达到最优解的2倍吗,即上述不等式是紧的吗?是紧的!
近似策略2
策略2:将任务按照处理时长tj从大到小排序,之后再每次在机器中选出当前处理时长最短的机器处理下一个任务。时间复杂度为O(nlogn+nlogm)。这个近似算法是23−近似的,证明如下:
-
引理3:假设有m个机器,超过m个任务,这些任务按照处理时长排好序,t1≥t2≥⋯≥tm+1≥⋯,则显然某个机器上至少要处理两个任务,则最优解L∗≥2tm+1。
- 从近似策略1的推导可以得到L=L[i]=(L[i]−tj)+tj,假设机器i上至少有2个任务,则利用引理3可得tj≤21L∗,故L≤23L∗,该策略是该问题的23−近似算法。
该近似算法能达到最优解的23倍吗,即上述不等式是紧的吗?不是紧的!
2、中心点选择问题
问题描述:给出n个点s1,⋯,sn,从中选出k个点C,设每个点到最近的中心点C的距离为di,问采取何种策略选出这k个点使得r(C)=max(di)最小。这个问题是NPH问题。
贪心策略:初始时随机选一个点作为中心点,之后的k−1次,每次遍历除已选做中心点的其他点,找出与该点距离最近的某个中心点计算出距离dj。最后在这些点中找出maxjdj对应的点作为下一个中心点。这个近似算法是2-近似的,证明如下:
- 设C∗是最优解对应的中心点,C是用上述贪心算法选出的中心点,则r(C)≤2r(C∗)。
3、带权顶点覆盖问题
图的每个顶点都有权重,找一个图的顶点集合能覆盖所有的边,问如何选择顶点使得这些顶点的权重和最小。用竞价法去近似求解。
- 对于某个顶点i,其权重为wi,与该顶点相连的边记为p,给这些边赋值权重,使得∑e=(i,j)pe≤wi。
- 设S为任意一个集合覆盖,则∑epe≤∑i∈S∑e=(i,j)pe≤∑i∈Swi=w(S),故∑epe≤w(S)。
- 算法流程:对于图中任意一条边e=(i,j),令pe=0,当i,j顶点的∑e=(i,j)pe<wi,∑e=(i,j)pe<wj时,增加pe直到满足∑e=(i,j)pe=wi或者∑e=(i,j)pe=wj。这时候相等的那个顶点放入S中。
- 竞价法是2-近似算法,证明如下: