算法分析与设计2007第b讲.doc

第B讲上次内容：(1)什么是拟多项式算法PESEUDO polynomial，在考虑问题实例描述的两个参数，MaxI，LengthI。(2)什么是拟多项式变换，什么是数问题。(3)什么是强NPC问题，限制数不很大时也很难解。数值参量受限时亦为NPC的。(4)什么是NP-hard问题。Turing规约。神喻图灵机。(5)NPC问题对应的优化形式都是NP-hard问题。很多问题具有与NPC问题同样的复杂度，但不是NP问题，用图灵规约，可以把这些问题统一起来。图灵归约：p1p2，要说明若p2有多项式时间求解算法，则p1也有多项式时间求解算法。设求解p2的算法为A2。有一个将p1实例转换为p2实例的变换f：If(I)。设计求解p1的算法A1(I)，其中调用A2(f(I)，(1)若A2(*)能求得满足条件的解，则A1(*)求得的解也满足条件。(2)若A2(*)时间复杂度为O(1)，则A1(*)时间复杂度是多项式时间复杂度。实际可以假设A2(f(I)的计算不需要时间。这样就叫p1图灵归约到p2，图灵规约是多项式变换的推广。若p1能图灵规约到p2，则p2就不必p1容易。仔细解释，难：不存在多项式算法易：存在多项式算法若p1 T p2则p1 难p2也难，p2易p1也易，p1 易p2难易均可能。NP-Hard的定义：一个问题是NPC的，则该问题推广称为NP-hard问题，若p1是NP-hard问题，p1可以图灵归约到p2，则p2也是NP-hard问题。TSP优化问题：实例：城市集合C=C1,Cm，城市之间距离d(Ci,Cj)，询问：求城市排列：,，使=min|Cp1Cp2Cpm为城市排列定理：TSP优化问题是NP-hard。证明：TSP判定问题图灵归约到TSP优化问题。TSP判定问题是NPC，所以是NP-Hard。l 设存在TSP优化问题求解算法A，设计tsp判定问题的算法如下：1对于给定TSP判定问题的给定实例：G,d,K，调用A(G, d)，求得城市排列：，2若K，则回答yes，否则回答No。若A是多项式算法，则上述算法能够在多项式时间解答。所以TSP优化问题是NP-hard问题。货郎延伸问题实例：(1)城市集合C=C1,C2,Cm，(2)任意两个城市之间的距离d(Ci, Cj)Z+，(3)正整数界值BZ+，(4)C中K个城市的部分旅游Q=询问：能否将Q延伸为一个长度不超过B的全程旅游回路： Cp(1), Cp(2), , Cp(k), Cp(k+1), , Cp(m), Cp(1)定理：货郎延伸问题是NP-hard。证明：将货郎优化问题图灵归约到货郎延伸问题。设计货郎判定算法如下：折半法。假设货郎延伸问题算法为：SC, d, , Bmid1 Bmin=m; Bmax=m*maxd(ci,cj)|ci,cjC/最大就这么大。2若Bmax-Bmin=0，则B*=Bmin，暂停。3 Bmid=(Bmin+Bmax)/2; 4调用子程序：SC, d, , Bmid，若回答yes，则Bmax=Bmid转2，否则Bmin=Bmid，转2。/最优解值为B*，最优解怎么求？SC, d, , B*，SC, d, , B*， ，SC, d, , B*由此确定Cp(2)SC, d, , B*，SC, d, , B*， ，SC, d, , B*由此确定Cp(3)5 Cp(1)=C1,6 for i=2 to m do for j=1 to m do若CjC1,Cp(2),Cp(i-1)且SC,d,B*回答yes，则Cp(i)=Cj。没有判定货郎延伸是否NP，但是已经将货郎判定问题图灵归约到货郎延伸。这样最后求得C1, Cp(2), , Cp(i-1), Cp(m)，为最优解。还有第k个最大子集问题是NP-Hard，证明自己看。第7章：近似算法和概率算法只讲近似算法，不讲概率算法。搜索问题，就是求解，求满足条件的解，不再是判定问题了。含义：虽然不能得到最优解，但能离最优解不远。达不到最好，力争更好。7.1：近似算法及其性能评估符号：p，Dp，IDp，求解的目标是最大化或最小化的优化问题。询问时要求解，按照解的格式，并满足解的条件。Sp(I)：可行解集，现在不求最优解了，只要符合解的格式就叫可行解。Mp(I,S)：对于IDp, SSp(I)，表示解值，解的数值。总是用一个数值衡量解的优化程度。S*Sp(I)：表示最优解，显然有：Mp(I,S*) Mp(I,S)，最小优化问题。Mp(I,S*) Mp(I,S)，最大优化问题。通常用OPTp(I)= Mp(I,S*)表示最优解值。通常将实例I的最优解的解值记为：OPT(I)。假设有算法A，对于任意实例I都能找到最优解，A(I)=OPT(I)，则称算法A为求解问题p的精确算法。也有很多问题能够求得最优解。有时总也求不到最优解，可以求出一个解，解的格式符合规则，但不能保证求到最优解，求出的解只是可行解。定义：给定问题p，若有算法A，存在一个常数K0，使得所有实例IDp，总有：|A(I)-OPT(I)|K则称算法A为解答问题p的绝对近似算法。若A为多项式时间算法，则称A为解答问题p的多项式时间绝对近似算法。已知当PNP时，NP-hard优化问题不存在多项式时间算法，但其中有些问题存在多项式时间绝对近似算法。存储最多程序问题：实例：n个程序，每个程序的存储容量分别为：L1,Ln。两个磁盘，存储容量都是L。询问：若不允许一个程序同时存在于两个磁盘内，求两个磁盘最多能存储程序的个数。这个问题是NP-hard，将划分问题图灵规约到该问题就能证明。现在设计一个算法：(1)对n个程序，按其存储容量的非增顺序排序，L1L2Ln。(2)按程序编号从1到n，依次向磁盘1存放程序，直到磁盘1放不下为止，再转向存储磁盘2。直到磁盘2不能存放为止。*这个算法的时间复杂度为O(nlogn)定理7.1：设I是存储最多程序问题的任意实例，OPT(I)为其最优解的解值，A(I)为算法A所求出的解的解值，有：|OPT(I)-A(I)|1。即算法A为多项式时间绝对近似算法。证明：考虑一个容量为2L的磁盘，按照L1,Ln的顺序存入磁盘可以存p个程序。OPT(I) p。，两个磁盘按照前面算法：最少可以存储p-1个程序。所以：|A(I)-OPT(I)|1。放的程序越多越好，所以先放小的，后放大的。并不是所有NP-hard问题都有多项式时间绝对近似算法。最小度生成树问题，只讲什么问题，自己看吧。这个图的最小度生成树是什么？局部搜索算法可使所求解达到所能达到最优解的值加1。定理7.2：当P NP时，背包问题没有多项式时间绝对近似算法。证明：背包问题的优化形式：背包优化问题。只要一个界，背包容量，价值最大化，就是背包优化问题。设背包问题存在多项式时间绝对近似算法A，则存在常数K，使对背包问题的任意实例I：有，|A(I)-OPT(I)| K。令p1i=(K+1)pi将背包问题实例变换为另一问题实例I1：根据假设有：|A(I1)-OPT(I1)|K又有：OPT(I1)=(K+1)OPT(I)所以：，可以认为A(I1)是K+1的整数倍。A(I1)(K+1)OPT(I)由于背包问题的实例中，每个元素的价值均为正整数，所以OPT(I)=，由此可以得到最优解值，这样背包判定问题就可以解决了。与PNP矛盾。可以假设A(I1)是K+1的整数倍。定理7.3：若PNP，则最大独立集问题不存在多项式时间绝对近似算法。证明：设最大独立集问题的实例为G，有绝对近似算法A，使得：|A(G)-OPT(G)|K，构造最大独立集问题另一实例G：G由图G复制K+1个副本组成。显然有：OPT(G)=(K+1)OPT(G)对于新构造的G调用算法A得到：|A(G)-OPT(G)|K，得到实际上可以假设A(G)一定K+1的倍数，解释为什么。OPT(G)=，可以求到G的最优解值。与PNP矛盾。绝大多数NP-hard问题不存在多项式时间绝对近似算法。绝对近似算法没大有意义，存在绝对近似算法的问题实在太少。定义7.1：l p最小优化问题，实例I，解答p的近似算法A，则算法A对实例I的近似性能比定义为：RA(I)=，基本假设：A(I)OPT(I)Approximation ratioPerformance ratioPerformance factorl 若p最大优化问题，实例I，解答p的近似算法A，RA(I)=，基本假设：A(I)OPT(I)。显然这样定义后，不论最大优化还是最小优化，近似性能比总比1大。近似性能比越接近1越说明算法好。背包问题：定理7.4：背包问题有多项式时间近似算法，任意I近似性能比RA(I)2。证明：设计一个算法：思想，价值重量比大到小排序。(1)将A中的元素排序，按照性能价格比。(2)从一开始装入背包，直到不能装下为止，得到可行解GA(I)。(3)A(I)=maxGA(I),maxPi|i=1,n/考虑最大价值的装法得Pi设正整数r满足：，显然a1,ar是装入背包的物体。OPT(I) 所以RA(I)=2装箱问题：实例：(1)n个物体的集合：S=a1,an，(2)每个物体aiS，体积为：w(ai)。(3)容量为C的箱子。询问：最少需要多少个箱子，才能将S中物体都装入箱子内。每个箱子装入物体的体积和不超过C。首次适合算法最简单：fit-first(1)设箱子为：B1，Bm，按照一定顺序将a1，an依次装入箱子，一个箱子装满再装另一个箱子。这就是算法。算法的时间复杂度为O(n)，算法的名字叫FF。算法的想法就是吓装，拿过来就装。定理7.5：对于装箱问题的任意实例，首次适合算法的近似性能比为：RFF(I)=2。证明：任意两个相邻箱子Bi-1Bi装入物体体积大于C。B1B2B3B4BkK=FF(I)，若FF(I)为偶数，则，两个箱子合一个，装入的东西会有富裕。所以FF(I) 2OPT(I)若FF(I)为奇数，FF(I)r，使对任意I，有RA(I)r1，对r2r，对任意I，有RA(I)r2，？RA=infr1|所有实例IDp, RA(I)r找一个数r，所有实例近似性能比都比r小，r最小能小到多少。渐进近似性能比： = infr1|存在NZ+，对于满足OPT(I) N的所有实例IDp, RA(I) r装箱的首次适合算法还不够好。凭感觉，应该先装体积大的，后装体积小的。这样使用箱子数会少一点。所以改进算法：(1)将物体排序，体积从大装到小。先大后小算法。w(a1)w(a2)w(an)，形成非降次序主次表L。(2)按