《生成树算法》PPT课件.ppt

《《生成树算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《生成树算法》PPT课件.ppt（32页珍藏版）》请在三一办公上搜索。

1、15.082 和 6.855J,生成树算法,2,行动中的贪婪算法,1,2,3,4,5,6,7,3,行动中的贪婪算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,4,行动中的贪婪算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,5,行动中的贪婪算法,1,2,3,35,10,4,5,30,15,25

2、,40,20,6,7,17,8,15,11,21,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,6,行动中的贪婪算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,7,行动中的贪婪算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,8,行动中的贪婪

3、算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,9,行动中的贪婪算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,10,行动中的贪婪算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,35,10,30,15,25,40,20,17,8,15,

4、11,21,1,2,3,4,5,6,7,11,行动中的贪婪算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,12,行动中的贪婪算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,13,行动中的贪婪算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21

5、,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,14,行动中的贪婪算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,行动中的贪婪算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,结点 1 2 3 4 5 6 7 首 1 2 3 4 5 4 7,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,5,7,4,6,

6、6,15,行动中的贪婪算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,结点 1 2 3 4 5 6 7 首 1 4 3 4 5 4 7,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,2,16,行动中的贪婪算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,结点 1 2 3 4 5 6 7 首 1 4 3 4 5 4 5,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,7,17,行动中的贪

7、婪算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,结点 1 2 3 4 5 6 7 首 1 4 5 4 5 4 5,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,7,3,18,行动中的贪婪算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,结点 1 2 3 4 5 6 7 首 1 4 4 4 4 4 4,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,5,7,3,19,行动中的贪婪算法,

8、1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,结点 1 2 3 4 5 6 7 首 4 4 4 4 4 4 4,35,10,30,15,25,40,20,17,8,15,11,21,1,2,3,4,5,6,7,3,1,20,21,行动中的Prim算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,4,5,6,7,1,2,3,从黄色结点到绿色结点的最小代价弧能通过把在优先队列中的弧值替换找到。,22,行动中的Prim算法,1,3,35,4,5,30,15,25,40,20,6,7,17,8,1

9、5,11,21,4,5,6,7,1,35,2,2,10,2,3,23,20,行动中的Prim算法,1,3,35,4,5,15,25,40,6,7,17,15,11,1,35,2,2,10,25,10,2,4,10,8,21,30,5,6,7,3,4,24,20,行动中的Prim算法,1,3,35,4,5,15,25,40,6,7,17,15,11,1,35,2,2,10,25,10,2,4,10,8,21,30,8,20,30,21,6,8,5,7,3,6,4,25,20,行动中的Prim算法,1,3,35,4,5,15,25,40,6,7,17,15,11,1,35,2,2,10,25,10

10、,2,4,10,8,21,30,8,20,30,21,6,8,17,15,6,4,15,5,7,3,5,26,20,行动中的Prim算法,1,3,35,4,5,15,25,40,6,7,17,15,11,1,35,2,2,10,25,10,2,4,10,8,21,30,8,20,30,21,6,8,17,15,6,4,15,5,7,3,5,27,20,行动中的Prim算法,1,3,35,4,5,15,25,40,6,7,17,15,11,1,35,2,2,10,25,10,2,4,10,8,21,30,8,20,30,21,6,8,17,15,6,4,15,5,15,11,3,7,5,11,7

11、,28,20,行动中的Prim算法,1,3,35,4,5,15,25,40,6,7,17,15,11,1,35,2,2,10,25,10,2,4,10,8,21,30,8,20,30,21,6,8,17,15,6,4,15,5,15,11,7,11,7,3,5,15,3,29,20,行动中的Prim算法,1,3,35,4,5,15,25,40,6,7,17,15,11,1,35,2,2,10,25,10,2,4,10,8,21,30,8,20,30,21,6,8,17,15,6,4,15,5,15,11,7,11,7,3,5,15,3,30,20,行动中的Prim算法,1,3,35,4,5,1

12、5,25,40,6,7,17,15,11,1,35,2,2,10,25,10,2,4,10,8,21,30,8,20,30,21,6,8,17,15,6,4,15,5,15,11,7,11,7,3,5,15,3,31,行动中的Prim算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,把所有结点当成单独的组件，然后选择离开组件的最小代价弧.,4,5,6,7,1,2,3,4,5,6,7,1,2,3,32,行动中的Prim算法,1,2,3,35,10,4,5,30,15,25,40,20,6,7,17,8,15,11,21,寻找从每个组件出发的最小代价边,4,5,6,7,1,2,3,7,3,5,6,