算法设计与分析答案参考
1、用Floyd算法求下图每一对顶点之间的最 短路径长度，计算矩阵 D, D, D和D,其中 Di, j表示从顶点i到顶点j的不经过编号oi23k 大于k的顶点的最短路径长度。解0 20 20 2072D 305D 305D 305D 306102310501050850850在每条边的矩阵行中依次加入顶点1,2,3，判断有无最短路径k2、设有n=2个运动员要进行循环赛，现设计一个满足以 下要求的比赛日程表：每个选手必须与其他n-1名选手比赛各一次；每个选手一天至多只能赛一次；循环赛要在最短时间内 完成。k（ 1）如果n=2,循环赛最少需要进 行几天； 1 2 3 4 5 6 7 8 3（ 2）当 n=2=8 时， 请画出循环赛日程表。2 1 4 3 6 5 8 7 3 4 1 2 78 5 6 解: （ 1）至少要进行n天 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4（ 2）如右图： 6 5 8 7 2 1 4 378 5 6 3 4 1 28 7 6 5 4 3 2 13、对于下图使用Dijkstra算法求由顶点a至9 顶点h的最短路径。 be2g212ad323182cf2h解： 用V表示已经找到最短路径的顶点，V表示与V中某E为与V中的顶点相邻接且距离最1121短的路径。步骤12121. abab 2. a,bd个顶点相邻接且不在121V中的顶点；E表示加入到 最短路径中的边，abbd 3.dc,df 4. a,b,d,ca,b,c,d,fea,b,dfc,f ab,bd ab,bd df 5.ab,bd,dc,df fe 6. a,b,c,d,e,fg 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,hab,bd,de,df,fe,eg,gh 结果：从a到h的最短路径 为，权值为18。求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最 短路径，最终可以求得所有顶点对之间的最短路径。 补充例题：求A到各个顶点的最短路径： 解:4用动态规划策略求解最长公共子序列问题：（1）给出计算最优值的递归方程。（2）给定两个序列X=B,C,D,AY=A,B,C,B，请采用动态规划策略求出其最长公共子序列，要求给出过程。解：(1当i0或j0时当i,j0且xy时IIk1max(cijlLcilj)当 i,jo 且 xy 时Y A B CBX0000B 0 0 1 1 1C00122 D 0 0 1 2 2 A 0 1 12 2 最长公共子序列：BC5、对下图所示的连通网络G,用克鲁斯卡尔(Kruskal) 算法求G的最小生成树T,请写 出在算法执行过程中，依次加 入T的边集TE中18217 2119 11 9 6 3 2615 6 4 5 17 的边。说明 该算法的贪心策略和算法的基 本思想，并简要分析算法的时 间 复 杂 度 。 答 ： TE=(3,4), (2,3),(1,5),(4,6)(4,5)贪心策略是每次都在连接两个不同连通分量的边中选权值最小 的边。 基本思想：首先将图中 所有顶点都放到生成树中，然 后每次都在连接两个不同连通 分量的边中选权值最小的边， 将其放入生成树中，直到生成 树中有 n-1 条边。 时间复杂度 为： O(eloge) 6、快速排序算法对下列实例排序，算法执行 过程中，写出数组 A 第一次被分割的过程。 A=(65,70,75,80,85,55,50,2) 解：第一个分割元 素为 65 (1) (2) (3) (4) (5) (6) (7) (8) i p657075808555 50228652758085555070 376525080855575704 665250558580757046 5570758085655027 、对于下图，写出图着色算法得出一种着色方案的过程。2 3 1 4 解：31 X1返1 ,回 true X2 1 返回 false; X2 X2+1=2,返回 true X3 1 ,返回 false; X3 X3+1=2,返 回 false;X3 X3+1返回 true X4 1 返回 false;X4 X4+1=2返回 false;X4 X4+返回 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 将物品编号、利润、重量作为一个结构体 例如 Gk=1,10,2 求最优解按利润 /重量的递减序有： 5,6,1,6、1,10,2,56,18,4,9/2 、3,15,5,3 、7,3,1,3、2,5,3,5/3 、4,7,7,1算法：procedure KNAPSACK(P W M X n) P(1 和 W(1n)分别含有按P(i)/W(i)> P(i+1)/W排+序的n件物品的效益 值和重量。M是背包的容量大小而x(1 n)是解向量 / real P(1 n) W(1 n) X(1 n) M cu integer i nX0 /将解向量初始化为零 / cuM是背包剩余容量 / for i1 to n do if W(i)>cu then exitendif X(i) 1 -W(ci)urepeatcu endGREEDY-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）第一步： 15 29 135 18 32 1 27 25 5 第 二步：29 135 18 32 27 25 15 1 5第三步： 135 32 29 18 27 25 15 5 1 第四步： 135 32 29 27 25 18 15 5 1 （2） 输入：递减数组 Aleft:right待搜索元素 V。输出： v在A中的位置pos,或者不在A中的消息（-1）。步骤： int BinarySearch（int A,int left,int right,int v）int mid;if (left<=right)mid=int(left+right)/2);if (v=Amid) return mid;else if (v>Amid) return BinarySearch(A,left,mid-1,v); else return BinarySearch(A,mid+1,right,v); else return -1;(3)搜索 18：首先与 27 比较,18<27,在后半部分搜索；再次与18 比较,搜索到,返回 5。搜索 31：首先与 27 比较, 31>27,在前半部分搜索；再次 32 比较, 31<32,在后半部分搜 索,与 29 比较, 31>29,此时只有一个元素,未找到，返回-1。搜索135:首先与27比较，135>27,在前半部分搜索；再次 32比较，135>32,在前半部分搜索；与135比较，相同，返回0。10、假设有7个物品，它们的重量和价值如 下表所示。若这些物品均不能被分割，且背 包容量M = 150,使用回溯方法求解此背包问 题。请写出状态空间搜索树。物品A BC DEF G 重量 35 30 60 50 40 10 25 价值 10 40 30 5035 40 30解：（1）求所有顶点对之间的最短路径可以使用Dijkstra算法， 使其起始节点从a循环到h,每次求起始节点到其他节点的最短路径，最终可 以求得所有顶点对之间的最短路径。（2）按照单位效益从大到小依次排列这 7个物品为：FBGDECA将它们的序号分别记为 17。则可生产如下的状态空间 搜索树。其中各个节点处的限界函数值通过如下方式求得： aX ii x Olajx 12x 02aix 13ax Ox 134x 04adex 14x Ox 054behx 15x Ox OSSgecx 06x 07fQi150 115a.740 403050 35190.625(1,1,1,1,0,0)408150115b.74040 30 5030177.5(1,1,1,1,0,0)6012C .40 4030 50 10 170(1,1,1,1,0,0,1)150105d.34040 30 35301673(14,104)604150130e.14040 50 3530603f.150 13044040 5 0 35 10170.71(1,1,044A) 35 740 4050 30 160(1,1,0,1,0,1,0)150140h.24040 353010146.85(1,1,0.OJJJ357150 125L54030 503530167.5(1A1A4,O)6012150 145 14030 503530157.5(04,1,14,0)6012(1,1,1,1,0,0,1)在 Q 处获得该问题的最优解为，背包效益为 170。即在背包中装入物品 F、1 B、G、D、A 时达到最大效益， 为 170 ，重量为 150 。
