算法设计练习题(共7页).doc

精选优质文档-倾情为你奉上算法设计练习题一. 计算复杂性1 P184 10.3 设计一个多项式时间的算法判断一个无向图G是否是2可着色的算法：2-COLORING输入：无向图G(V, E)输出：该图是2可着色的，则输出yes；否则，输出no.1. 取任一节点，标记为白色2. 所有与它邻接的节点标记为黑色3. 对任意已标记的节点v，将所有与v邻接且未标记的节点标记为与v相反的颜色4. 重复步骤3，直到不存在与已标记节点邻接且还未标记的节点5. 如果图中还有未标记的节点，那么这些节点一定在一个新的连通分量中，再选 择其中一个节点标记为白色，转到步骤36. 如果得到的图中，所有邻接的节点都标记为不同的颜色，则输出yes；否则，输出no.End 2-COLORING 时间复杂度分析：在n个顶点和m条边的图上进行分析，算法的运行时间是2 P185-186 10.16 团集问题的NP完全性是由可满足性问题归约到它证明的，给出一个从顶点覆盖到团集的较简单的归约法1：规约方法：设G=（V，E）是连通无向图，SV是一个团集当且仅当是中的一个顶点覆盖。证明：设e=(u,v)是G中的任意边，SV是一个团集当且仅当u和v都在S中，即是中的一个顶点覆盖。法2：证明：设G=（V，E）是连通无向图，SV是G中的一个独立集，则S是的一个团集，独立集poly团集。因为顶点覆盖poly独立集，根据定理10.3，顶点覆盖poly团集。3 P185-186 10.26 用顶点覆盖问题规约到集合覆盖问题，证明集合覆盖问题是NP完全问题。证明：第一步是说明集合覆盖问题是NP的。因为一个不确定性算法可以从猜测一个集合X的子集族F开始，然后验证是否存在F中的k个子集的并是集合X。第二步证明顶点覆盖问题可以在多项式时间内规约到集合覆盖问题。设任意连通无向图G=(V,E)，集合X为G中所有与边相邻的顶点的集合，其子集族则是每个顶点与其相邻的顶点构成的子集。集合X是满足集合覆盖的当且仅当X的子集族中存在k个子集的并是X，当且仅当G中存在大小为k的顶点覆盖。4 P215 12.16 证明：设x1,x2,xn是一个正实数集合。对于每一个实数xi，我们使它和二维平面中的点 (x1,1),(xj,0) | j2,n 相联系，这样，所构造的n个点都位于三角形边上。如果我们用TRIANGULATION问题的任何算法求解构造的实例，输出将是根据它们的x坐标排序的构造点的表，遍历表并读出每点的第一个坐标，结果是排序好的数。所以，排序问题规约到TRIANGULATION问题，排序问题是(n logn)，TRIANGULATION问题也是(n logn)。5 P215 12.17 证明：设x1,x2,xn是一个升序排列的正实数集合，及实数x。对于实数x及每一个实数xi，我们使它和二维平面中的点(x,0),(xi,0) | i1,n 相联系，这样，所构造的点都位于x轴上。如果我们用NEAREST POINT问题的任何算法求解，输出就是二分搜索要查找的数。所以，二分搜索问题规约到NEAREST POINT问题，二分搜索问题是(logn)，NEAREST POINT问题也是(logn)。6 P215 12.18证明：设x1,x2,xn是一个正实数集合，对于每一个实数xi，我们构造点(xi,0)与之对应，于是这些点在x轴上。如果我们用ALL NEAREST POINT问题的任何算法求解，输出将是每个点(xi,0)对应的最近点对(xi,0)，(xj,0)。所以，CLOSEST-PAIR问题规约到ALL NEAREST POINT问题，CLOSEST-PAIR问题是(n logn)，ALL NEAREST POINT问题也是(n logn)。二. 随机算法1 P241 14.2 假定你有一枚硬币，请设计一个有效的随机算法用来生成整数1,2.n的随机排列，n为正整数，分析你的算法的时间复杂性。基本思想：从空序列开始，逐个向序列添加1, 2, , n。根据二分搜索的思想，并利用多次抛硬币，来随机确定每个添加的数在序列中的位置。算法 RANDOMIZE2 输入：正整数n 输出：1, 2, , n的一个随机排列。 A1=1 for i=2 to n j=randombisearch(1, i-1)/在数组A中随机确定i的插入位置。 insert(A , j, i) /在数组A的j位置上插入值i。 end for output A1.n end RONDOMIZE2 过程 randombisearch(low, high)/ 利用二分搜索在Alow.high+1中随机确定值i的插入位置，/ 并返回该位置。if low>high then return lowelse mid= k=random(1,2) /抛一次硬币。 if k=1 then high=mid-1 /插入位置在Alow.mid中。 else low=mid+1 /插入位置在Amid+1.high+1中。 return randombisearch(low, high)end if end randombisearch时间复杂性：(n2) 2 P241 14.5 在算法RANDOMIZEDQUICKSORT的讨论中曾说过，为算法QUICKSORT得到一个O（log n）期望时间的一种可能性，是通过排列输入元素使它们的次序变成随机的来获得的。描述一个O（n）时间算法，先随机排列下算法思想：对预排序的数组进行随机排列，使该数组与原先相比显得无序。尽量避免QUICKSORT算法最坏情况的发生即n2时间，使之更趋近于最佳情况nlogn时间。算法PRE_DISPOSE输入：n个元素的数组a1n输出：随机排列的数组a for i=1 to n P =random(n)/随机选择小于n的数 Q=random(n) /随机选择小于n的数 互换aP和aQ end forend PRE_DISPOSE3 P241 14.7 考虑对算法BINARYSERCH做如下修改见1.3节，在每次迭代中，随机的选择剩下的位置来代替搜索区间减半设元素存储在一维数组C中，第0个位置不放元素，若每次生成的随机数都是要查找的剩余元素的第一个且未找到要搜索的数，则时间复杂度计算公式如下：计算得到时间复杂度为4 写出n皇后问题的如下随机算法：先在棋盘上随机放置m(m<n)个互不冲突的皇后，然后用回溯法搜索其余皇后的位置。算法 NQUEENS_RAN_ACCU输入：正整数n,m，其中n表示棋盘纬度，m表示随机算法和回溯算法的处理的 划分， m<n。输出：若找到解，则输出n皇后问题的一个解x1.n,否则输出无解Flag_Random=true /随机查找时是否有解得标记Flag_Accu=false/精确查找时是否有解得标记k=1 xm+1=0/精确查找初始化while k<=n and Flag_Random if k<=m/随机算法 j=0for i=1 to n /寻找第k行所有可放置皇后的位置。 if place(k) then /若第k行的位置i可放置皇后, j+; tempj=i; /则存储该位置。 end if end for if j>0 then xk=temprandom(1, j) /随机选取一个位置放皇后 else Flag_Random =false/表示找不到解 end if k+ else if k>m/回溯算法 while k>m and not Flag_Accu while xk< n and not Flag_Accu xk=xk+1 /试将第k行的皇后移到下一个位置。 if place(k) then /第k行的当前位置可放置皇后。 if k=n then Flag_Accu =true /xm+1.n是一个解 else /xm+1.k是精确解答时的部分解 k=k+1 /前进到下一行 xk=0 end if end if /否则，剪枝 end while k=k-1/回溯 end while if k =m break; /退出整个循环 end ifend whileif Flag_Random and Flag_Accu then output x /输出一个解 else output “No solution”/输出无解三. 近似算法1 对于装箱问题，分别写出近似算法FF和BF。思路:1.最先适配法(FF)：箱子编号为1, 2, , n，初始时各箱子为空。各项按u1, u2, , un的顺序装箱，装项ui时，将其装入序号最小的可容得下该项的箱子中（即装入满足l<= 1-si的序号最小的箱子中，其中l表示箱子的已填充容量）。 2.最佳适配法(BF)：箱子编号为1, 2, , n，初始时各箱子为空。各项按u1, u2, , un的顺序装箱，装项ui时，将其装入满足l<= 1-si并且使l值最大的箱子中。算法FF输入: n个项的集合u1n, n个箱子的容量l1n，其中0<=ui<=1，li=1.输出: 装这n个项的最少箱子的个数k k=1;/箱子的个数 for i=1 to n/装项ui时，将其装入序号最小的可容得下该项的箱子中 j=1 flag=false; while j<=k and not flag/从序号最小的开始查找 if lj>ui then/找到可以放进去的箱子 lj=lj-ui flag=true; else j+/继续寻找 end if end while if not flag then/没有找到可以放进去的箱子 k+/开启新的箱子 lk=lk-ui; end if end for return kend FF算法BF 输入: n个项的集合u1n, n个箱子的容量l1n，其中0<=ui<=1，li=1. 输出:装这n个项的最少箱子的个数k k=1;/箱子的个数 for i=1 to n/装项ui时，将其装入满足l<= 1-si的箱子中使l值最大的箱子中 if lj>ui then/找到l值最大的可以放进去的箱子 lj=lj-ui elsek+/开启新的箱子 lk=lk-ui; end ifsort(l1k)/对前k个箱子的l值从大到小排序 end for return k end BF2 P255 15.10V1V2如图：V3V4按照算法，先得到顶点的度数降序排列：V1、V2、V3、V4（度数均为2），先将V1添加到覆盖中，删除边 V1 ，V4和 V1，V2，接着添加V2，删除边 V2，V3，添加V3，删除边 V3，V4。故得覆盖 V1，V2，V3，而最佳覆盖为 V1，V3或 V2，V4。3 P256 15.14 15.15（这两题的答案是学长给的）15.14考虑在给定的图G中找出最大团集问题的近似算法，基本步骤：1、 C=2、 向C中添加一个顶点（该顶点不在C中，与C中每个顶点相连接）3、 重复步骤2，直到C=G 或者G-C中任一点x与C中点都不是全部相连Solution:这里取,。则题目算法寻求最大团集，这是最大化问题，近似度分三种情况讨论：若若是由个无向完全图：之简单并，则=。上式个顶对于不是由、讨论的无向图，则可以去掉一些边，这些边及跟这些边相连的顶点不构成图的完全子图，最后图分解成独立的“较小”的无向图（即团集）的简单并。转为讨论的情形。结论：这个近似算法可能达到的近似度具有如下形式：， =，。 1515证明练习15.14中给出的查找最大团集问题的启发式算法的近似度是无界的。证明：反证法：假定该启发式算法的近似度是有界的，则由于的任意性，构造如下：设是一个具有6个顶点的无向完全图，是 具有3个顶点的无向完全图，取,显然，且由于是近似算法，不可能输出的都是具有个顶点的团集,故而：导出矛盾！4 P256 15.16给出着色问题的一个近似算法:找出给一个无向图着色,使得相邻顶点着不同颜色的最少颜色数。证明或否定该算法的近似度是有界的算法思想：对无向图进行分类讨论算法：COLORING输入：无向图G(V,E)输出：着色的颜色数if V=0 then return 0 end ifif E=0 then return 1 end ifif G是二分图 return 2 end ifelse return 4end ifend COLORING证明：在上述算法A中，在V=0，E=0， G是二分图情况都属于最优解，所以其RA(I)=1;而只有else语句不是最优解，因为在else语句中出现的情况不是3可着色就是4可着色的，任何一个图形并不都满足3可着色，3着色是NP完全问题,但是任何一个平面图G都是4可着色的，所以这时我们返回4，即 A(I)=4, OPT(I)=3 RA(I)=A(I)/OPT(I)=4/3 所以1<=RA(I)<=4/3该算法的近似度是有界的得证5 P256 15.21证明只需找出一个反例即可。例 X = 1, 2, 3, 4, 5, 6, 7, 8 子集族F = 1, 2 2, 3, 4, 5, 6, 6, 7, 8 1, 2, 3, 4, 5, 6 , 7, 8, 已知最小覆盖只需两个即 1, 2, 3, 4, 5, 6 , 7, 8, 。但按照算法则先选择交集个数最大的子集 2, 3, 4, 5, 6, ，然后再在其余的选择两个比如 1, 2 ， 6, 7, 8 或者 1, 2, 3, 4, 5, 6 , 7, 8, 。该题给出的算法对例子的最小覆盖个数是3个。所以不总是产生最小覆盖。专心-专注-专业