数学最短路问题.pptx

《数学最短路问题.pptx》由会员分享，可在线阅读，更多相关《数学最短路问题.pptx（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论及其应用 图论概论 最短路问题 行 遍 性 问 题 1、中 国 邮 递 员 问 题 2、推 销 员 问 题第1页/共35页概论图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。

2、第2页/共35页图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。第3页/共35页哥尼斯堡七桥问题在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题归结为：从任一点出发一笔画出七条线再回到起点 问题：要从这四块陆地中的任何一块开始通过每一座 桥正好一次，再回到起点。一笔画的一个判定法则：这个图是连通的，且每个点都 与偶数线相关联 第4页/共35页图与

3、网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。基本问题：匹配问题 最小费用流问题 最大流问题 最短路问题第5页/共35页例1 最短路问题 （SPPshortest path problem）一名货柜车司机奉命在最短的时间内将一车货 物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种 行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问 题相当于需要找到一条从甲地到乙地的最短路。第6页/共35页例2 公路连接问题 某一地区有若干个主要城市

4、，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市 假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？第7页/共35页例3 指派问题 （assignment problem）一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同 一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？第8页/共35页例4 中国邮递员问题 （CPPchinese postman problem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递

5、路线 （从邮局出发，经过投递区内每条街道至少 一次，最后返回邮局）？管梅谷教授 1960年首先提出的 第9页/共35页例5 旅行商问题 （TSPtraveling salesman problem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线 （从驻地出发，经过每个城市恰好一次，最后返回驻地）？第10页/共35页例6 运输问题 （transportation problem）某种原材料有个产地，现在需要将原材料从产 地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本 最低？

6、第11页/共35页两个共同的特点：1、目的都是从若干可能的安排或方案中寻求 某种意义下的最优安排或方案，数学上把 这种问题称为最优化或优化(optimization)问题；2、易于用图形的形式直观地描述和表达，数学 上把这种与图相关的结构称为网络(network)。与图和网络相关的最优化问题就是网络最优化或 称网络优化（netwok optimization）问题。第12页/共35页第13页/共35页最短路问题最短路问题基本内容基本内容2、会用、会用Matlab软件求最短路软件求最短路1、了解最短路的算法及其应用、了解最短路的算法及其应用1、图 论 的 基 本 概 念2、最 短 路 问 题 及

7、 其 算 法3、最 短 路 的 应 用4、建模案例：最优截断切割问题5、实验作业第14页/共35页图 论 的 基 本 概 念一、图 的 概 念1、图的定义2、顶点的次数 3、子图二、图 的 矩 阵 表 示1、关联矩阵2、邻接矩阵返回第15页/共35页定义有序三元组G=(V,E,)称为一个图.图的定义第16页/共35页定义定义第17页/共35页第18页/共35页第19页/共35页顶点的次数第20页/共35页例 在一次聚会中，认识奇数个人的人数一定是偶数。第21页/共35页子图第22页/共35页关联矩阵注：假设图为简单图返回第23页/共35页邻接矩阵注：假设图为简单图第24页/共35页返回第25页

8、/共35页最 短 路 问 题 及 其 算 法一、基 本 概 念二、固 定 起 点 的 最 短 路三、每 对 顶 点 之 间 的 最 短 路返回第26页/共35页基 本 概 念第27页/共35页返回第28页/共35页固 定 起 点 的 最 短 路最短路是一条路径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此,可采用树生长的过程来求指定顶点到其余顶点的最短路第29页/共35页第30页/共35页算法步骤：算法步骤：第31页/共35页 TO MATLAB(road1)第32页/共35页第33页/共35页u1u2u3u4u5u6u7u8返回第34页/共35页感谢您的观看。第35页/共35页