算法分析与设计2009第e讲

《算法分析与设计2009第e讲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上次内容：(1)图着色不能多项式时间近似到小于，TSP问题不能多项式时间近似到任意常数。(2)，时间复杂度O(mK+nlogn)，K越大求解优化程度越高，1+e，T=O()。M是常数时可以认为是多项式时间近似方案。(3)背包问题：1+，时间复杂度：O(nK)。什么是多项式时间近似方案：定义7.2：若问题p的近似算法A(e)满足，对任意实例I任意e>0(1)RA(e)[I]<1+e；(2)A(e)的时间复杂度是I输入长度的多项式函数。则A(e)称为求解问题p的多项式时间近似方案。解释：(1)1+e很容易说明，但后面的多项式需要解释,时间复杂度一定与e有关。近似

2、性能比1+e，时间复杂度为：O()，O(n)，O(n2)，PTAS。特殊情况：O()等等，各种情况。一定是e越小，时间复杂度越大。最后一种情况又称为完全多项式时间近似方案。FPTAS完全多项式时间近似方案：近似性能比：1+e；时间复杂度：P(n,)，P(·,·)是多项式函数。(2)为什么叫多项式近似方案，而不叫多项式近似算法。因为e没有确定大小，只有程序运行时才能确定。下面讲完全多形式时间近似方案。背包问题：整数规划形式。算法描述，先考虑动态规划算法求背包问题最优解算法要求x1,x2,…,xn的赋值，赋值为1的为装入背包的，赋值为0的为没有装入背包的。最后使

3、装入背包的元素价值最大，重量不超过M。先考虑前i个元素的装法，要考虑(x1,x2,…,xi)赋值的组合：每种组合对应一个价值和重量数对：，Pil=，Wil=用一个数对表示一种装法。S(i)={,…,}表示所有这样的数对集合，按说共有如此数对2i个。但是可以去掉一些，实际上有些数对可以去掉。并不是所有数对均有前途成为最优解，只保留有前途的数对即可，有一些是没有前途的通过比较可以看出来。l两种情况：看哪些数对可以去掉，不考虑。(1)若有数对，Wil>M，则该数对没有必要存在，

4、>ÏS(i)(2)若有两个数对,满足：Pil£Pik,Wil³Wik一种装法重量大价值小，另一种装法重量小价值大，后一种更好，更有发展潜力，再往包里放时不再放前i个元素中的元素了。为什么可以去掉？因为开始好以后也好。没有潜力发展的数对没有必要保存。看看数对有没有前途，没有前途就淘汰了。在所有有前途的数对中培养出最优解来。前面的关系“Pil£Pik,Wil³Wik”称支配，若支配则，将被支配的数对从S(i)中去掉。l下面看若S(i)构造出来以后，怎样构造

5、S(i+1)S(i)为所有有前途的数对集合。(1)若xi+1=0，则S(i)ÌS(i+1)//前i个元素可以，前i+1个元素也可以。(2)若xi+1=1，则={

6、ÎS(i),Wi+1+Wt£M}S(i+1)=S(i)È{被其他数对支配的数对},1£i为最后一个数对，若ÏS(n-1)，则xn=1，否则xn=0。xn=1时考虑数对ÏS(n-2)，以此反向追踪得到(xn,xn-1,…,x2,x1)，得到背包

7、问题最优解。例子：P=(P1,P2,P3,P4,P5)=(W1,W2,W3,W4,W5)=W=(1,2,10,100,1000)M=1112,因为每个元素价值与重量相等，所以就不用考虑数对了，只考虑一个数。S(0)={0}S(1)={0,1}={2,3}S(2)={0,1,2,3}={10,11,12,13}S(3)={0,1,2,3,10,11,12,13}={100,101,102,103,110,111,112,113}S(4)={0,1,2,3,10,11,12,13,100,101,102,103,110,111,112,113}={1000,10

8、01,1002,1003,1010,1011,1012,1013,1100,1101,1102,1103,1110,1111,1112,1113(删除)}S(5)=S(4)È={0,1,2,3,10,11,12,13,100,101,102,103,110,111,112,113，1000,1001,1002,1003,1010,1011,1012,1013,1100,1101,1102,1103,1110,1111,1112}求出该实例的解数对为：<1112,1112>，反向追踪得到最优解(x1,x2,x3,x4,x5)=(0,1,1,1,1)。算法复杂度

9、分析，算法很坏，但是可以化腐朽为神奇。(1)O()=