大连理工大学算法分析与设计算法

1.写出Prim算法描述，并给出时间复杂度的分析。算法描述：假设N=(V，E)，TE是N最小生成树边的集合。算法从U={u0}(u0∈V),TE={}开始，重复执行下述操作：在所有u∈V，v∈V-U的边(u,v)∈E中，找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直到U=V为止。此时TE中必有n-1条边，则T=(V,TE)为最小生成树时间复杂度：算有2个内循环，其一是选择具有最小代价的边，频度为n-1；其二是重新选择最小代价的边，频度为n，因此prim算法的时间复杂度为O(n2).与图中的边数无关，因此适合于求边稠密的图的最小生成树。2.给出Prim算法的正确性证明。正确性证明：设由算法生成的MST为T1，假设存在T2，为与T1具有相同边数最多的实际MST，则w(T1)=w(T2)。假定e2=xy为在T2中且不在T1中的且具有最小权值的边。记在T1中，从根结点A到x的路径为Px1x2…xs(x1=A,xs=x)，从A到的y路径为Py1y2…yt(y1=A,yt=y)。不妨假定在算法执行过程A先到达x，再到达y。因为y是通过yt-1yt进入的T1，所以w(yt-1yt)=w(xy),否则xy先进入T1。设在路径Px1x2…xs和Py1y2…yt上且不在T2中权值最小的边e1，将e1加入T2中构成回路。在回路中找一条在T2中但不在T1中的边e3删除之，得T2’若:(1)w(e1)w(e3),则w(T2’)w(T2),与是T2一条最小生成树矛盾；(2)w(e1)=w(e3),T2’与T1具有相同边数比T2与T1具有相同边数多1，与T2是与T1具有相同边数最多的假定矛盾；(3)w(e1)w(e3),因为w(e1)=w(yt-1yt)=w(xy),所以w(e3)w(xy),与xy是在T2中不在T1中的最小权值的边矛盾。所以，Prim算法执行过程是正确的.Prim算法正确性证明数学归纳法：当n=1时，显然成立。假设n=k时，用prim算法构建的是最小生成树。当n=k+1时，设最后加入最小生成树的点是v。在这个n+1个结点的树中任意添加一条边。分两种情况。1.添加的这条边中任意一个顶点都不是v。相当于在去掉了结点v的又k个结点的生成树中添加一条边，根据MST性质，这条边一定是产生回路中权值最大的边。再添加上顶点v，依旧是之前的回路，所以添加的边依旧是现在回路中最长的边。所以当n=k+1时成立2..现在只需要证明，当添加的边其中有一个顶点是v的情形成立即可。假设其余k个结点为uk（k=1,2,3….)其中W(U1v)最小。任意连接Uk(k=2,3…..),一定会出现一条回路。因为采用的是Prim算法，切V结点是最后一个加入进来的，因此回路中不存在大于W(U1V）或者大于W(UkV)的边，并且W(UkV)W(U1V）,所以加入的UkV是回路中权值最大的边，符合MST性质，因此，这种情形下，n=k+1成立综上所述，prim算法正确。3..写出一个怎样找到一个图中的割点的算法描述。由于上述算法是一个遍历的过程，因此求关键点的事假复杂度为O(n+e).4.n个节点的二叉树有多少棵？给出证明。可以分析，当n=1时，只有1个根节点，则只能组成1种形态的二叉树，令n个节点可组成的二叉树数量表示为h(n)，则h(1)=1;h(0)=1;当n=2时，1个根节点固定，还有2-1个节点。这一个节点可以分成（1,0），（0,1）两组。即左边放1个，右边放0个；或者左边放0个，右边放1个。即：h(2)=h(0)*h(1)+h(1)*h(0)=2，则能组成2种形态的二叉树。当n=3时，1个根节点固定，还有2个节点。这2个节点可以分成（2,0），（1,1），（0,2）3组。即h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5，则能组成5种形态的二叉树。以此类推，当n=2时，可组成的二叉树数量为h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)种，即符合Catalan数的定义，可直接利用通项公式得出结果。令h(1)＝1,h(0)=1，catalan数（卡特兰数）满足递归式：h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)h(0)(其中n=2)该递推关系的解为：h(n)=C(2n,n)/(n+1)(n=1,2,3,...)5.给出利用DFS进行拓扑排序算法描述，并给出时间复杂度分析把图中节点的状态分成三种。white代表节点还未被搜索到，gray代表节点已被搜索到但还未被处理完，black代表节点已被处理完。数组topo[]来记录每个顶点的编号。把图中所有的节点的状态初始化为white，topoNum=n，从顶点号为1的顶点开始搜索color[1]=gray.设当前搜索到的节点为v，则按深度优先的方式搜索它的邻接点，若存在某个邻接点状态为white，则把该邻接点的状态改为gray，把它作为当前搜索到的节点，继续按深度优先方式搜索；若所有的邻接点状态都不是white则把当前节点状态改为black，topo[v]=topoNum,topoNum--,然后退回到上一个节点。当所有节点的状态都为black时，退出循环。时间复杂度：设顶点数为n，边数为m。算法分为两部分：初始化和搜索节点，显然初始化的时间复杂度是O（n），搜索节点则是按按深度优先的方式查找所有的边，时间复杂度为O（m+n），故此时间复杂度为O（m+n）。6.对于给定的长度为n的数字序列，给出一个算法，找到该序列中的最长不降子序列（要求至少找到一个）。即对于序列a1，a2，a3，……，an，找到一组1=j1j2……jk=n，使得aj1=aj2=……=ajk，且k最大。并分析时间复杂度解答：定义两个数组maxLength[n]和preEle[n]maxLength[i]表示：序列a1，a2，a3，……，ai中，ai之前（包括ai）最长的子序列的长度preEle[i]表示：上诉子序列中ai的前一个元素的编号。初始：maxLength[1]=1，preEle数组全部置0for(intk=2;k=n;k++){//对于a1，a2，a3，……，ak-1中小于ak的所有at所对应的maxLength[t]中找到最大的一个，将该maxLength[t]加上1即为maxLength[k]，找到的t即为at在当前最长不下降子序列中的前一个元素maxLength[k]=max{maxLength[t]|1=tk,at=ak}+1;preEle[k]=上式中找到的t;}最后，maxLength[n]数组中最大的数即为所求的最长不下降子序列的长度，对应的元素即为最长不下降子序列的最后一个元素，从此元素开始，顺着该元素对应的preEle数组元素向前找对应的元素，直到找到的元素对应的preEle数组元素为0，便得到所求序列。时间复杂度分析：为了获得每个元素ai对应的数组元素maxLength[i]的取值，都需要对原序列中ai之前的每个数进行检验，故时间复杂度为O(n2)。举例：数字序列：192385106找到的maxLength数组中最大的元素为maxLength[7]和maxLength[8]，所以找到两个所求的序列，分别为：1，2，3，5，61，2，3，5，107.已知一有向图G=(V,E),其每条边(u,v)∈E均对应有一个实数值r(u,v),表示从顶点u到顶点v之间的通信线路的可靠性，取值范围为0≤r(u,v)≤1,定义r(u,v)为从u到v的线路不中断的概率，并假定这些概率是相互独立的。写出一个有效算法，来找出两个指定顶点间的最可靠的线路。解答：运用Dijkstra算法的思想，将原来的加法计算改为乘法即可。例如下图：解答过程如下：每一行的意义：从A出发，经过所用可能路径，到达各点的最可靠效率第一次找到B之后，就不用再找了，因为再乘以任何r(u,v)（[0-1]）会使得A到B的可靠性减小8.Floyd算法求出任意两点间的最短距离。例：有向图中有四个点，点之间的距离如下所示：解答：for(k=0;kn;k++)for(i=0;in;i++)for(j=0;jn;j++)A[i，j]=min{A[i，j]，A[i，k]+A[k，j]}算法思想：从图的带权邻接矩阵A=[a(i,j)]n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度9.对于矩阵乘法：第1个乘号第(n-1)个乘号A1×A2×…×And0×d1d1×d2dn-1×dn给出每个乘法运算的执行顺序，使得进行整个矩阵乘法运算过程中进行的数值乘法次数最少。解答：定义函数cost(low,high)，表示计算矩阵A(low)×…×A(high)所需的最少数值乘法次数，root(low,high)表示相应于上述cost(low,high)的进行的最后一次乘法的位置。则状态转移方程为：当low==high时，cost(low,high)=0，root(low,high)=-1当lowhigh时，cost(low,high)=min{cost(low,k)+cost(k+1,high)+d(low-1)×dk×d(high)|low=k=high-1}式(1)root(low,high)=k(式(1)中的k)伪代码实现：定义两个二维数组cost[1...n][1…n]和root[1…n][1…n]//初始化数组的对角线元素for(i=1;i=n;i++)cost[i][i]=0;root[i][i]=-1;//按一定的顺序填充数组for(low=n-1;low=1;low--)for(high=low+1;high=n;high++)cost[low][high]=maxNum;//maxNum表示无穷大for(k=low;khigh;k++)//计算选取不同乘号进行最后一次乘法运算的代价if(cost[low][k]+cost[k+1][high]+dlow-1×dk×dhighcost[low][high])cost[low][high]=cost[low][k]+cost[k][high]+dlow-1×dk×dhigh;root[low][hith]=k;最终，cost[1][n]即为进行该矩阵乘法所需的最少代价。对root数组进行如下的后序遍历，即可得到代价最少的乘法次序，乘法进行的次序存储在数组multOrder[]中intmultOrderNext;extractOrderWrap(intn,introot[],multOrder[]){multOrderNext=1;extractOrder(1,n,multOrder);}extractOrder(intlow,inthigh,introot[],intmultOrder[]){Intk;If(lowhigh)k=root[low][high];extractOrder(low,k,multOrder);extractOrder(k+1,high,multOrder);multOrder[multOrderNext]=k;multOrderNext++;}举例：A1×A2×A3×A430×11×4040×1010×25d0×d1d1×d2d2×d3d3×d4注：以下cost[i][j]用Cij表示，root[i][j]用Rij表示C11=C22=C33=C44=0C12=C11+C22+30×1×40=1200R12=1C23=C22+C33+1×40×10=400R23=2C34=C33+C44+40×10×25=10000R34=3C13=C11+C23+30×1×10=700okC12+C33+30×40×10=13200R13=1C24=C22+