算法设计与分析答案参考

1、用Floyd算法求下图每一对顶点之间的最短路径长度，计算矩阵D0，D1，D2和D3，其中Dk[i,j]表示从顶点i到顶点j的不经过编号大于k的顶点的最短路径长度。解051060320D0051050320D105850320D2058503270D3在每条边的矩阵行中依次加入顶点1,2,3，判断有无最短路径2、设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表：①每个选手必须与其他n-1名选手比赛各一次；②每个选手一天至多只能赛一次；③循环赛要在最短时间内完成。（1）如果n=2k，循环赛最少需要进行几天；（2）当n=23=8时，请画出循环赛日程表。解：（1）至少要进行n天（2）如右图：12345678214365873412785643218765567812346587214378563412876543213、对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。ahgfedcb12122823223解：用V1表示已经找到最短路径的顶点，V2表示与V1中某个顶点相邻接且不在V1中的顶点；E1表示加入到最短路径中的边，E2为与V1中的顶点相邻接且距离最短的路径。步骤V1V2E1E21.{a}{b}{}{ab}2.{a,b}{d}{ab}{bd}3.{a,b,d}{c,f}{ab,bd}{dc,df}4.{a,b,d,c}{f}{ab,bd}{df}5.{a,b,c,d,f}{e}{ab,bd,dc,df}{fe}6.{a,b,c,d,e,f}{g}{ab,bd,dc,df,fe}{eg}7.{a,b,c,d,e,f,g}{h}{ab,bd,dc,df,fe,eg}{gh}8.{a,b,c,d,e,f,g,h}{}{ab,bd,de,df,fe,eg,gh}{}结果：从a到h的最短路径为abdfegh，权值为18。求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。补充例题：求A到各个顶点的最短路径：解：4、用动态规划策略求解最长公共子序列问题：（1）给出计算最优值的递归方程。（2）给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出其最长公共子序列，要求给出过程。解：(1)时y0且xj当i,)j]1,c[i1],jmax(c[i,时y0且xj当i,11]j1,c[i0时0或j当i0j]c[i,iiii（2）ＹＡＢＣＢＸ0000Ｂ00111Ｃ00122Ｄ00122Ａ01122最长公共子序列：｛ＢＣ｝5、对下图所示的连通网络G，用克鲁斯卡尔(Kruskal)算法求G的最小生成树T,请写出在算法执行过程中，依次加入T的边集TE中的边。说明该算法的贪心策略和算法的基本思想，并简要分析算法的时间复杂度。答：TE={(3,4),(2,3),(1,5),（4,6）（4,5）}贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。基本思想：首先将图中所有顶点都放到生成树中，然后每次都在连接两个不同连通分量的边中选权值最小的边，将其放入生成树中，直到生成树中有n-1条边。时间复杂度为：O(eloge)123456181117151921266796、快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。A=(65,70,75,80,85,55,50,2)解：第一个分割元素为657、对于下图，写出图着色算法得出一种着色方案的过程。解：K←1X[1]←1,返回trueX[2]←1,返回false;X[2]←X[2]+1=2,返回trueX[3]←1,返回false;X[3]←X[3]+1=2,返回false;X[3]←X[3]+1=3,返回trueX[4]←1,返回false;X[4]←X[4]+1=2,返回false;X[4]←X[4]+1=3,返回true找到一个解（1，2，3，3）8、有n个物品，已知n=7,利润为P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1)，背包容积M=15,物品只能选择全部装入背包或不装入背包，设计贪心算法，并讨论是否可获最优解。解：定义结构体数组G将物品编号、利润、重量作为一个结构体例如G[k]={1,10,2}求最优解按利润/重量的递减序有：{5,6,1,6}、{1,10,2,5}{6,18,4,9/2}、1342(1)(2)(3)(4)(5)(6)(7)(8)ip65707580855550228652758085555070376525080855575704665250558580757046557075808565502{3,15,5,3}、{7,3,1,3}、{2,5,3,5/3}、{4,7,7,1}算法：procedureKNAPSACK(PWMXn)//P(1n)和W(1n)分别含有按P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值和重量。M是背包的容量大小而x(1n)是解向量//realP(1n)W(1n)X(1n)McuintegerinX←0//将解向量初始化为零//cu←M//cu是背包剩余容量//fori←1tondoifW(i)cuthenexitendifX(i)←1cu←cu-W(i)repeatendGREEDY-KNAPSACK根据算法得出的解：X=1,1,1,1,1,0,0获利润52而解1,1,1,1,0,1,0可获利润54，因此贪心法不一定获得最优解。9、排序和查找是经常遇到的问题。按照要求完成以下各题：（1）对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。（2）给出上述算法的递归算法。（3）使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：18，31，135。解：（1）第一步：15291351832127255第二步：29135183227251515第三步：13532291827251551第四步：13532292725181551（2）输入：递减数组A[left:right]，待搜索元素v。输出：v在A中的位置pos，或者不在A中的消息（-1）。步骤：intBinarySearch(intA[],intleft,intright,intv){intmid;if(left=right){mid=int((left+right)/2);if(v==A[mid])returnmid;elseif(vA[mid])returnBinarySearch(A,left,mid-1,v);elsereturnBinarySearch(A,mid+1,right,v);}elsereturn-1;}（3）搜索18：首先与27比较，1827，在后半部分搜索；再次与18比较，搜索到，返回5。搜索31：首先与27比较，3127，在前半部分搜索；再次32比较，3132，在后半部分搜索，与29比较，3129，此时只有一个元素，未找到，返回-1。搜索135：首先与27比较，13527，在前半部分搜索；再次32比较，13532，在前半部分搜索；与135比较，相同，返回0。10、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树。物品ABCDEFG重量35306050401025价值10403050354030解：（1）求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。（2）按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：aaabaacQ111x21x31x41x50x60x70xdee40x30x41xe51xf60xg50xh40xi20xj10xa．1501154040305035190.625407(1,1,1,1,,0,0)8b.1501154040305030177.5607(1,1,1,1,0,,0)12c．4040305010170(1,1,1,1,0,0,1)d.1501054040303530167.5603(1,1,1,0,1,,0)4e.1501304040503530175601(1,1,0,1,1,,0)3f.1501304040503510170.71354(1,1,0,1,1,0,)7g.40405030160(1,1,0,1,0,1,0)h.1501404040353010146.85352(1,1,0,0,1,1,)7i.1501254030503530167.5605(1,0,1,1,1,,0)12j.1501454030503530157.5601(0,1,1,1,1,,0)12在Q1处获得该问题的最优解为(1,1,1,1,0,0,1)，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。