算法分析与设计2007第c讲

《算法分析与设计2007第c讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第C讲上次内容：(1)什么是绝对近似算法，存储最多程序问题的多项式时间绝对近似算法。(2)背包问题和最大独立集问题都不存在绝对多项式近似算法。(3)近似算法，近似性能比。近似度。RA(I)=。RA(I)=(4)背包问题和装箱问题的近似度为2的近似算法。RA£2。实际上每个实例都有一个具体的近似性能比，但我们并不关心这个，而是关心一个界，使算法对每个实例求解都有近似性能比不超过这个界。绝对近似性能比：RA=inf{r³1

2、所有实例IÎDp,RA(I)£r}，可以找到r。找一个数r，所有实例近似性能比都比r小，r最小能小到多

3、少。渐进近似性能比：=inf{r³1

4、存在NÎZ+，对于满足OPT(I)³N的所有实例IÎDp,RA(I)£r}前面装箱算法不是最好，应该先装体积大的，后装体积小的。这样使用箱子数会少一点。到底能改进多少呢？所以改进算法：FD算法：(1)将物体排序，体积从大到小。w(a1)³w(a2)³…³w(an)，形成非降次序主次表L={a1,a2,…,an}。(2)按照表L的顺序，以次装入箱子，直到装完为止。所用箱子数即为解。定理7.6：对于装箱问题任意实例I，非降次序主次表L，FD算法的近似性能比为：FD(I)£第15页第C讲存

5、在足够大的实例I，FD算法的性能估计：FD(I)³由此可以说明：+e。基本锁定渐进近似性能比了。这个定理不证了，只举个例子。说明渐进近似性能比为11/9。例1：L={a1,a2,a3,a4,a5,a6,a7}w(a1)=，w(a2)=w(a3)=，w(a4)=，w(a5)=w(a6)=w(a7)=A11/2+ea21/4+2eA41/4+e最优解a31/4+2e最优解A71/4-2ea51/4-2ea61/4-2eFD解另外一个例子:，30m个物体，体积如左。1/4-2e1/4-2e1/4-2e1/4+e1/4-2e1/

6、4+2e1/4+e1/4-2e第15页第C讲1/2+e1/4+2e1/2+e1/4+e1/4-2e1/4+2e1/4+e1/4-2e6m3m6m2m3mRFD(I)=11/9,RFD³11/9,，例子自己看吧。举例子很重要，研究的基本手段。§7.2：近似算法设计满足三角不等式的货郎问题：实例：城市集合C={c1,c2,…,cm},城市之间距离：d(ci,cj)ÎZ+,d(ci,cj)+d(cj,ck)³d(ci,ck),"ci,cj,ckÎC。相当于给定满足三角不等式边长的图G。将城市看成图G的点，G=(V,E)，V={

7、v1,v2,…,vm}询问：求城市排列：cp(1),cp(2),…,cp(m)，满足条件：旅游长度最短。*什么是欧拉图：每个点的度数为偶数。*任意图的性质：奇数度的点的个数为偶数个。*欧拉回路多项式时间可解的。走遍所有边但边不重复的点序列。点允许重复。第15页第C讲欧拉回路:acbcdedgfghgdca抄近路：acbdegfhaÞacbdegfha算法：MST(minimumspanningtreealgorithm)step1对G调用最小生成树算法得到树T(V,ET)。step2复制T的每条边得到欧拉图D(V,ED)

8、step3在D中求欧拉回路vp(1),vp(2),…,vp(k),…,vp(2m-2)vp(1)。step4抄近路得到货郎旅游vt(1)=vp(1),vt(2),…,vt(k),…,vt(m)vt(1)定理：RMST<2。证明：(1)w(T)

9、更小的数了。l就说算法A的近似度为C，C通常是一个常数，就叫常数近似算法。第15页第C讲lC有时也不一定是常数，现在有各种类型的近似算法。有时是一个与n有关的函数，如logn，或ne。l有时可以证明不存在RAC1，则人们开始找比C更小的多项式时间近似算法。下面改进近似度2。原来：<2。主要改进第二步。前面性质：T中度数为奇数的点的个数为偶数个。偶数个也不会超过所有顶点的个数。实际上不用复制每条边得到欧拉图，只需要加上一半条数的边就能形成欧拉图。求最小对集就行，能量最小的配对，权值最小，给

10、定带权的图，和图中偶数个点，求图中权最小的顶点对集是多项式时间可解的。将前面的第2步改为：2.1：设树T的奇度数点为v1,v2,…,v2t，在G中求点集{v1,v2,…,v2t}的最小对集Ep={e1,e2,…,et}ÍE。ei=(vi[1],vi[2])。这是多项式时间可解的。2.2：将Ep加入到T中形成欧拉图T1