算法设计练习题

算法设计练习题一.计算复杂性1．P18410.3设计一个多项式时间的算法判断一个无向图G是否是2可着色的算法：2-COLORING输入：无向图G(V,E)输出：该图是2可着色的，则输出yes；否则，输出no.1.取任一节点，标记为白色2.所有与它邻接的节点标记为黑色3.对任意已标记的节点v，将所有与v邻接且未标记的节点标记为与v相反的颜色4.重复步骤3，直到不存在与已标记节点邻接且还未标记的节点5.如果图中还有未标记的节点，那么这些节点一定在一个新的连通分量中，再选择其中一个节点标记为白色，转到步骤36.如果得到的图中，所有邻接的节点都标记为不同的颜色，则输出yes；否则，输出no.End2-COLORING时间复杂度分析：在n个顶点和m条边的图上进行分析，算法的运行时间是)(nm2．P185-18610.16团集问题的NP完全性是由可满足性问题归约到它证明的，给出一个从顶点覆盖到团集的较简单的归约法1：规约方法：设G=（V，E）是连通无向图，SV是一个团集当且仅当SV是G中的一个顶点覆盖。证明：设e=(u,v)是G中的任意边，SV是一个团集当且仅当u和v都在S中，即SV是G中的一个顶点覆盖。法2：证明：设G=（V，E）是连通无向图，SV是G中的一个独立集，则S是G的一个团集，独立集∝poly团集。因为顶点覆盖∝poly独立集，根据定理10.3，顶点覆盖∝poly团集。3．P185-18610.26用顶点覆盖问题规约到集合覆盖问题，证明集合覆盖问题是NP完全问题。证明：第一步是说明集合覆盖问题是NP的。因为一个不确定性算法可以从猜测一个集合X的子集族F开始，然后验证是否存在F中的k个子集的并是集合X。第二步证明顶点覆盖问题可以在多项式时间内规约到集合覆盖问题。设任意连通无向图G=(V,E)，集合X为G中所有与边相邻的顶点的集合，其子集族则是每个顶点与其相邻的顶点构成的子集。集合X是满足集合覆盖的当且仅当X的子集族中存在k个子集的并是X，当且仅当G中存在大小为k的顶点覆盖。4．P21512.16证明：设{x1,x2,…,xn}是一个正实数集合。对于每一个实数xi，我们使它和二维平面中的点{(x1,1),(xj,0)|j∈2,…,n}相联系，这样，所构造的n个点都位于三角形边上。如果我们用TRIANGULATION问题的任何算法求解构造的实例，输出将是根据它们的x坐标排序的构造点的表，遍历表并读出每点的第一个坐标，结果是排序好的数。所以，排序问题规约到TRIANGULATION问题，排序问题是Ω(nlogn)，TRIANGULATION问题也是Ω(nlogn)。5．P21512.17证明：设{x1,x2,…,xn}是一个升序排列的正实数集合，及实数x。对于实数x及每一个实数xi，我们使它和二维平面中的点{(x,0),(xi,0)|i∈1,…,n}相联系，这样，所构造的点都位于x轴上。如果我们用NEARESTPOINT问题的任何算法求解，输出就是二分搜索要查找的数。所以，二分搜索问题规约到NEARESTPOINT问题，二分搜索问题是Ω(logn)，NEARESTPOINT问题也是Ω(logn)。6．P21512.18证明：设{x1,x2,…,xn}是一个正实数集合，对于每一个实数xi，我们构造点(xi,0)与之对应，于是这些点在x轴上。如果我们用ALLNEARESTPOINT问题的任何算法求解，输出将是每个点(xi,0)对应的最近点对(xi,0)，(xj,0)。所以，CLOSEST-PAIR问题规约到ALLNEARESTPOINT问题，CLOSEST-PAIR问题是Ω(nlogn)，ALLNEARESTPOINT问题也是Ω(nlogn)。二.随机算法1．P24114.2假定你有一枚硬币，请设计一个有效的随机算法用来生成整数1,2...n的随机排列，n为正整数，分析你的算法的时间复杂性。基本思想：从空序列开始，逐个向序列添加1,2,…,n。根据二分搜索的思想，并利用多次抛硬币，来随机确定每个添加的数在序列中的位置。算法RANDOMIZE2输入：正整数n输出：1,2,…,n的一个随机排列。A[1]=1fori=2tonj=randombisearch(1,i-1)//在数组A中随机确定i的插入位置。insert(A,j,i)//在数组A的j位置上插入值i。endforoutputA[1..n]endRONDOMIZE2过程randombisearch(low,high)//利用二分搜索在A[low..high+1]中随机确定值i的插入位置，//并返回该位置。iflowhighthenreturnlowelsemid=2highlowk=random(1,2)//抛一次硬币。ifk=1thenhigh=mid-1//插入位置在A[low..mid]中。elselow=mid+1//插入位置在A[mid+1..high+1]中。returnrandombisearch(low,high)endifendrandombisearch时间复杂性：Θ(n2)2．P24114.5在算法RANDOMIZEDQUICKSORT的讨论中曾说过，为算法QUICKSORT得到一个O（logn）期望时间的一种可能性，是通过排列输入元素使它们的次序变成随机的来获得的。描述一个O（n）时间算法，先随机排列下算法思想：对预排序的数组进行随机排列，使该数组与原先相比显得无序。尽量避免QUICKSORT算法最坏情况的发生即n^2时间，使之更趋近于最佳情况nlogn时间。算法PRE_DISPOSE输入：n个元素的数组a[1…n]输出：随机排列的数组afori=1tonP=random(n)//随机选择小于n的数Q=random(n)//随机选择小于n的数互换a[P]和a[Q]endforendPRE_DISPOSE3．P24114.7考虑对算法BINARYSERCH做如下修改见1.3节，在每次迭代中，随机的选择剩下的位置来代替搜索区间减半设元素存储在一维数组C中，第0个位置不放元素，若每次生成的随机数都是要查找的剩余元素的第一个且未找到要搜索的数，则时间复杂度计算公式如下：0)0(1)(1)(10CiCnnCni计算得到时间复杂度为)(lognO4．写出n皇后问题的如下随机算法：先在棋盘上随机放置m(mn)个互不冲突的皇后，然后用回溯法搜索其余皇后的位置。算法NQUEENS_RAN_ACCU输入：正整数n,m，其中n表示棋盘纬度，m表示随机算法和回溯算法的处理的划分，mn。输出：若找到解，则输出n皇后问题的一个解x[1..n],否则输出无解Flag_Random=true//随机查找时是否有解得标记Flag_Accu=false//精确查找时是否有解得标记k=1x[m+1]=0//精确查找初始化whilek=nandFlag_Randomifk=m//随机算法j=0fori=1ton//寻找第k行所有可放置皇后的位置。ifplace(k)then//若第k行的位置i可放置皇后,j++;temp[j]=i;//则存储该位置。endifendforifj0thenx[k]=temp[random(1,j)]//随机选取一个位置放皇后elseFlag_Random=false//表示找不到解endifk++elseifkm//回溯算法whilekmandnotFlag_Accuwhilex[k]nandnotFlag_Accux[k]=x[k]+1//试将第k行的皇后移到下一个位置。ifplace(k)then//第k行的当前位置可放置皇后。ifk=nthenFlag_Accu=true//x[m+1..n]是一个解else//x[m+1..k]是精确解答时的部分解k=k+1//前进到下一行x[k]=0endifendif//否则，剪枝endwhilek=k-1//回溯endwhileifk=mbreak;//退出整个循环endifendwhileifFlag_RandomandFlag_Accuthenoutputx//输出一个解elseoutput“Nosolution”//输出无解三.近似算法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个项的集合u[1…n],n个箱子的容量l[1…n]，其中0=u[i]=1，l[i]=1.输出:装这n个项的最少箱子的个数kk=1;//箱子的个数fori=1ton//装项ui时，将其装入序号最小的可容得下该项的箱子中j=1flag=false;whilej=kandnotflag//从序号最小的开始查找ifl[j]u[i]then//找到可以放进去的箱子l[j]=l[j]-u[i]flag=true;elsej++//继续寻找endifendwhileifnotflagthen//没有找到可以放进去的箱子k++//开启新的箱子l[k]=l[k]-u[i];endifendforreturnkendFF算法BF输入:n个项的集合u[1…n],n个箱子的容量l[1…n]，其中0=u[i]=1，l[i]=1.输出:装这n个项的最少箱子的个数kk=1;//箱子的个数fori=1ton//装项ui时，将其装入满足l=1-si的箱子中使l值最大的箱子中ifl[j]u[i]then//找到l值最大的可以放进去的箱子l[j]=l[j]-u[i]elsek++//开启新的箱子l[k]=l[k]-u[i];endifsort(l[1…k])//对前k个箱子的l值从大到小排序endforreturnkendBF2．P25515.10如图：按照算法，先得到顶点的度数降序排列：V1、V2、V3、V4（度数均为2），先将V1添加到覆盖中，删除边{V1，V4}和{V1，V2}，接着添加V2，删除边{V2，V3}，添加V3，删除边{V3，V4}。故得覆盖{V1，V2，V3}，而最佳覆盖为{V1，V3}或{V2，V4}。3．P25615.1415.15（这两题的答案是学长给的）V1V2V3V415.14考虑在给定的图G中找出最大团集问题的近似算法，基本步骤：1、C=｛｝2、向C中添加一个顶点（该顶点不在C中，与C中每个顶点相连接）3、重复步骤2，直到C=G或者G-C中任一点x与C中点都不是全部相连Solution:这里}|{是无向图graphgraphDII取的侯选解集为实例则ggSDgIIII)(,,是由题意给出的算法设。则而找到团集的顶点个数作用于实例为算法其中定义gkkfgSIIII,)(),(题目算法寻求最大团集，这是最大化问题，近似度1)()()(ggOPTgR分三种情况讨论：:)i若则个顶点的无向完全图，是一个具有1,mgDgII1)(gR:)ii若g是由n个无向完全图：nggg,,,21之简单并，niigg1，的顶点个数表示用iigg)(，则)()}(,),(),(max{)(21ingggggR=MgOPT)(ZM。MgOPT)(且。上式分母取)(ig输出的是具有示意算法)(ig个顶nigi,,2,1,点的团集:)iii对于gDgII,不是由)i、)ii讨论的无向图，则可以去掉一些边，这些边及跟这些边相连的顶点不构成图g的完全子图，最后图g分解成独立的“较小”的无向图（即团集）的简单并。转为)ii讨论的情形。结论：这个近似算法可能达到的近似度具有如下形式：IIDg