资源描述
最短路: 求下图从 1 到 8 的最短路 方法: 1.枚举法 2.Dijkstra 方法 最短路 例( Dijkstra方法) 最短路练习( Dijkstra方法) 最短路 1 最短路 2 最短路 3 最短路 4 最短路 5 最短路 6 最短路 7 最短路 8 最短路应用 设备更新计划 设址问题 古典游戏:人、狗、鸡、米过河 设备更新 年初表示第点: jv j 年初费用年初买新设备,用到第表示第边: jivv ji 1v 问题归结为最短路问题 每一条从都表示一种相应的设备更新方 案; 每条路的长度都表示该方案的费用; 问题变为在图中求一条从 V1到 V6的最短 路; 该问题可以用 Dijkstra 方法求解。 57 57 53 57 53 57 53 57 53 小结 设址问题(以就近为最佳) 1-2-3-4-5-6-7 最大距离 距离总和 1 0-3-4-5-7-8-10 10 37 2 3-0-3-2-4-5-7 7 24 3 4-3-0-5-5-6-8 8 31 4 5-2-5-0-2-3-5 5 22 5 7-4-5-2-0-1-3 7 22 6 8-5-6-3-1-0-2 8 25 7 10-7-8-5-3-2-0 10 35 ji vv 设址问题(以就近为最佳) 1-2-3-4-5-6-7 距离总和 1 0-75-180-150-140-280-500 1325 2 120-0-135-60-80-175-350 920 3 160-75-0-150-100-210-400 1095 4 200-50-225-0-40-105-250 870 5 280-100-225-60-0-35-150 850 6 320-125-270-90-20-0-100 925 7 400-175-360-150-60-70-0 1215 古典游戏:人、狗、鸡、米过河 要求 规则 状态 (1,1,0,1) 1:在此岸, 0:在对岸 允许状态 (1111),(0000),(1110),(0001), (1101),(0010),(1011),(0100), (1010),(0101) 数学模型 1 2 3 4 3 4 5 6 7
展开阅读全文