图与网络优化最短路问题.pptVIP

最短路问题 因为 当 k=5时， 所以 从 v1 到 v1 的最短路的距离为 0， 从 v1 到 v2 的最短路的距离为-1， 从 v1 到 v4 的最短路的距离为2， 从 v1 到 v5 的最短路的距离为-1， 从 v1 到 v6 不存在路。 从 v1 到 v3 的最短路的距离为1， 最短路问题 采用“反向追踪法”可得最短路。 把上述结果填入下表得 如从 v1 到 v2 的最短路为 d(v1,v3)=d(v1,v5)+w53=-1+2=1 d(v1,v5)=d(v1,v4)+w45=2-3=-1 d(v1,v4)=d(v1,v1)+w14=0+2=2 d(v1,v2)=d(v1,v3)+w32=1-2=-1 (v1, v4, v5, v3, v2) 例12 (设备更新问题) 某企业使用一台设备，在每年年初，企业领导部门就要 决定是购置新的，还是继续使用旧的。若购置新的，就要支付一定的购置费用； 若继续使用旧设备，则需支付一定的维修费用。现在的问题是如何制定一个 五年之内的设备更新计划，使得总的支付费用最少。若已知该种设备在各年 年初的价格为： 最短路问题 4. 应用举例 第1年 第2年 第3年 第4年 第5年 11 11 12 12 13 还已知使用不同时间(年)的设备所需要的维修费用为： 使用年数 0~1 1~2 2~3 3~4 4~5 维修费用 5 6 8 11 18 解： 把这个问题化为如图4所示的最短路问题： 最短路问题 v1 v2 v3 v4 v5 v6 16 16 17 17 18 22 30 41 59 23 41 30 22 31 23 其中 vi 表示“第i 年年初购进一台新设备”这种状态， v6 表示“第5年年底”； 弧(vi ，vj) 表示在第i 年年初购进的设备一直使用到第j 年年初 (即第j-1年年底)； 弧(vi ，vj) 上的权表示在第i 年年初购进的设备一直使用到第 j 年年初时总的支付 费用。 最优方案：{v1 ，v3 ，v6} 与 {v1 ，v4，v6}。 【例】（渡河问题）这是一个古老的趣味数学问题，在世界不同国家与民族中有着不同的表述形式。今设一人携带狼、羊、菜，须从一条小河的此岸渡往对岸。河边仅有一条小船，容量为2。当人不在场时，狼要吃羊、羊要吃菜。问：应怎样渡河，才能使大家安全到达对岸，且小船在河上的来回次数最少。(船上必须要有人) 最短路问题 【解】 记M代表人、W代表狼、S代表羊、V代表菜。以河的此岸为考察基点，则开始状态为MWSV，结束状态为Φ。共有16种状态：MWSV、MWS、MWV、MSV、WSV、MW、MS、MV、WS、WV、SV、M、W、S、V、Φ。其中，有6种不允许出现，即：WSV、MW、MV、WS、SV、M。 最短路问题 于是，可能的状态仅有10种，以每个状态作为顶点，构造相应的图（如图5-8所示），其中，边的连接原则为：若状态甲经一次渡河可变为乙，则连一条边。从而，渡河问题就归结为求MWSV→Φ的最短路， 其中，每条边的权为1。 MWSV MWS MWV MSV MS WV W S V Φ 最短路问题 练习 如图所示为某地区的交通网络，弧上的权表示该路线的长度。设有一批货物要从v1运到v7，试确定最短运输路线 v1 v2 v3 v4 v5 v6 v7 1 4 2 1 4 5 7 2 3 2 6 最短路问题 (Shortest Path Problems) v1 v2 v3 v4 v5 v6 9 1 1 3 12 图 3 2 6 8 5 从 v1 到 v6 的最短路？ 1. 最短路 最短路－用途： 管道铺设, 路线安排, 厂区布局, 设备更新 最短路：给定一个赋权有向图 D=(V, A)，对D中每条弧 (vi, vj)赋权 wij; 若 P 为 D 中从 vs 到 vt 的一条路，定义P的权为 W(P)= 如果 存在一条从 vs 到 v