数学建模离散模型培训.ppt

《数学建模离散模型培训.ppt》由会员分享，可在线阅读，更多相关《数学建模离散模型培训.ppt（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散模型离散模型一、一、差分方程模型差分方程模型二、二、层次分析法模型层次分析法模型三、三、图与网络模型图与网络模型参考书数学模型姜启源谢金星等著高等教育出版社任何数学建模方面的书计算机语言方面的书(matlab,mathematica,lindogo）数学建模的历史1988.6叶其孝教授在美国讲学期间向美国大学生数学建模竞赛发起者和负责人Fusaro教授了解这项竞赛的情况，商讨中国学生参赛的办法和规则。26我国大学生（北京大学、清华大学、北京理工大学共4个队）首次参加美国大学生数学建模竞赛，自此每年我国都有同学参加这项竞赛。1989.3高校应用数学学报第4卷第1期发表叶其孝教授的文章“美国大

2、学生数学建模竞赛及一些想法”，第一次向国内介绍这项竞赛。7.1美国Fusaro教授访问北京和上海，作了有关美国大学生数学建模竞赛的报告，并与叶其孝、姜启源等讨论数学建模竞赛的组织工作。9上海市举办大学生（数学类）数学模型竞赛，这是我国省、市级首次举办数学建模竞赛。22第三届全国数学建模教学及应用会议在湖南张家界举行，对举办全国性竞赛起了组织作用。（第一、二届会议分别于1986、1988年举行。）24中国工业与应用数学学会第一届第三次常务理事会决定成立数学模型专业委员会，俞文？为主任，姜启源、叶其孝、谭永基为副主任，并责成他们组织1992年部分城市大学生数学模型联赛。这个委员会实际上成为我国大学

3、生数学建模竞赛的主要组织者。291992年部分城市大学生数学模型联赛举行，这是全国性的首届竞赛，10省（市）79所院校的314队参加。模型模型:为了一定目的，对客观事物的一部分为了一定目的，对客观事物的一部分进行简缩、抽象、提炼出来的进行简缩、抽象、提炼出来的原型原型的替代物的替代物.集中反映了原型中人们需要的那一部分特征集中反映了原型中人们需要的那一部分特征什么是什么是数学模型数学模型数学模型定义数学模型定义:对于一个对于一个现实对象现实对象，为了一个，为了一个特定特定目的目的，根据其，根据其内在规律内在规律，作出必要的，作出必要的简化假设简化假设，运用适当的运用适当的数学工具数学工具，得到

4、的一个，得到的一个数学结构数学结构。数学建模数学建模:建立数学模型的全过程（包括表建立数学模型的全过程（包括表述、求解、解释、检验等）述、求解、解释、检验等）数学建模的基本方法数学建模的基本方法机理分析机理分析测试分析测试分析根据对客观事物特性的认识，找出反映根据对客观事物特性的认识，找出反映内部机理的数量规律内部机理的数量规律将对象看作将对象看作“黑箱黑箱”,通过对量测数据的通过对量测数据的统计分析，找出与数据拟合最好的模型统计分析，找出与数据拟合最好的模型机理分析没有统一的方法，主要通过实例研究机理分析没有统一的方法，主要通过实例研究 (CaseStudies)来学习。以下建模主要指机理分

5、析。来学习。以下建模主要指机理分析。二者结合二者结合用机理分析建立模型结构用机理分析建立模型结构,用测试分析确用测试分析确定模型参数定模型参数 数学建模的方法和步骤数学建模的方法和步骤 数学建模的重要意义数学建模的重要意义 数学建模的具体应用数学建模的具体应用 数学建模的一般步骤数学建模的一般步骤模型准备模型准备模型假设模型假设模型构成模型构成模型求解模型求解模型分析模型分析模型检验模型检验模型应用模型应用模模型型准准备备了解实际背景了解实际背景明确建模目的明确建模目的搜集有关信息搜集有关信息掌握对象特征掌握对象特征形成一个形成一个比较清晰比较清晰的的问题问题模模型型假假设设针对问题特点和建模

6、目的针对问题特点和建模目的作出合理的、简化的假设作出合理的、简化的假设在合理与简化之间作出折中在合理与简化之间作出折中模模型型构构成成用数学的语言、符号描述问题用数学的语言、符号描述问题发挥想像力发挥想像力使用类比法使用类比法尽量采用简单的数学工具尽量采用简单的数学工具 数学建模的一般步骤数学建模的一般步骤模型模型求解求解各种数学方法、软件和计算机技术各种数学方法、软件和计算机技术如结果的误差分析、统计分析、如结果的误差分析、统计分析、模型对数据的稳定性分析模型对数据的稳定性分析模型模型分析分析模型模型检验检验与实际现象、数据比较，与实际现象、数据比较，检验模型的合理性、适用性检验模型的合理性

7、、适用性模型应用模型应用 数学建模的一般步骤数学建模的一般步骤数学建模的全过程数学建模的全过程现实对象的信息现实对象的信息数学模型数学模型现实对象的解答现实对象的解答数学模型的解答数学模型的解答表述表述求解求解解释解释验证验证(归纳)(演绎)现现实实世世界界数数学学世世界界表述表述求解求解解释解释验证验证根据建模目的和信息将实际问题根据建模目的和信息将实际问题“翻译翻译”成数学问题成数学问题选择适当的数学方法求得数学模型的解答选择适当的数学方法求得数学模型的解答将数学语言表述的解答将数学语言表述的解答“翻译翻译”回实际对象回实际对象用现实对象的信息检验得到的解答用现实对象的信息检验得到的解答实

8、践理论实践模型的逼真性和可行性模型的逼真性和可行性模型的渐进性模型的渐进性模型的强健性模型的强健性模型的可转移性模型的可转移性模型的非预制性模型的非预制性模型的条理性模型的条理性模型的技艺性模型的技艺性模型的局限性模型的局限性数学模型的特点数学模型的特点数学建模能力的培养数学建模能力的培养数学建模与其说是一门技术，不如说是一门艺术数学建模与其说是一门技术，不如说是一门艺术技术大致有章可循技术大致有章可循艺术无法归纳成普遍适用的准则艺术无法归纳成普遍适用的准则想像力想像力洞察力洞察力判断力判断力 学习、分析、评价、改进别人作过的模型学习、分析、评价、改进别人作过的模型 亲自动手，认真作几个实际题

9、目亲自动手，认真作几个实际题目 *也是一种创新能力的培养也是一种创新能力的培养 *没有没有创新创新，就没有，就没有发展发展，创新促进人类，创新促进人类社会的进步社会的进步.*正处于传统的继承性教育向创新性教育正处于传统的继承性教育向创新性教育转变的时期转变的时期.重要的科学思维方式之一是创新思维，重要的科学思维方式之一是创新思维，创新思维是创新能力的核心与灵魂创新思维是创新能力的核心与灵魂.创新能力的培养创新能力的培养 图与网络模型图与网络模型数学建模中的图论方法数学建模中的图论方法1.图论的起源图论的起源 图论起源于图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉世纪。第一篇图论论文是瑞士

10、数学家欧拉于于1736 年发表的年发表的“哥尼斯堡的七座桥哥尼斯堡的七座桥”。1847年，克希霍夫年，克希霍夫为了给出电网络方程而引进了为了给出电网络方程而引进了“树树”的概念。的概念。1857年，凯莱年，凯莱在计数烷的同分异构物时，也发现了在计数烷的同分异构物时，也发现了“树树”。哈密尔顿于。哈密尔顿于1859年提出年提出“周游世界周游世界”游戏，用图论的术语，就是如何找游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理科学的飞速发展，大大地促进了图论研究和

11、应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。遗传学、心理学、经济学、社会学等学科中。图论中所谓的图论中所谓的“图图”是指某类具体事物和这些事物之间是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个述这个“图图”的几何形象。图论为任何一个包含了一种二元的几何形象。图论为任何一个包含了一种二元关

12、系的离散系统提供了一个数学模型，借助于图论的概念、关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。开始通过每一座桥正好一次，再回到起点。当然可以通过试验去尝试解决这个问题，但该城居民当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功

13、。欧拉为了解决这个问题，采用了建的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个每一座桥用连接相应两点的一条线来代替，从而得到一个有四个有四个“点点”，七条，七条“线线”的的“图图”。问题成为从任一点。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联

14、，将这个判定法则应用通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了于七桥问题，得到了“不可能走通不可能走通”的结果，不但彻底解的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。决了这个问题，而且开创了图论研究的先河。最短路问题、最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题的基本问题2.问题（通过一些例子来了解图解决的问题）问题（通过一些例子来了解图解决的问题）问题一：问题一：最短路问题（最短路问题（SPPshortest path problem）一名货柜车司机奉命在最短的时间内将一车货

15、物从甲地运往乙一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。那么这一问题相当于需要找到一条从甲地到乙地的最短路。问题二：问题二：公路连接问题公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或连接起

16、来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？使得总成本最小？问题三：问题三：指派问题（指派问题（assignment problem）一家公司经理准备安排名员工去完成项任务，每人一项。由于各一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报员工的特点不同，不同的员工去完成同一项任务时所获得的回报是

17、不同的。如何分配工作方案可以使总回报最大？是不同的。如何分配工作方案可以使总回报最大？问题四：问题四：中国邮递员问题（中国邮递员问题（CPPchinese postman problem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先年首先提出的，所以国际上称之为中国邮递员问题。提出的，所以国际上称之为中国邮递员问

18、题。问题五：问题五：旅行商问题（旅行商问题（TSPtraveling salesman problem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。旅行商问题。问题六：问题六：运输问题（运输问题（transportation problem）某种原材料有个产地，现在需要将原材料从产地运往个使用这某种原材料有

19、个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？输方案可以使总运输成本最低？上述问题有两个共同的特点：一是它们的目的都是从若干上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（数学上把这种问题称为最优化或优化（optimizat

20、ion）问）问题；二是它们都易于用图形的形式直观地描述和表达，数题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（学上把这种与图相关的结构称为网络（network）。与图）。与图和网络相关的最优化问题就是网络最优化或称网络优化和网络相关的最优化问题就是网络最优化或称网络优化（netwok optimization）问题。所以上面例子中介绍的）问题。所以上面例子中介绍的问题都是网络优化问题。由于多数网络优化问题是以网络问题都是网络优化问题。由于多数网络优化问题是以网络上的流（上的流（flow）为研究的对象，因此网络优化又常常被称）为研究的对象，因此网络优化又常常

21、被称为网络流（为网络流（network flows）或网络流规划等。）或网络流规划等。3.图论的基本概念图论的基本概念 图定义图定义：图是由顶点集合图是由顶点集合(vertex)(vertex)及顶点间的关系集合组成及顶点间的关系集合组成的一种数据结构：的一种数据结构：Graph Graph(V V,E E)其中其中 V V=x x|x x 某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合；E E=(=(x x,y y)|)|x x,y y V V 或或 E E=y|x x,y y V V&PathPath(x x,y y)是顶点之间关系的有穷集合，也叫做边是顶点之间关系的

22、有穷集合，也叫做边(edge)(edge)集合。集合。PathPath (x x,y y)表示从表示从 x x 到到 y y 的一条单向通路的一条单向通路,它是有方向的。它是有方向的。有向图与无向图有向图与无向图：在有向图中，顶点对在有向图中，顶点对是有序的。在是有序的。在无向图中，顶点对无向图中，顶点对(x,y)(x,y)是无序的。是无序的。完全图：完全图：若有若有 n n 个顶点的无向图有个顶点的无向图有 n(n-1)/2 n(n-1)/2 条边条边,则此则此图为完全无向图。有图为完全无向图。有 n 个顶点的有向图有个顶点的有向图有n(n-1)条边条边,则此图则此图为完全有向图。为完全有向

23、图。邻接顶点：邻接顶点：如果如果(u,v)是是 E(G)中的一条边，则称中的一条边，则称 u 与与 v 互为邻接顶点。互为邻接顶点。若若ek,el至少有一个公共端点至少有一个公共端点,则称则称ek,el 是是彼此相邻彼此相邻的的,简简称称相邻相邻的的 权权：某某些些图图的的边边具具有有与与它它相相关关的的数数,称称之之为为权权。这这种种带带权权图叫做网络。图叫做网络。顶顶点点的的度度：一一个个顶顶点点v v的的度度是是与与它它相相关关联联的的边边的的条条数数。记记作作T TD D(v v)。在有向图中。在有向图中,顶点的度等于该顶点的入度与出度之和。顶点的度等于该顶点的入度与出度之和。顶点顶点

24、 v v 的入度：的入度：以以 v v 为终点的有向边的条数为终点的有向边的条数,记作记作 I ID D(v v););顶点顶点 v v 的出度：的出度：以以 v v 为始点的有向边的条数为始点的有向边的条数,记作记作 O OD D(v v)。度为奇数的顶点个数为偶数度为奇数的顶点个数为偶数.路径：路径：在图在图 G G(V V,E E)中中,若从顶点若从顶点 v vi i 出发出发,沿一些沿一些边经过一些顶点边经过一些顶点 v vp p1 1,v vp p2 2,v vpmpm，到达顶点到达顶点v vj j。则称顶点序则称顶点序列列 (v vi i v vp p1 1 v vp p2 2.v

25、 vpmpm v vj j )为从顶点为从顶点v vi i 到顶点到顶点 v vj j 的路径。的路径。它经过的边它经过的边(v vi i,v vp p1 1)、(v vp p1 1,v vp p2 2)、.、(v vpmpm,v vj j)应是属于应是属于E E 的边。的边。路径长度：路径长度：非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。简单路径：简单路径：若路径上各顶点若路径上各顶点 v v1 1,v v2 2,.,.,v vm m 均不互相重复均不互相重复,则则称这样的路径

26、为简单路径。称这样的路径为简单路径。回路：回路：若路径上第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点v vm m 重合重合,则称则称这样的路径为回路或环。这样的路径为回路或环。连通图与连通分量：连通图与连通分量：在无向图中在无向图中,若从顶点若从顶点v v1 1到顶点到顶点v v2 2有路有路径径,则称顶点则称顶点v v1 1与与v v2 2是连通的。如果图中任意一对顶点都是连通是连通的。如果图中任意一对顶点都是连通的的,则称此图是连通图。非连通图的极大连通子图叫做连通分则称此图是连通图。非连通图的极大连通子图叫做连通分量。量。强连通图与强连通分量：强连通图与强连通

27、分量：在有向图中在有向图中,若对于每一对顶点若对于每一对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和从和从vj到到vi的路径的路径,则称此图是则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。强连通图。非强连通图的极大强连通子图叫做强连通分量。关联：关联：设设ek(vi,vj)为无向图为无向图G中的一中的一条边条边,称称vi,vj为为ek的端点的端点,ek与与vi(或或vj)是是彼此关联彼此关联的的.无边关联的顶点称为无边关联的顶点称为孤立点孤立点.若一条边若一条边所关联的两个顶点重合所关联的两个顶点重合,则称此边为则称此边为环环.ek与与vi(或或vj)的关联次数的关

28、联次数1vivj,2vi vj,0vi(vj)不是ek的端点bavV关联矩阵关联矩阵对无向图对无向图G，其关联矩阵，其关联矩阵M=(mij)ve，其中：，其中：对有向图对有向图G，其关联矩阵，其关联矩阵M=(mij)ve，其中：，其中：邻接矩阵邻接矩阵(Adjacency Matrix)(Adjacency Matrix)图的邻接矩阵就是表示各个顶点之间关系的一个矩阵。图的邻接矩阵就是表示各个顶点之间关系的一个矩阵。设图设图 A=(V,E)A=(V,E)是一个有是一个有 n n 个顶点的图，则图的邻接矩阵定个顶点的图，则图的邻接矩阵定义为：义为：无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是

29、不对称的。无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。在有向图中在有向图中,统计第统计第 i i 行行 1 1 的个数可得顶点的个数可得顶点 i i 的出度，统计第的出度，统计第 j j 行行 1 1 的个数可得顶点的个数可得顶点 j j 的入度。的入度。在无向图中在无向图中,统计第统计第 i i 行行(列列)1)1 的个数可得顶点的个数可得顶点i i 的度。的度。对于网络图（带权图）：对于网络图（带权图）：树的定义：树的定义：连通而不含回路的无向图称为连通而不含回路的无向图称为无向树无向树,简称简称树树,常常用用T表示树表示树.连通分支数大于等于连通分支数大于等于2,且每个连通

30、分支均是树的且每个连通分支均是树的非连通无向图称为非连通无向图称为森林森林.平凡图称为平凡图称为平凡树平凡树.设设T是无向图是无向图G的子图并且为树，则称的子图并且为树，则称T为为G的的树树.若若T是是G的树且为生成子图，则称的树且为生成子图，则称T是是G的的生成树生成树.最小生成树最小生成树使用不同的遍历图的方法，可以得到不同的生成树；使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，按照生成树的定义，n n 个顶点的连通网络的生成树个顶点的连通网络的生成树有有n n 个顶点、个顶点、n-n-1

31、 1 条边。条边。构造最小生成树的准则构造最小生成树的准则必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；必须使用且仅使用必须使用且仅使用 n n-1-1 条边来联结网络中的条边来联结网络中的 n n 个顶点；个顶点；不能使用产生回路的边。不能使用产生回路的边。生成最小树的方法有克鲁斯卡尔算法和普里姆算法生成最小树的方法有克鲁斯卡尔算法和普里姆算法生成最小树的方法有克鲁斯卡尔算法和普里姆算法生成最小树的方法有克鲁斯卡尔算法和普里姆算法 普里姆普里姆(Prim)算法算法 普里姆算法的基本思想：普里姆算法的基本思想：普里姆算法的基本思想：普里姆算法的基本思想：从连通

32、网络从连通网络从连通网络从连通网络 N N=V V,E E 中的某一顶点中的某一顶点中的某一顶点中的某一顶点 u u0 0 出发，选择与出发，选择与出发，选择与出发，选择与它关联的具有最小权值的边它关联的具有最小权值的边它关联的具有最小权值的边它关联的具有最小权值的边(u u0 0,v v)，将其顶点加入到，将其顶点加入到，将其顶点加入到，将其顶点加入到生成生成生成生成树的顶点集合树的顶点集合树的顶点集合树的顶点集合U U中。中。中。中。以后每一步从以后每一步从以后每一步从以后每一步从一个顶点在一个顶点在一个顶点在一个顶点在U U中中中中，而，而，而，而另一个顶点不在另一个顶点不在另一个顶点不

33、在另一个顶点不在U U中中中中的的的的各条边中选择各条边中选择各条边中选择各条边中选择权值最小的边权值最小的边权值最小的边权值最小的边(u u,v v),把它的顶点加入到把它的顶点加入到把它的顶点加入到把它的顶点加入到集合集合集合集合U U中。如此继续下去，直到网络中的所有顶点都加入到生成中。如此继续下去，直到网络中的所有顶点都加入到生成中。如此继续下去，直到网络中的所有顶点都加入到生成中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合树顶点集合树顶点集合树顶点集合U U中为止。中为止。中为止。中为止。采用邻接矩阵作为图的存储表示。采用邻接矩阵作为图的存储表示。采用邻接矩阵作为图的存

34、储表示。采用邻接矩阵作为图的存储表示。用普里姆算法构造最小生成树的过程prim算法如下：，while end用用prim算法求右图的最小生成树。算法求右图的最小生成树。我们用的第一、二、三行分别表示生成树边的起点、终点、我们用的第一、二、三行分别表示生成树边的起点、终点、权集合。权集合。Matlab程序如下：程序如下：clc;clear;M=1000;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;a=a;zeros(2,7);a=a+a;a(

35、find(a=0)=M;result=;p=1;tb=2:length(a);while length(result)=length(a)-1 temp=a(p,tb);temp=temp(:);d=min(temp);jb,kb=find(a(p,tb)=d);j=p(jb(1);k=tb(kb(1);result=result,j;k;d;p=p,k;tb(find(tb=k)=;endresult结果结果result=125447254673504050304245克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：设有一个有设有一个有

36、设有一个有设有一个有 n n n n 个顶点的连通网络个顶点的连通网络个顶点的连通网络个顶点的连通网络 N N N N=V V V V,E E E E,最初先最初先最初先最初先构造一个只有构造一个只有构造一个只有构造一个只有 n n n n 个顶点，没有边的非连通图个顶点，没有边的非连通图个顶点，没有边的非连通图个顶点，没有边的非连通图 T T T T=V V V V,图中每个顶点自成一个连通分量。图中每个顶点自成一个连通分量。图中每个顶点自成一个连通分量。图中每个顶点自成一个连通分量。当在当在当在当在 E E E E 中选到一条具有最小权值的边时中选到一条具有最小权值的边时中选到一条具有最小

37、权值的边时中选到一条具有最小权值的边时,若该边的两个顶点若该边的两个顶点若该边的两个顶点若该边的两个顶点落在不同的连通分量上，则将此边加入到落在不同的连通分量上，则将此边加入到落在不同的连通分量上，则将此边加入到落在不同的连通分量上，则将此边加入到 T T T T 中；否则将此边中；否则将此边中；否则将此边中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所舍去，重新选择一条权值最小的边。如此重复下去，直到所舍去，重新选择一条权值最小的边。如此重复下去，直到所舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。有顶点在同一个连通分量上为止。有顶点在同

38、一个连通分量上为止。有顶点在同一个连通分量上为止。克鲁斯卡尔克鲁斯卡尔克鲁斯卡尔克鲁斯卡尔（Kruskal）算法如下）算法如下:(1)选选使得使得(2)若若已已选选好，好，则则从从中中选选取取，使得，使得(3)直到直到选选得得为为止。止。中无圈，且中无圈，且生成上例中的最小生成树生成上例中的最小生成树Matlab程序如下：clc;clear;M=1000;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;i,j=find(a=0)&(a=M);b

39、=a(find(a=0)&(a=M);data=i;j;b;index=data(1:2,:);loop=max(size(a)-1;result=;whilelength(result)v2index(find(index=v1)=v2;elseindex(find(index=v2)=v1;enddata(:,flag)=;index(:,flag)=;endresult结果结果result=4243146577253040424550502最短路径问题及其算法 最短路径问题：最短路径问题：最短路径问题：最短路径问题：如果从图中某一顶点如果从图中某一顶点如果从图中某一顶点如果从图中某一顶点

40、(称为源点称为源点称为源点称为源点)到达另一到达另一到达另一到达另一顶点顶点顶点顶点(称为终点称为终点称为终点称为终点)的路径可能不止一条，如何找到一条路径的路径可能不止一条，如何找到一条路径的路径可能不止一条，如何找到一条路径的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。使得沿此路径上各边上的权值总和达到最小。使得沿此路径上各边上的权值总和达到最小。使得沿此路径上各边上的权值总和达到最小。问题解法问题解法问题解法问题解法 边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路径问题 Di

41、jkstraDijkstra算法算法算法算法 边上权值为任意值的单源最短路径问题边上权值为任意值的单源最短路径问题边上权值为任意值的单源最短路径问题边上权值为任意值的单源最短路径问题 Bellman Bellman和和和和FordFord算法算法算法算法 所有顶点之间的最短路径所有顶点之间的最短路径所有顶点之间的最短路径所有顶点之间的最短路径 Floyd Floyd算法算法算法算法边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路径问题固定起点的最短路固定起点的最短路最短路有一个重要而明显的性质：最短路是一条路径，且最短路的任一最短路有一个重要而明显的性质：最短路是一条路径，且最短

42、路的任一段也是最短路假设在段也是最短路假设在u0v0的最短路中只取的最短路中只取条，则从条，则从u0到其余顶点的最到其余顶点的最短路将构成短路将构成棵以棵以u0为根的树。因此可采用树生长的过程来求制定顶点到其为根的树。因此可采用树生长的过程来求制定顶点到其余顶点的最短路径余顶点的最短路径.实现这一过程的方法是实现这一过程的方法是Dijkstra算法算法设设G为赋权有向图或无向图，为赋权有向图或无向图，G边上的权均非负边上的权均非负Dijkstra算法：求算法：求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路S：具有永久标号的顶点集：具有永久标号的顶点集对每个顶点，定义两个标记对每个

43、顶点，定义两个标记(l(v)，z(v)，其中：，其中：l(v)：表示从顶点：表示从顶点u0到到v的一条路的权的一条路的权z(v)：v的父亲点，用以确定最短路的路线的父亲点，用以确定最短路的路线算法的过程就是在每一步改进这两个标记，使最终算法的过程就是在每一步改进这两个标记，使最终l(v)为从顶点为从顶点u0到到v的最的最短路的权，输人为带权邻接矩阵短路的权，输人为带权邻接矩阵w(u,v)Dijkstra算法步骤算法步骤matlab程序程序dijkstra.mmatlab程序程序floyd.mRoad.m1可划为最短路径问题的多阶段决策问题可划为最短路径问题的多阶段决策问题多阶段决策问题常用动态

44、规划方法处理：多阶段决策问题常用动态规划方法处理：原问题原问题阶段阶段1阶段阶段2阶段阶段n状态转移方程状态转移方程无论过去的状态和决策如何无论过去的状态和决策如何,对前面的决策所对前面的决策所形成的的状态而言形成的的状态而言,余下的决策必须构成最优余下的决策必须构成最优解解.求解顺序求解顺序状态状态决策决策动态规划方法的特点动态规划方法的特点构造动态递推关系式关系式构造具有艺术性递推关系式解法因问题而异图的最短路问题是典型的多阶段决策图的最短路问题是典型的多阶段决策问题，且具有成型问题，且具有成型Dijkstra算法求解算法求解探索将多阶段决策问题转化为适当的图，在转化为最短路问题，可将问题

45、清晰、直观，解法统一。例例设备更新问题设备更新问题（设备更新问题）企业使用一台设备，每年年初，企设备更新问题）企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的。若业领导就要确定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用，购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用。现要制定一个五年之内的则需支付一定的维修费用。现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少。设备更新计划，使得五年内总的支付费用最少。设备在每年年初设备在每年年初的价格为：的价格为：第1年第2年第3年第4年第5年111112121

46、3使用年限使用年限01 12233445维修费维修费5681118使用不同时间设使用不同时间设备所需维修费为备所需维修费为 ：模型分析模型分析设备在每年年初设备在每年年初的价格为：的价格为：第1年第2年第3年第4年第5年1111121213使用年限使用年限01 12233445维修费维修费5681118使用不同时间设使用不同时间设备所需维修费为备所需维修费为 ：模型建立与求解模型建立与求解G1(V,E)的含的含义为义为：（1）顶顶点集点集每个每个顶顶点代表年初的一种决策，其中点代表年初的一种决策，其中顶顶点点代表第代表第i年初购置年初购置新设备的决策，顶点新设备的决策，顶点 代表第代表第i年初

47、修理用过年初修理用过k年的旧设备的决策年的旧设备的决策.（2）弧集（3）构造加权有向图G1(V,E)Matlab程序程序minroad.m（4）问题转化为顶点到顶点的最短路问题问题转化为顶点到顶点的最短路问题五年的最优购置费为：其中其中 为顶点为顶点 到到 的最短路的权的最短路的权。求得最短路的权为求得最短路的权为5353，而两条最短路分别为：，而两条最短路分别为：因此，计划为第一、三年初购置新设备，或第一、四年初购置因此，计划为第一、三年初购置新设备，或第一、四年初购置新设备，五年费用均最剩，为新设备，五年费用均最剩，为5353。l=Columns 1 through 14 Inf 11 1

48、6 22 30 11 22 16 28 27 22 34 33 33 Columns 15 through 20 30 43 39 39 41 41z=Columns 1 through 14 1 1 6 8 11 1 2 6 3 7 8 4 9 10 Columns 15 through 20 11 5 12 13 14 15另一类图的构造策略另一类图的构造策略此问题也可构造如图所示的加权有向图此问题也可构造如图所示的加权有向图 顶点集顶点集 表示第表示第 年初购置新设备的年初购置新设备的决策，决策，表示第五年底表示第五年底.带权有向边集带权有向边集 权权 表示由这一决策表示由这一决策在第在

49、第 年初到第年初到第 年初的总年初的总费用，如费用，如 弧（弧（，）表示第）表示第 年初年初购置一台设备一直使用到第购置一台设备一直使用到第 年初的决策。年初的决策。问题转化为求问题转化为求 到到 的最短路问题，求得两条最短路为的最短路问题，求得两条最短路为 权为权为5353，与图，与图 的解相同。的解相同。Matlab程序程序minroad1.ml=Inf 11 16 22 30 39z=1 1 1 1 1 3Euler图图定义定义 经过经过G的每条边的迹叫做的每条边的迹叫做G的的Euler迹；闭的迹；闭的Euler迹叫迹叫做做Euler回路或回路；含回路或回路；含Euler回路的图叫做回路

50、的图叫做Euler图。图。直观地讲，直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。出发点的那种图，即不重复地行遍所有的边再回到出发点。定理定理 （i）G是是Euler图的充分必要条件是图的充分必要条件是G连通且每顶点皆偶次。连通且每顶点皆偶次。（ii）G是是Euler图的充分必要条件是图的充分必要条件是G连通且连通且 是圈。是圈。（iii）G中有中有Euler迹的充要条件是迹的充要条件是G连通且至多有两个奇次连通且至多有两个奇次点。点。Euler回路的回路的Fleury算法算法1921年，年，