最短路问题课件

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） 一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？中国邮递员问题（CPPchinese postm

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

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

7、对象，因此网络优化又常常被称为网络流（network flows）或网络流规划等 狼、羊、白菜过河问题 猎人要把一只狼、一头羊和一篮白菜从河的左岸带到右岸，但他的渡船太小，一次只能带一样。因为狼要吃羊，羊会吃白菜，所以狼和羊，羊和白菜不能在无人监视的情况下相处。问猎人怎样才能达到目的？图 论 的 基 本 概 念一、 图 的 概 念1、图的定义2、顶点的次数 3、子图二、 图 的 矩 阵 表 示1、 关联矩阵2、 邻接矩阵返回定义有序三元组G=(V,E, )称为一个图.图的定义定义定义顶点的度数例 在一次聚会中，认识奇数个人的人数一定是偶数。子图关联矩阵注：假设图为简单图邻接矩阵注：假设图为简单

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

9、B(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)u23(u1,u2)u66

10、(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)u7u8u3u4u6u7u1u3u2u6u5u4u7u8u1u2u3u4u5u6u7u8124

11、3553317284例 求出点1到其余各顶点的最短有向路的长度？Dijkstra算法:选址问题：已知某地区的交通网络如图5-39所示，其中点代表居民区，边表示公路， 为小区间公路距离，问区中心医院建在哪个小区，可使距离医院最远的小区居民就诊时所走的路程最近?V1V3V4V6V7V2V5602030251520183015解：实际是要求出图的中心，可以化为一系列求最短路问题。先求出v1到其他各顶点的最短路长dj,令D(v1)=maxd1,d2,d7,表示若医院建在v1, 则离医院最远的小区距离为D(v1),再依次计算v2，v3，v7到其余各点的最短路，类似求出D(v2)，D(v3)，D(v7)。

12、 D(vi)(i=1，2，7)中最小者即为所求，计算结果见下表。 由于 D(v6)=48最小，所以医院建在v6，此时离医院最远的小区 v5距离为48。由于 D(v6)=48最小，所以医院建在v6，此时离医院最远的小区 v5距离为48。v1v2v3v4v5v6v7D(vi)V1030506393456093V2300203363153063V3502002050254050V4633320030183363V5936350300486393V6451525184801548V7603040336315063 人、狼、羊、菜四种的任意组合共有16种。其中狼羊菜、狼羊、羊菜三种不允许出现，所以人、人

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

14、模型，利用图论工具来解决 这样摆渡问题就转化成在图中找出以“人狼羊菜”为起点，以“空”为终点的简单路。每 对 顶 点 之 间 的 最 短 路1、求距离矩阵的方法2、求路径矩阵的方法3、查找最短路路径的方法（一）算法的基本思想（三）算法步骤算法的基本思想算法原理 求距离矩阵的方法算法原理 求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R ij算法原理 查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：算法步骤v1v2v4v3v5937422第0步121211第2步111116161919222222第3步第4步 TO MATLAB(road2(floyd)一、 可

15、化为最短路问题的多阶段决策问题二、 选 址 问 题1、 中心问题2、 重心问题可化为最短路问题的多阶段决策问题 选址问题-中心问题S(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) 选址问题-重心问题实验作业 生产策略问题：现代化生产过程中，生产部门面临的突出问题之一，便是如何选取合理的生产率。生产率过高，导致产品大量积压，使流动资金不能及时回笼；生产率过低，产品不能满足市场需要，使生产部门失去获利的机会。可见，生产部门在生产过

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

17、成两部分。从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过 6 次截断切割。 设水平切割单位面积的费用是垂直切割单位面积费用的 r 倍，且当先后两次垂直切割的平面 ( 不管它们之间是否穿插水平切割 ) 不平行时，因调整刀具需额外费用 e 。 试为这些部门设计一种安排各面加工次序（称“切割方式”）的方 法，使加工费用最少。（由工艺要求，与水平工作台接触的长方体底面 是事先指定的)详细要求如下： 1 ）需考虑的不同切割方式的总数。 2 ）给出上述问题的数学模型和求解方法。3 ）试对某部门用的如下准则作出评价：每次选择一个加工费用最少的待切割面进行切割。 4 ）对于 e = 0 的情形有无简明的优化准则。5 ）用以下实例验证你的方法：待加工长方体和成品长方体的长、宽、高分别为 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. 对最后一组数据应给出所有最优解，并进行讨论。 例 某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工