最小生成树及应用幻灯片.ppt

《最小生成树及应用幻灯片.ppt》由会员分享，可在线阅读，更多相关《最小生成树及应用幻灯片.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最小生成树及应用第1页，共22页，编辑于2022年，星期六生成树n指没有任何回路的图n图由点、线和长度构成n以前的网络图，求关键路径为求最长路。第2页，共22页，编辑于2022年，星期六煤气管道的铺设n某新建小区着手铺设煤气管道，已知每一幢楼的接入位置和距离，请求出最短的铺设方案。第3页，共22页，编辑于2022年，星期六ABCDO1386549910破圈法破圈法第4页，共22页，编辑于2022年，星期六ABCDO6549最短路：第5页，共22页，编辑于2022年，星期六问题n最短生成树唯一吗？n如果是求最长生成树，如何解决？n1n2n3第6页，共22页，编辑于2022年，星期六练习n求最短生

2、成树1 12 23 34 45 51 12 25 53 3-4-42 23 3第7页，共22页，编辑于2022年，星期六动态规划动态规划(Dynamic Programming)第8页，共22页，编辑于2022年，星期六动态规划动态规划(Dynamic Programming)1、动态规划解决的问题可解决运输问题（p165例3）、生产问题（p165例4）、库存问题、定价问题和资金运用等问题。2、涉及学科3、Bellman最优化原理P1634、图上作业法5、表上作业法第9页，共22页，编辑于2022年，星期六Bellman最优化原理Bellman方程(最短路方程、动态规划基本方程)每一点最优都是

3、上一点最优加上这段长度。即当前最优只与上一步有关。第10页，共22页，编辑于2022年，星期六例1 从上海到伊犁间有一个铁路网，某学生暑从上海到伊犁间有一个铁路网，某学生暑假打算到伊犁旅游，出于经济关系只能坐火车，假打算到伊犁旅游，出于经济关系只能坐火车，而且要求费用最少。下图标出了各种可能的行车而且要求费用最少。下图标出了各种可能的行车路线，请为这位同学的决策做出指导。路线，请为这位同学的决策做出指导。第11页，共22页，编辑于2022年，星期六图上作业法图上作业法上海伊犁AB45CDE425FH56753G43654546求费用最小的方案如果用穷举法，先要计算从上海到伊犁的所有路径的费用，

4、再取最小的路径。第12页，共22页，编辑于2022年，星期六Dijkstra算法算法第13页，共22页，编辑于2022年，星期六计算过程 正向图上作业法图上作业法RAm=4,RBm=5,RCm=minRAm-C8,RBm-C12=8RDm=minRAm-D,RBm-D=6REm=minRAm-E9,RBm-E8=8RFm=minRCm-F13,RDm-F10,REm-F14=10RGm=minRDm-G9,REm-G13=9RHm=minRCm-H14,REm-H12=12RSm=minRFm-S15,RGm-S13,RHm18-S=13G943RS13A4B545C8D6E8425F10H1

5、256546753654RBm-E8REm-H12RGm-S13RDm-G9RDm-F10RAm-C8RAm-DRAmRSmRGmRDmRAm第14页，共22页，编辑于2022年，星期六计算过程 逆向FSm=5,GSm=4,HSm=6CSm=minC-FSm,C-HSm=10DSm=minD-FSm,D-GSm=7ESm=minE-FSm,E-GSm,E-HSm=9ASm=minA-CSm,A-DSm,A-ESm=9BSm=minB-CSm,B-DSm,B-ESm=12RSm=minR-ASm,R-BSm=13图上作业法图上作业法G443R13SA9B1245C10D7E9425F5H6565

6、46753654第15页，共22页，编辑于2022年，星期六图上作业法图上作业法R上海S伊犁AB45CDE425FH56753G43654546费用最小的方案为RADGS13有时可能有几条费用最小方案，也可一同求出。第16页，共22页，编辑于2022年，星期六表上作业法表上作业法对于状态很多的问题，图上表示不易，适宜采用表上作业法。见P164-165第17页，共22页，编辑于2022年，星期六表上作业法表上作业法第18页，共22页，编辑于2022年，星期六Q：如何求效益最大问题？在计算中采用MAX函数第19页，共22页，编辑于2022年，星期六课后练习n再网上搜索Dijkstra的信息，为他作一份网页，你怎样和他取得联系？n动态规划除了Dijkstra算法之外还有其他方法吗？第20页，共22页，编辑于2022年，星期六作业：下表表示一个AK城的运输任务，数字表示10公里数，请为司机选择最短的路线（分别用图上和表上作业法）。第21页，共22页，编辑于2022年，星期六lhttp:/ S.Introduction to Stochastic Dynamic ProgrammingBertsekasDynamic ProgrammingHarris M.Dynamic Economic Analysislhttp:/