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

《第1讲 最短路问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

5、同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？中国邮递员问题（CPP－chinesepostmanproblem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。旅行商问题（TSP－travelingsalesmanproblem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问

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

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

8、矩阵返回定义有序三元组G=(V,E,)称为一个图.图的定义定义定义