算法设计与分析笔记之近似算法

关注
算法设计与分析笔记之近似算法www.shan-machinery.com为什么使用近似算法

无法找到一个NP难问题的多项式时间普适算法,因此我们思考牺牲算法的精确度,以在可计算时间内找到一个近似解。对于一个近似算法,满足:

在多项式时间内完成具有普适性(能解决这类问题的任何实例)有一个确切的近似程度(准确解的多少倍)

找一个NP难问题的近似算法,只需要证明其近似程度(多少倍地接近精确值),而不用知道这个精确值究竟是多少。

近似算法举例Ⅰ. 负载均衡问题

m台相同的机器,n个不同的工作及完成它所需的时间t_{j},问满足如下条件的最短工作时长。

一个工作必须连续执行直到完成;一台机器一次只能处理一个工作。2倍近似算法——List Scheduling

List Scheduling 是一种贪心策略,它的核心思想是将各个工作依次安排到累计工作时长最短的机器中,下面的动图显示了这一过程。可以发现,这种贪心的初衷只考虑了眼前的最小值,而局部最优解并不一定是最终的最优解。

LS算法fail

我们假设完成所有工作的最短工作时长,来自第i台机器L[i],证明前,先确定两个结论。设完成所有工作的最短时间跨度(makespan)为L^{*},结束时各台机器的时间跨度为L_{i},有:

L^{*}≥max(t_{j})L^{*}不小于完成最长的工作所需时间L^{*}≥\frac{1}{m}\sum_{j}^{n}t_{j}L^{*}不小于总工作时长的\frac {1}{m}(机器平分工作)

设最后一个加入到第i台机器运行的是工作j(注意:不一定是所有工作的最后一个),那么有          \qquad\qquad\ L_{i}-t_{j}≤\frac{1}{m}\sum_{k}^{m}L_{k}       ①              \qquad\qquad\ =\frac{1}{m}\sum_{k}^{n}t_{k}         ②              \qquad\qquad\ ≤L^{*}          ③

所以L_{i}=(L_{i}-t_{j})+t_{j} ≤ 2L^{*}

3/2倍近似算法——LPT Rule

上述贪心策略存在一个很明显的漏洞,当最后加入的工作所花时间最长时,效果很差,直逼2倍TT。因此我们希望先安排长工作,将所有工作按花费时间降序排列,再执行上述贪心算法,这就是LPT(Longest Processing Time) Rule的核心思想。当n≤m时,则每台机器最多安排一个工作,容易找到最优解。当n≥m时,先将m个工作安排到m台机器,那么对第m+1个工作,有2t_{m+1}≤L^{*}. 则对③,L_{i}=(L_{i}-t_{j})+t_{j} ≤ 2/3L^{*}

Graham在1969年,计算出LPT Rule是负载均衡问题的一个4/3近似算法。太复杂了,老师都放弃了···

Ⅱ. 中心选择问题

给定平面(或空间)上的n个点和中心个数k,问如何放置这k个中心,使得所有点被以这k个点为中心的圆盘覆盖且最大的圆盘半径最小(不是所有圆盘的半径之和)。对所有点,被相距最近的中心点形成的圆盘覆盖。

贪心策略——依次选择离其中心最远的点为新的中心

因为中心选择的目标是最小化离其中心最远的点与该中心的距离,所以每次加入新的中心时,直接贪心选择这样离其中心最远的点。依次选择离其中心最远的点为新的中心,这样的贪心算法是一个2倍近似算法。设集合CC^{*}分别是贪心算法和真实的最佳中心,r(C)r(C^{*})分别是贪心算法和真实情况里离中心最远的距离(最小覆盖半径)。需要证明结论r(C)≤2r(C^{*})      dist(s, C)≤dist(s, c_{i})≤dist(s, c_{i}^{*})+dist(c_{i}^{*}, c_{i})≤2r(C^{*})

Ⅲ. 带权点覆盖问题

对于点覆盖问题(一个点的集合使得图中所有边至少有一个端点在集合内),带权点覆盖问题中,需要满足这个集合中所有点的权值之和最小。

竞价法是带权点覆盖问题的2倍近似算法

竞价简单理解为边给相邻的点支付保护费,以保证自己能被至少一个点保护(覆盖);而点收到来自各条相邻边支付的保护费之和刚好是它的权值,才能保护它们。这样,那些收到保护费刚好是自身权值的点构成一个顶点覆盖。下面证明用竞价法是带权点覆盖问题的2倍近似算法。引理 对于任意点覆盖S和边e给出的价格P_{e},有\sum p_{e}\leq w(S).可通过两个恒等变换简单证明,因为很多点共用了边支付的价格,所以一定有所有点给出的竞价不大于点覆盖权值之和。

竞价法过程

选出还未被保护的边,提最少的价使得其相邻点至少有一个能保护它,这些能保护(覆盖)临近边的点称其为紧(tight)的,将其加入点覆盖集合。循环操作,直至所有边都能被保护。伪代码如下:

竞价法算法流程

竞价法求解点覆盖问题,举例如下:

竞价法过程

上图中,最后tight的点{a, b, d},即为最小的带权点覆盖,权为10. 注意:边给出的竞价之和不是点覆盖的权。

竞价法2倍近似的证明

设最优点覆盖S^{*}和竞价法获得的点覆盖S,有w(S)≤2w(S^{*}).      w(S)=\sum_{i\in S}W_{i}=\sum_{i\in S}\sum_{e=(i,j)}p_{e}\leq \sum_{i\in V}\sum_{e=(i,j)}p_{e}=2\sum_{e\in E}p_{e}≤2w(S^{*})

倒数第二个恒等变换的依据是每条边计算了两次,最后到w(S^{*})的放缩依据是,每条边给出的价格不大于其任一相邻点的权值(给钱的事都是达到目的后越少越好)。注意 并不是所有的边都会出钱,因为点一旦具备保护(覆盖)能力后,与其相邻的所有边均被保护(覆盖),从上面的图也能看出。

https://www.shan-machinery.com