第1讲-最短路问题课件.ppt

1、第1讲一、图论的基本概念二、固定起点的最短路三、任意两点的最短路四、最短路算法的应用 18世纪的哥尼斯堡城中流过一条河。河上游七座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样的游戏：一个游人怎样才能一次连续走过这七座桥而每座桥只走一次，回到原出发点。没有人想出这种走法，又无法说明走法不存在，这就是著名的“七桥”难题。欧拉将这个问题归结图论的问题。他用A,B,C,D四点表示河的两岸和小岛，用两点间的连线表示桥。七桥问题变为：从A,B,C,D任意点出发，能否通过每条边一次且 仅一次，再回到原点？欧拉证明了这样的走法不存在，并给出了这类问题的一般结论。图论 1857年，英国数学家哈密顿

2、发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个定点分别表示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次且仅一次再回到原出发点的路，这就是“环球旅行”问题。七桥问题与“环球旅行”问题不同，前者要在图中找一条经过每边且仅一次的路统称欧拉回路，而后者是要在图中找一条经过每个点一次且仅一次的路，能成为哈密尔顿回路。在这一时间，还有许多诸如迷宫问题、博弈问题以及棋盘上马的行走路线之类的游戏难题，吸引了许多学者。这些看起来似乎无足轻重的游戏却引出了许多有实用意义的新问题，开辟了新学科。图论的第一本专著是匈牙利数学家O Koing 写的“有限图与无限图的理论”，

3、发表于1936年。从1736年欧拉的第一篇论文到这本专著，前后经历了200年之久，总的来讲这一时期图论的发展是缓慢的。直到20世纪中期，电子计算机的发展以及离散数学问题具有越来越重要的地位，使得作为提供离散数学模型的图论得以迅速发展，成为运筹学中十分活跃的重要分支。目前图论被广泛地应用于管理科学、计算机科学、信息论、控制论、物理、化学、生物、心理学等各个领域，并取得了丰硕的成果。图论应用图论应用图与网络优化的一些基本问题图与网络优化的一些基本问题最短路问题最短路问题（SPPshortest path problem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网

4、纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。公路连接问题公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？指派问题指派问题（assignment problem）一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总

5、回报最大？中国邮递员问题中国邮递员问题（CPPchinese postman problem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。旅行商问题（旅行商问题（TSPtraveling salesman problem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。运输问题运输问题（transport

6、ation problem）某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定每个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化（netwok optimization）问题。所以上面例子中介

7、绍的问题都是网络优化问题。由于多数网络优化问题是以网络上的流（flow）为研究的对象，因此网络优化又常常被称为网络流（network flows）或网络流规划等 狼、羊、白菜过河问题狼、羊、白菜过河问题 猎人要把一只狼、一头羊和一篮白菜从河的左岸带到右岸，但他的渡船太小，一次只能带一样。因为狼要吃羊，羊会吃白菜，所以狼和羊，羊和白菜不能在无人监视的情况下相处。问猎人怎样才能达到目的？图图 论论 的的 基基 本本 概概 念念一、一、图图 的的 概概 念念1、图的定义、图的定义2、顶点的次数、顶点的次数 3、子图、子图二、二、图图 的的 矩矩 阵阵 表表 示示1、关联矩阵关联矩阵2、邻接矩阵邻接矩

8、阵返回返回定义定义有序三元组G=(V,E,)称为一个图图.1 V=,21nvvv是有穷非空集，称为顶顶点点集集，其中的元素叫图 G 的顶顶点点.2 E 称为边边集集，其中的元素叫图 G 的边边.3 是从边集 E 到顶点集 V 中的有序或无序的元素 偶对的集合的映射，称为关关联联函函数数.例例1 设 G=(V,E,)，其中 V=v1,v2,v3,v4，E=e1,e2,e3,e4,e5,335414413312211)(,)(,)(,)(,)(vvevvevvevvevve.G 的图解如图.图的定义图的定义定义定义定义定义规定用记号和分别表示图的顶点数和边数.顶点的度数顶点的度数4)(4vd5)(

9、3)(2)(444vdvdvd推论推论任何图中奇次顶点的总数必为偶数例例 在一次聚会中，认识奇数个人的人数一定是偶数。子图子图定定义义设图 G=(V,E,),G1=(V1,E1,1)GGv1,v4,v5Ge1,e2,e3关联矩阵关联矩阵注：假设图为简单图邻接矩阵邻接矩阵注：假设图为简单图最最 短短 路路 问问 题题 及及 其其 算算 法法一、一、基基 本本 概概 念念二、固二、固 定定 起起 点点 的的 最最 短短 路路三、每三、每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路基基 本本 概概 念念通路44112544141vevevevevWvv道路4332264521141veve

10、vevevevTvv路径4521141vevevPvv固固 定定 起起 点点 的的 最最 短短 路路问题：问题：无向连通简单带权图，求出顶点a与z之间的最短通路的长度。最短路问题是网络理论中应用最广的问题之一。许多优化问题可以使这个模型，如设备更新、管道铺设、线路安排、厂区布局等。图论方法比较有效。算法思想：算法思想：最短路是一条路径，且最短路的任一段也是最短路 求出从a到第一个顶点的最短通路的长度，从a到第二个顶点的最短通路的长度，一次类推，直到求出从a到z 的最短通路的长度为止。即类似于树生长的过程。Dijkstra 算法算法：求 G 中从顶点 u0到其余顶点的最短路算法步骤：算法步骤：（

11、）赋初值：令 Su0,l u()0=0 vSVS,令l v()=W u v(,)0,z v()=u0 uu0（3）设v*是使l v()取最小值的S中的顶点，则令 S=Sv*，uv*（4）若S，转 2，否则，停止.用上述算法求出的l v()就是u0到v的最短路的权，从v的父亲标记)(vz追溯到u0,就得到u0到v的最短路的路线.（2）更新l v()、z v()：vSVS,若l v()l uW u v()(,)则令l v()=l uW u v()(,),z v()=u例例 求下图从顶点 u1到其余顶点的最短路先写出带权邻接矩阵：03064093021509701608120W因 G 是无向图，故

12、W是对称阵 TO MATLAB(road1)u1u2u3u4u5u6u7u8218152939763416第0步u2u3u4u5u6u7u82181529397634162(u0)8(u0)1(u0)u1第1步u3u2u3u4u5u6u7u82181529397634162(u0)8(u0)1(u0)u1第2步u310(u0,u3)u2u2u3u4u5u6u7u82181529397634162(u0)8(u0)1(u0)u1第3步u310(u0,u3)u23(u0,u2)u5u2u3u4u5u6u7u82181529397634162(u1)8(u1)1(u1)u1第4步u310(u1,u3

13、)u23(u1,u2)u66(u1,u2)12(u1,u2,u5)u5u2u3u4u5u6u7u82181529397634162(u1)8(u1)1(u1)u1第5步u310(u1,u3)u23(u1,u2)u66(u1,u2)12(u1,u2,u5)u57(u1,u2,u5,u6)u4u2u3u4u5u6u7u82181529397634162(u1)1(u1)u1第6步u310(u1,u3)u23(u1,u2)u66(u1,u2)12(u1,u2,u5)u57(u1,u2,u5,u6)u49(u1,u2,u5,u6,u4)u7u8u3u4u6u7u1u3u2u6u5u4u7u8u1u2u

14、3u4u5u6u7u81243553317284例 求出点1到其余各顶点的最短有向路的长度？Dijkstra算法:9,3,8,5,0:918,11min5,3,min5,3,2,4,1,3115,11min5,2,min835,10min3,2,min5,3,2,4,1,21183,min5,4,min1073,min3,4,min53,5min2,4,min5,3,2,4,1,45,1,34,1,3,152,1,0,5,4,3,2,15432135525523345543342254321SSSSSwSSSTPkwSSSwSSSTPkwSSSwSSSwSSSTPkwSwSwSwSSTP显然且

15、 选址问题：已知某地区的交通网络如图5-39所示，其中点代表居民区，边表示公路，为小区间公路距离，问区中心医院建在哪个小区，可使距离医院最远的小区居民就诊时所走的路程最近?ijlV1V3V4V6V7V2V5602030251520183015解：实际是要求出图的中心，可以化为一系列求最短路问题。先求出v1到其他各顶点的最短路长dj,令D(v1)=maxd1,d2,d7,表示若医院建在v1,则离医院最远的小区距离为D(v1),再依次计算v2，v3，v7到其余各点的最短路，类似求出D(v2)，D(v3)，D(v7)。D(vi)(i=1，2，7)中最小者即为所求，计算结果见下表。由于 D(v6)=4

16、8最小，所以医院建在v6，此时离医院最远的小区 v5距离为48。由于 D(v6)=48最小，所以医院建在v6，此时离医院最远的小区 v5距离为48。v1v2v3v4v5v6v7D(vi)V1030506393456093V2300203363153063V3502002050254050V4633320030183363V5936350300486393V6451525184801548V7603040336315063 人、狼、羊、菜四种的任意组合共有16种。其中狼羊菜、狼羊、羊菜三种不允许出现，所以人、人狼、人菜也不允许出现。允许出现的情况有以下10种情况：人狼羊菜、人狼羊、人狼菜、人羊菜

17、、人羊、狼菜、狼、菜、羊及空。把这10种状态视为10个点，若一种状态通过一次摆渡后可变为另一种状态，则在两种状态（点）之间画一直线，得示意图如下：狼、羊、白菜问题（图论解法狼、羊、白菜问题（图论解法）7424613503 将各顶点到“人狼羊菜”的距离标在图中各顶点处，可知有两种最迅速最安全的渡河方案：（1）人狼羊菜狼菜人狼菜狼 人狼羊羊 人羊空；（2）人狼羊菜狼菜人狼菜菜 人羊菜羊 人羊空；每种方案都要七次。这种“用顶点代表状态，边代表状态间的转移”的状态转移图模型颇具代表性任何具有有限个状态的多步决策问题都可以类似地建立图的模型，利用图论工具来解决 这样摆渡问题就转化成在图中找出以“人狼羊菜

18、”为起点，以“空”为终点的简单路。每每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路(二二)算算法法原原理理1、求距离矩阵的方法、求距离矩阵的方法2、求路径矩阵的方法、求路径矩阵的方法3、查找最短路路径的方法、查找最短路路径的方法（一）算法的基本思想（一）算法的基本思想（三）算法步骤（三）算法步骤算法的基本思想算法的基本思想算法原理算法原理 求距离矩阵的方法求距离矩阵的方法把带权邻接矩阵 W 作为距离矩阵的初值，即 D(0)=)()0(ijd=W（）D(1)=)()1(ijd，其中)0(1)0()1(,miniijijddd)0(1jd)1(ijd是从 vi到 vj的只允许以 v1作为

19、中间点的路径中最短路的长度（2）D(2)=)()2(ijd，其中)1(2)1()2(,miniijijddd)1(2 jd )2(ijd是从 vi到 vj的只允许以 v1、v2作为中间点的路径中最短路的长度（）D()=)()(ijd，其中)1()1()(,miniijijddd)1(jd)(ijd是从 vi到 vj的只允许以 v1、v2、v作为中间点的路径中最短路的长度即是从 vi到 vj中间可插入任何顶点的路径中最短路的长，因此D()即是距离矩阵算法原理算法原理 求路径矩阵的方法求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R ij算法原理算法原理 查找最短路路径的方法查找最短路路径的方

20、法若1)(prij，则点 p1是点 i 到点 j 的最短路的中间点.然后用同样的方法再分头查找若：（）向点 i 追朔得：2)(1prip,3)(2prip,kipprk)(（）向点 j 追朔得：1)(1qrjp,2)(1qrjq,jrjqm)(pkp2p1p3q1q2qm则由点i到j的最短路的路径为：jqqqpppimk,21,12算法步骤算法步骤D(i,j)：i 到 j 的距离R(i,j)：i 到 j 之间的插入点输入:带权邻接矩阵 w(i,j)例例 求下图中加权图的任意两点间的距离与路径v1v2v4v3v5937422第0步(0)(0)09312345902712345,202412345

21、3201234574012345DR(1)(1)09312345902712345,2024123453201234574012345DR121211第2步(2)(2)0931234590212712315,202412345312201134574012345DR111116161919222222(3)(3)153463346331566091131224902123,112024223453201344035333DR第3步(4)(4)031402462333,7594447 2024234534206133436460453343495DR第4步(5)(4)(5)(4),DDRR TO

22、 MATLAB(road2(floyd)由 v4向 v1追朔：141r所以从 v5到 v1的最短路径为：1435.最最 短短 路路 的的 应应 用用一、一、可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题二、二、选选 址址 问问 题题1、中心问题中心问题2、重心问题重心问题可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题 例例 1 设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的.若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用.现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少.已知该种

23、设备在每年年初的价格为：第一年第二年第三年第四年第五年1111121213 使用不同时间设备所需维修费为：使用年限0112233445维修费5681118构造加权有向图 G1(V,E)（1）顶点集 VXib,i=1,2,3,4,5Xirk(),i=2,3,4,5,6;k=1,2,i-1,每个顶点代表年初的一种决策，其中顶点Xib代表第 i 年初购置新设备的决策，顶点Xirk()代表第 i 年初修理用过 k 年的旧设备的决策也可构造加权有向图 G2(V,E).选址问题选址问题-中心问题中心问题05.15.55.86475.10475.45.25.55.54032475.8730571065.42

24、502545.24720375.5710530DS(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处。TO MATLAB(road3(floyd)选址问题选址问题-重心问题重心问题实验作业实验作业 生产策略问题生产策略问题：现代化生产过程中，生产部门面临的突出问题之一，便是如何选取合理的生产率。生产率过高，导致产品大量积压，使流动资金不能及时回笼；生产率过低，产品不能满足市场需要，使生产部门失去获利的机会。可见，生产部门在生产过程中必须时刻注意市场需求的变化，以便适时调整生产率，获取最大收

25、益。某生产厂家年初要制定生产策略，已预知其产品在年初的需求量为a=6万单位，并以b=1万单位/月速度递增。若生产产品过剩，则需付单位产品单位时间（月）的库存保管费C2=0.2元；若产品短缺，则单位产品单位时间的短期损失费C3=0.4元。假定生产率每调整一次带有固定的调整费C1=1万元，试问工厂如何制定当年的生产策略，使工厂的总损失最小？建模实例 最优截断切割问题1997B 奥运会临时超市网点设计2004B1997B 题题 截断切割截断切割 某些工业部门（如贵重石材加工等）采用截断切割的加工方式。这里“截断切割”是指将物体沿某个切割平面分成两部分。从一个长方体中加工出一个已知尺寸、位置预定的长方

26、体（这两个长方体的对应表面是平行的），通常要经过 6 次截断切割。设水平切割单位面积的费用是垂直切割单位面积费用的 r 倍，且当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时，因调整刀具需额外费用 e。试为这些部门设计一种安排各面加工次序（称“切割方式”）的方 法，使加工费用最少。（由工艺要求，与水平工作台接触的长方体底面 是事先指定的)详细要求如下：1）需考虑的不同切割方式的总数。2）给出上述问题的数学模型和求解方法。3）试对某部门用的如下准则作出评价：每次选择一个加工费用最少的待切割面进行切割。4）对于 e=0 的情形有无简明的优化准则。5）用以下实例验证你的方法：待加工长

27、方体和成品长方体的长、宽、高分别为 10、14.5、19 和 3、2、4，二者左侧面、正面、底面之间的距离分别为 6、7、9（单位均为厘米）。垂直切割费用为每平方厘米 1 元，r 和 e 的数据有以下 4 组：a.r=1,e=0;b.r=1.5,e=0;c.r=8,e=0;d.r=1.5;2=e=15.对最后一组数据应给出所有最优解，并进行讨论。例例 某工厂使用一种设备，这种设备在一定的年限内随着时某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使

28、用旧设更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维修费与运行费增加。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。方案才能使包括购置费、维修费与运行费在内的总费用最小。年份年份1 12 23 34 45 5购置费购置费18182020212123232424使用年数使用年数0 01 11 12 22 23 33 34 44 45 5维修费维修费5 57 7121218182525最短路应用最短路应用 年份年份1 12 23 34 45 5购置费购置费18182020212123232424使用年数使用年数0 01 11 12 22 23 33 34 44 45 5维修费维修费5 57 712121818252528v1v2v3v4v5v62325262930426085324462334530