教师培训课件：数学建模中的最短路.ppt

《教师培训课件：数学建模中的最短路.ppt》由会员分享，可在线阅读，更多相关《教师培训课件：数学建模中的最短路.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最短路：最短路：求下图从求下图从 1 到到 8 的最短路的最短路方法：方法：1.枚举法枚举法2.Dijkstra 方法方法最短路最短路 例（例（Dijkstra方法）方法）最短路练习（最短路练习（Dijkstra方法）方法）最短路最短路1最短路最短路2最短路最短路3最短路最短路4最短路最短路5最短路最短路6最短路最短路7最短路最短路8最短路应用设备更新计划设址问题古典游戏：人、狗、鸡、米过河设备更新问题归结为最短路问题每一条从都表示一种相应的设备更新方案；每条路的长度都表示该方案的费用；问题变为在图中求一条从V1到V6的最短路；该问题可以用 Dijkstra 方法求解。方法求解。5757 53

2、57 5357 5357 53小结小结设址问题（以就近为最佳）1-2-3-4-5-6-7最大距离 距离总和1 0-3-4-5-7-8-1010372 3-0-3-2-4-5-77243 4-3-0-5-5-6-88314 5-2-5-0-2-3-55225 7-4-5-2-0-1-37226 8-5-6-3-1-0-2825710-7-8-5-3-2-01035设址问题（以就近为最佳）1-2-3-4-5-6-7距离总和1 0-75-180-150-140-280-50013252 120-0-135-60-80-175-3509203 160-75-0-150-100-210-40010954200-50-225-0-40-105-2508705 280-100-225-60-0-35-1508506 320-125-270-90-20-0-1009257400-175-360-150-60-70-01215古典游戏：人、狗、鸡、米过河要求规则状态 (1,1,0,1)1：在此岸，：在此岸，0：在对岸：在对岸允许状态 (1111),(0000),(1110),(0001),(1101),(0010),(1011),(0100),(1010),(0101)数学模型123434567