最小生成树及应用

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

1、动态规划解决的问题

可解决运输问题（p165例3）、生产问题（p165例4）、库存问题、定价问题和资金运用等问题。2、涉及学科3、Bellman最优化原理－P1634、图上作业法5、表上作业法第9页，共22页，2023年，2月20日，星期六Bellman最优化原理Bellman方程(最短路方程、动态规划基本方程)每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。第10页，共22页，2023年，2月20日，星期六例1

从上海到伊犁间有一个铁路网，某学生暑假打算到伊犁旅游，出于经济关系只能坐火车，而且要求费用最少。下图标出了各种可能的行车路线，请为这位同学的决策做出指导。第11页，共22页，2023年，2月20日，星期六图上作业法上海伊犁AB45CDE425FH56753G43654546求费用最小的方案如果用穷举法，先要计算从上海到伊犁的所有路径的费用，再取最小的路径。第12页，共22页，2023年，2月20日，星期六Dijkstra算法第13页，共22页，2023年，2月20日，星期六计算过程正向图上作业法RAm=4,RBm=5,RCm=min{RAm-C8,RBm-C12}=8RDm=min{RAm-D,RBm-D}=6REm=min{RAm-E9,RBm-E8}=8RFm=min{RCm-F13,RDm-F10,REm-F14}=10RGm=min{RDm-G9,REm-G13}=9RHm=min{RCm-H14,REm-H12}=12RSm=min{RFm-S15,RGm-S13,RHm18-S}=13G943RS13A4B545C8D6E8425F10H1256546753654RBm-E8REm-H12RGm-S13RDm-G9RDm-F10RAm-C8RAm-DRAmRSmRGmRDmRAm第14页，共22页，2023年，2月20日，星期六计算过程逆向FSm=5,GSm=4,HSm=6CSm=min{C-FSm,C-HSm}=10DSm=min{D-FSm,D-GSm}=7ESm=min{E-FSm,E-GSm,E-HSm}=9ASm=min{A-CSm,A-DSm,A-ESm}=9BSm=min{B-CSm,B-DSm,B-ESm}=12RSm=min{R-ASm,R-BSm}=13图上作业法G443R13SA9B1245C10D7E9425F5H656546753654第15页，共22页，2023年，2月20日，星期六图上作业法R上海S伊犁AB45CDE425FH56753G43654546费用最小的方案为RADGS＝13有时可能有几条费用最小方案，也可一同求出。第16页，共22页，2023年，2月20日，星期六表上作业法对于状态很多的问题，图上表示不易，适宜采用表上作业法。见P164-165第17页，共22页，2023年，2月20日，星期六表上作业法第18页，共22页，2023年，2月20日，星期六Q：如何求效益最大问题？在计算中采用MAX函数第19页，共22页，2023年，2月20日，星期六课后练习再网上搜索Dijkstra的信息，为他作一份网页，你怎样和他取得联系？动态规划除了Dijkstra算法之外还有其他方法吗？第20页，共22页，2023年，2月20日，星期六作业：下表表示一个A－K城的运输任务，数字表示10公里数，请为司机选择最短的路线（分别用图上和表上作业法）。第21页，共22页，2023年，2月20日，星期六/gb/technology/cybernetics/abc/abc202.htmlRossS.

IntroductiontoStochasticDynamicProgramming

Bertsekas

DynamicProgramming

HarrisM.

DynamicEconomicAnalysis/kjdt/kjdt3x_1.html/02/0212/a/0212a17_2.asp.tw/water-resource/water/CH08.html/bookhtm/28/1000aa2a.htm李人厚，韩崇昭（译），