算法设计与分析报告问题详解参考

《算法设计与分析报告问题详解参考》由会员分享，可在线阅读，更多相关《算法设计与分析报告问题详解参考（11页珍藏版）》请在装配图网上搜索。

1、标准文档1、用Floyd算法求下图每一对顶点之间的最短路径长度，计算矩阵D0,D,D2和D3,其中Dki,j表示从顶点i到顶点j的不经过编号大于k的顶点的最短路径长度。021Do一0比20曲20 7 2305D2 =305D3 =3 0 51050一i850_i8 5 0一Di1,2,3，判断有无最短路径在每条边的矩阵行中依次加入顶点2、设有n=2k（运动员要进行循环赛，现设计一个满足以下要求的比赛日程表： 每个选手必须与其他n-1名选手比赛各一次; 每个选手一天至多只能赛一次； 循环赛要在最短时间内完成。（1）如果n=2k，循环赛最少需要进行几天;（2）当n=23=8时，请画出循环赛日程表。

2、1 2 3 45 6 7 82 1 4 36 5 8 7解：（1）至少要进行n天3 4 1 27 8 5 64 3 2 18 7 6 5（2）如右图：5 6 7 81 2 3 46 5 8 72 1 4 37 8 5 63 4 1 28 7 6 54 3 2 1解：用V表示已经找到最短路径的顶点,V2表示与Vi中某个顶点相邻接且不在Vi中的顶点；Ei表示加入到最短路径中的边，E2为与Vi中的顶点相邻接且距离最 短的路径。步骤V 1V2E1E1.abab2.a,bdabbd3.a,b,dc,fab,bddc,df4.a,b,d,cfab,bddf5.a,b,c,d,feab,bd,dc,dffe

3、6.a,b,c,d,e,fgab,bd,dc,df,feeg7.a,b,c,d,e,f,ghab,bd,dc,df,fe,eggh8.a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh结果：从a到h的最短路径为a b d f e g h，权值为18求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h,每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的 最短路径。补充例题：求A到各个顶点的最短路径:解:T珂号塞合中1选入A3 此时虽短路径A TSO 以A为中间煜，从白开劇C. D、H FA-fe=6*C=3A-XfcV中的痂点=00

4、 发现羸TC=3权值为旱短2选入C此时沪g C此时屋短跖徑AT5b A-C=3以C为中屈直心A T83这条量短IS径捋 始找U= aTCTJ=5（比上面第一歩的要短】 此时勿E权值九A T匸TB=5AHTD=&AT 匚 TTA-C-U中的與点=00发现羸Tf T0砖权值力最短3iJtA b , jktffj s= a、c. b业河掃痼路径A - A=C F A - 03 . A-C-B=5U B为中间点，从A TC T 3咔这条皋短 诧径开胎找V= RTCTBTD力旗出上面第二步的TCTMB要长） 就时劉D权值更改为丸TC T皿中的顶点二 00发现A-C TX&权備为暈短414AD jktM

5、S-a B. Ditffj龄短略徑AT阿* K C=3i 宜TC B=5 j kTTD=6 以P为申阖点.从A T匚TD遠儀屋趣菇径 开給挽U= ATCTDTE =（比上面箒二步&UTCTE巧要长） itflta E 权值更改A-C -1 =T*cDF =9陵观ATCT盧昭权値詡懐短5iiAE . JW S-c,味 K !此时尿短 SS 2 A A=0 k C=3 / ATC TB=5, A-C -D=6 負 TUTE =7以E为中阎点，从鼻TCTTt商这条谶短 路轻开始找Us ATtTETF =】2f比上面第EB步的ATQTDTF =9 要长）上血到F权値更改为A TC TH TF =9 发

6、现ATCTDTF W根值为金短6SA F Jhtr S= a 匚、乩山 E. F 止囲显短蹄径ATE kTM, A-C-B：5i kCB=6 NTCTM miTCTDTF 曲U票合目空屮豪找完幸 2 723g ree 吐 roc k .btog.l63xom4、用动态规划策略求解最长公共子序列问题：（1）给出计算最优值的递归方程。（2） 给定两个序列 X二B,C,D,A , Y二A,B,C,B，请采用动态规划策略求出其最长公共子序列，要求给出过程。解：标准文档Pci, j=何-1,j -1 +1max(ci, j -1, ci当i = 0或j= 0时当i, j0且X i = yi时-1,j)当

7、i, j0且xyi 时00000 .0001 1 2 2XBCDA最长公共子序列：BC5、对下图所示的连通网络 G,用克鲁斯卡尔(Kruskal)算法求G的最 小生成树T,请写出在算法执行过程中，依次加入T的边集TE中的边。说明该算法的贪心策略和算法的基本思想，并简要分析算法的时间复杂度。答：TE=(3,4), (2,3),(1,5),( 4,6)( 4,5)贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。基本思想：首先将图中所有顶点都放到生成树中，然后每次都在连接两个不同连通分量的边中选权值最小的边，将其放入生成树中，直到生成树中有n-1 条边。时间复杂度为：O(eloge)6、

8、快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。A=(65,70,75,80,85,55,50,2)解：第一个分割元素为 65(1)(5) (6) (7)(8)iP657075808555502286527580855550703765250808555亠75704665250558580757046557075808565502解：1X1 1 ,返回 trueX2 1,返回 false; X2X2+1=2,返回 trueX3 1 ,返回 false; X3X3+仁2,返回 false;X3X3+仁3,返回 trueX4 1,返回 false; X4 X4+仁2,返回

9、 false;X4 X4+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将物品编号、利润、重量作为一个结构体例如 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 n)

10、和 W(1 n)分别含有按P(i)/W(i) P(i+1)/W(i+1)排序的n件物品的效益值和重量。M是背包的容量大小而x(1n)是解向量/real P(1 n) W(1 n) X(1 n) M cuin teger i nX0 /将解向量初始化为零/cu J M /cu是背包剩余容量/for i J1 to n doif W(i)cu the n exit en difX(i) J1cu J cu-W(i)repeatend GREEDY-KNAPSACK根据算法得出的解：X=1,1,1,1,1,0,0 获利润52而解1,1,1,1,0, 1,0可获利润54，因此贪心法不一定获得最优解。9

11、、排序和查找是经常遇到的问题。按照要求完成以下各题：(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

12、，待搜索元素 v。输出：v在A中的位置pos,或者不在A中的消息(-1 )。步骤：int BinarySearch(int A,int left,int right,int v)int mid;if (leftAmid) return BinarySearch(A,left,mid-1,v);else return BinarySearch(A,mid+1,right,v);elsereturn -1;(3)搜索 18：首先与 27比较, 1827,在前半部分搜索；再次32比较，3129,此时只有一个元素，未找到，返回-1。搜索135:首先与27比较，13527,在前半部分搜索；再次32比较，

13、13532, 在前半部分搜索；与135比较，相同，返回0。10、假设有7个物品，它们的重量和价值如下表所示。 若这些物品均不能被分割，且背包容量 Mk 150,使用回溯方法求解此背包问题。请写出状态空间搜索树。物品ABCDEFG重量35306050401025价值10403050354030解:(1) 求所有顶点对之间的最短路径可以使用Dijkstra 算法，使其起始节点从 a循环到 h,每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。(2) 按照单位效益从大到小依次排列这7个物品为：FBGDECA将它们的序号分别记为17。则可生产如下的状态空间搜索树。其中各个节点处

14、的限界函数值通过如下方式求得：X7a1a10ai1X3a0X310x4dae10he10egc0x6x 1x 4Q 1x 5x 5x4x2x,=0x 2150 _1157a.40 40 30 50 35190.625(1,1,1,1 = ,0,0)408b150 _1157.40 +40 +30 +50 +30 江=177.5 (1,1,1,1,0 ,0)6012C.40 40 30 50 10 =170(1,1,1,1,0,0,1)d.40150 -10540 - 30 - 35 - 30167.560(1,1,1,0,1,?,0)4e.4040 50 35 30 150 一13 =1756

15、01(1,1,0,1,1护)3f.40405035 10 150 一13 =170.7135(1,1,0,1,1,0,g.40 40 50 30 =160(1,1,0,1,0,1,0)h.40 +40 +35 +30 +10 J50 一140 =146.85(1,1,0,0,1,1,?)35， ， ， ， ， ，了i.4。+30+50十35+30=167.5(1,0,1,1,12,0)60 12j.40 +30 +50 +35 +30 x150 一145 =157.5 (0 10)60(0,1,1,1,1,12,0)在Q处获得该问题的最优解为(1,1,1,1,0,0,1),背包效益为170。即在背包中装入物品G D、A时达到最大效益，为 170,重量为150。