算法设计与分析试题及答案(4)

很好的复习资料!

答：

（1）标准：重量、价值和单位价值。【3分，每个1分】

（2）使用重量从小到大：FGBAEDC。得到贪心解为：FGBAE全部放入，而D放入20%，得到价值为165。【5分】

使用价值从大到小：DFBEGCA，得到贪心解为：DFBE全部放入，而G放入80%，得到价值为：189。【5分】

使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而E放入87.5%，得到价值为190.625。【5分】

（3）显然使用单位价值作为标准得到的是最优解。【2分】 三、

对于下图使用Dijkstra算法求由顶点a到其他各个顶点的最短路径。并给出求各个顶点对

之间的最短路径的算法思想。（20分）。

答：三、用V1表示已经找到最短路径的顶点，V2表示与V1中某个顶点相邻接且不在V1中的顶点；

E1表示加入到最短路径中的边，E2为与V1中的顶点相邻接且距离最短的路径。【1分】 步骤 V1 V2 E1 E2 1. {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} {} 【以上每步2分】 结果：从a到h的最短路径为a b d f e g h，权值为18。【1分】 求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。【2分】

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库算法设计与分析试题及答案(4)在线全文阅读。