第9章算法试卷.ppt

* 9.4.4 集合覆盖问题的近似算法 集合覆盖问题举例： 用12个黑点表示集合X。F={S1,S2,S3,S4,S5,S6,}，如图所示。容易看出，对于这个例子，最小集合覆盖为：C={S3,S4,S5,}。 * 9.4.4 集合覆盖问题的近似算法 集合覆盖问题近似算法——贪心算法 算法的循环体最多执行min{|X|，|F|}次。而循环体内的计算显然可在O(|X||F|)时间内完成。因此，算法的计算时间为O(|X||F|min{|X|，|F|})。由此即知，该算法是一个多项式时间算法。 Set greedySetCover (X,F) { U=X； C=?； while (U !=?) { 选择F中使|S∩U|最大的子集S； U=U-S； C=C∪{S}； } return C； } * 9.4.5 子集和问题的近似算法 问题描述：设子集和问题的一个实例为〈S,t〉。其中，S={x1，x2，…，xn}是一个正整数的集合，t是一个正整数。子集和问题判定是否存在S的一个子集S1，使得 。 * 1 子集和问题的指数时间算法 int exactSubsetSum (S,t) { int n=|S|； L[0]={0}； for (int i=1；i=n；i++) { L[i]=mergeLists(L[i-1],L[i-1]+S[i])； 删去L[i]中超过t的元素； } return max(L[n])； } 算法以集合S={x1，x2，…，xn}和目标值t作为输入。算法中用到将2个有序表L1和L2合并成为一个新的有序表的算法mergeLists(L1,L2)。 * 2 子集和问题的完全多项式时间近似格式 基于算法exactSubsetSum，通过对表L[i]作适当的修整建立一个子集和问题的完全多项式时间近似格式。 在对表L[i]进行修整时，用到一个修整参数δ，0＜δ＜1。用参数δ修整一个表L是指从L中删去尽可能多的元素，使得每一个从L中删去的元素y，都有一个修整后的表L1中的元素z满足(1-δ)y≤z≤y。可以将z看作是被删去元素y在修整后的新表L1中的代表。 举例：若δ=0.1，且L=〈10,11,12,15,20,21,22,23,24,29〉，则用δ对L进行修整后得到L1=〈10，12，15，20，23，29〉。其中被删去的数11由10来代表，21和22由20来代表，24由23来代表。 * 2 子集和问题的完全多项式时间近似格式 对有序表L修整算法 List trim(L,δ) { int m=|L|； L1=〈L[1]〉； int last=L[1]； for (int i=2；i=m；i++) { if (last(1-δ)*L[i]) { 将L[i]加入表L1的尾部； last=L[i]； } return L1； } 子集和问题近似格式 int approxSubsetSum(S,t,ε) { n=|S|； L[0]=〈0〉； for (int i=1；i=n；i++) { L[i]=Merge-Lists(L[i-1], L[i-1]+S[i])； L[i]=Trim(L[i],ε/n)； 删去L[i]中超过t的元素； } return max(L[n])； } * 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * 欢迎辞 * * 第9章 NP完全性理论与近似算法 * 学习要点 理解RAM，RASP和图灵机计算模型 理解非确定性图灵机的概念 理解P类与NP类语言的概念 理解NP完全问题的概念 理解近似算法的性能比及多项式时间近似格式的概念 通过范例学习NP完全问题的近似算法 （1）顶点覆盖问题； （2）旅行售货员问题； （3）集合覆盖问题； （4）子集和问题。 * 9.1 计算模型 在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定义该计算模型