问题引入与分析.ppt

《问题引入与分析.ppt》由会员分享，可在线阅读，更多相关《问题引入与分析.ppt（98页珍藏版）》请在三一文库上搜索。

1、1. 问题引入与分析,2. 图论的基本概念,3. 最短路问题及算法,第二讲 图论模型,4. 最小生成树及算法,5. 旅行售货员问题,6. 模型建立与求解,1. 问题引入与分析,1) 98年全国大学生数学建模竞赛B题“最佳灾,今年(1998年)夏天某县遭受水灾. 为考察灾情、,组织自救，县领导决定，带领有关部门负责人到,全县各乡（镇）、村巡视. 巡视路线指从县政府,所在地出发，走遍各乡（镇）、村，又回到县政,府所在地的路线.,情巡视路线”中的前两个问题是这样的：,1）若分三组（路）巡视，试设计总路程最,短且各组尽可能均衡的巡视路线.,2）假定巡视人员在各乡（镇）停留时间T=2,小时，在各村停留时

2、间t=1小时，汽车行驶速度V,=35公里/小时. 要在24小时内完成巡视，至少应分,几组；给出这种分组下最佳的巡视路线.,公路边的数字为该路段的公里数.,2) 问题分析：,本题给出了某县的公路网络图，要求的是在不,同的条件下，灾情巡视的最佳分组方案和路线.,将每个乡（镇）或村看作一个图的顶点，各乡,镇、村之间的公路看作此图对应顶点间的边，各条,再回到点O，使得总权（路程或时间）最小.,公路的长度（或行驶时间）看作对应边上的权，所,给公路网就转化为加权网络图，问题就转化图论中,一类称之为旅行售货员问题，即在给定的加权网络,图中寻找从给定点O出发，行遍所有顶点至少一次,如第一问是三个旅行售货员问题

3、，第二问是四,本题是旅行售货员问题的延伸,多旅行售货员问题.,本题所求的分组巡视的最佳路线，也就是m条,众所周知，旅行售货员问题属于NP完全问题，,显然本问题更应属于NP完全问题. 有鉴于此，,经过同一点并覆盖所有其他顶点又使边权之和达到,最小的闭链（闭迹）.,个旅行售货员问题.,即求解没有多项式时间算法.,一定要针对问题的实际特点寻找简便方法，想找到,解决此类问题的一般方法是不现实的，对于规模较大,的问题可使用近似算法来求得近似最优解.,2.图论的基本概念,1) 图的概念,2) 赋权图与子图,3) 图的矩阵表示,4) 图的顶点度,5) 路和连通,1) 图的概念,定义 一个图G是指一个二元组(

4、V(G),E(G)，其中:,其中元素称为图G的顶点.,组成的集合，即称为边集,其中元素称为边.,定义 图G的阶是指图的顶点数|V(G)|, 用,来表示；,2) E(G)是顶点集V(G)中的无序或有序的元素偶对,定义 若一个图的顶点集和边集都是有限集，则称,其为有限图. 只有一个顶点的图称为平凡图，其他的,所有图都称为非平凡图.,定义若图G中的边均为有序偶对,称G为有向,边 为无向边，称e连接 和 ，顶点 和 称,连接,，称 为e的尾，称 为e的头.,若图G中的边均为无序偶对 ，称G为无向图.称,为e的端点.,既有无向边又有有向边的图称为混合图.,常用术语,1) 边和它的两端点称为互相关联.,2

5、)与同一条边关联的两个端点称,为相邻的顶点，与同一个顶点,点关联的两条边称为相邻的边.,3) 端点重合为一点的边称为环，,端点不相同的边称为连杆.,4) 若一对顶点之间有两条以上的边联结，则这些边,称为重边,5) 既没有环也没有重边的图，称为简单图,常用术语,6) 任意两顶点都相邻的简单图,称为完全图. 记为Kv.,7) 若 ， ，且X 中任意两顶点不,，,相邻，Y 中任意两顶点不相邻，则称为二部图或,偶图；若X中每一顶点皆与Y 中一切顶点相邻,称为,完全二部图或完全偶图,记为 (m=|X|,n=|Y|),8) 图 叫做星.,2) 赋权图与子图,定义 若图 的每一条边e 都赋以,一个实数w(e

6、)，称w(e)为边e的权，G 连同边上的权,称为赋权图.,定义 设 和 是两个图.,1) 若 ,称 是 的一个子图,记,2) 若 ， ，则称 是 的生成子图.,3) 若 ，且 ，以 为顶点集，以两端点,均在 中的边的全体为边集的图 的子图，称,为 的由 导出的子图，记为 .,4) 若 ，且 ，以 为边集，以 的端点,集为顶点集的图 的子图，称为 的由 导出的,边导出的子图，记为 .,3) 若 ，且 ，以 为顶点集，以两端点,均在 中的边的全体为边集的图 的子图，称,4) 若 ，且 ，以 为边集，以 的端点,集为顶点集的图 的子图，称为 的由 导出的,边导出的子图，记为 .,为 的由 导出的子图

7、，记为 .,3) 图的矩阵表示,邻接矩阵:,1) 对无向图 ，其邻接矩阵 ，其中：,(以下均假设图为简单图).,2) 对有向图 ,其邻接矩阵 ,其中：,其中：,3) 对有向赋权图 , 其邻接矩阵 ,对于无向赋权图的邻接矩阵可类似定义.,关联矩阵,1) 对无向图 ，其关联矩阵 ,其中：,2) 对有向图 ，其关联矩阵 ,其中：,4) 图的顶点度,定义 1) 在无向图G中，与顶点v关联的边的数目(环,算两次),称为顶点v的度或次数，记为d(v)或 dG(v).,称度为奇数的顶点为奇点，度为偶数的顶点为偶点.,2) 在有向图中，从顶点v引出的边的数目称为顶点,v的出度，记为d+(v)，从顶点v引入的边

8、的数目称为,v的入度，记为d -(v). 称d(v)= d+(v)+d -(v)为顶点v的,度或次数,定理,的个数为偶数,推论 任何图中奇点,5) 路和连通,定义1) 无向图G的一条途径（或通道或链）是指,一个有限非空序列 ，它的项交替,地为顶点和边，使得对 ， 的端点是 和 ,称W是从 到 的一条途径，或一条 途径. 整,数k称为W的长. 顶点 和 分别称为的起点和终点 ,而 称为W的内部顶点.,2) 若途径W的边互不相同但顶点可重复，则称W,为迹或简单链.,3) 若途径W的顶点和边均互不相同，则称W为路,或路径. 一条起点为 ,终点为 的路称为 路,记为,定义,1) 途径 中由相继项构成子

9、序列,称为途径W的节.,2) 起点与终点重合的途径称为闭途径.,3) 起点与终点重合的的路称为圈(或回路)，长,为k的圈称为k阶圈，记为Ck.,4) 若在图G中存在(u,v)路，则称顶点u和v在图G,中连通.,5) 若在图G中顶点u和v是连通的，则顶点u和v之,之间的距离d(u,v)是指图G中最短(u,v)路的长；若没,没有路连接u和v，则定义为无穷大.,6) 图G中任意两点皆连通的图称为连通图,7) 对于有向图G，若 ，且 有,类似地，可定义有向迹，有向路和有向圈.,头 和尾 ，则称W为有向途径.,例 在右图中：,途径或链：,迹或简单链：,路或路径：,圈或回路：,3最短路问题及算法,最短路问

10、题是图论应用的基本问题，很多实际,问题，如线路的布设、运输安排、运输网络最小费,用流等问题,都可通过建立最短路问题模型来求解.,最短路的定义,最短路问题的两种方法：Dijkstra和Floyd算法 .,1) 求赋权图中从给定点到其余顶点的最短路.,2) 求赋权图中任意两点间的最短路.,2) 在赋权图G中，从顶点u到顶点v的具有最小权,定义 1) 若H是赋权图G的一个子图，则称H的各,边的权和 为H的权. 类似地，若,称为路P的权,若P(u,v)是赋权图G中从u到v的路,称,的路P*(u,v)，称为u到v的最短路,3) 把赋权图G中一条路的权称为它的长，把(u,v),路的最小权称为u和v之间的距

11、离，并记作 d(u,v).,1) 赋权图中从给定点到其余顶点的最短路,假设G为赋权有向图或无向图，G边上的权均非,负若 ，则规定,最短路是一条路，且最短路的任一节也是最短路,求下面赋权图中顶点u0到其余顶点的最短路,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代,替i，并转2).,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的

12、,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代,替i，并转2).,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代,替i，并转2).,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代,替i，并转2).,定义 根据顶点v的标号l(v)的取值途径，使 到

13、v,的最短路中与v相邻的前一个顶点w，称为v的先驱,点，记为z(v), 即z(v)=w.,先驱点可用于追踪最短路径. 例5的标号过程也,可按如下方式进行：,首先写出左图带权邻接矩阵,因G是无向图，故W是对称阵,Dijkstra算法：求G中从顶点u0到其余顶点的最短路,设G为赋权有向图或无向图，G边上的权均均非负.,对每个顶点，定义两个标记（l(v)，z(v)），其中:,l(v) ：表从顶点u0到v的一条路的权,z(v) ：v的先驱点，用以确定最短路的路线.,l(v)为从顶点u0到v的最短路的权,算法的过程就是在每一步改进这两个标记，使最终,S：具有永久标号的顶点集.,输入: G的带权邻接矩阵

14、w(u,v),备用-将求最短路与最短路径结合起来:,算法步骤：,首先写出带权邻接矩阵,例 求下图从顶点u0到其余顶点的最短路,因G是无向图，故W是对称阵,见Matlab程序-Dijkstra.doc,2) 求赋权图中任意两顶点间的最短路,算法的基本思想,（I）求距离矩阵的方法.,（II）求路径矩阵的方法.,（III）查找最短路路径的方法.,Floyd算法：求任意两顶点间的最短路.,举例说明,算法的基本思想,（I）求距离矩阵的方法.,（II）求路径矩阵的方法.,在建立距离矩阵的同时可建立路径矩阵R,（III）查找最短路路径的方法.,然后用同样的方法再分头查找若：,（IV）Floyd算法：求任意两

15、顶点间的最短路.,例 求下图中加权图的任意两点间的距离与路径.,插入点 v1，得：,矩阵中带“=”的项为经迭代比较以后有变化的元素.,插入点 v2，得：,矩阵中带“=”的项为经迭代比较以后有变化的元素.,插入点 v3，得：,插入点 v4，得：,插入点 v5，得：,插入点 v6，得：,故从v5到v2的最短路为8,由v6向v5追溯:,由v6向v2追溯:,所以从到的最短路径为：,见Matlab程序-Floyd.doc,4最小生成树及算法,1) 树的定义与树的特征,定义 连通且不含圈的无向图称为树常用T表示.,树中的边称为树枝. 树中度为1的顶点称为树叶.,孤立顶点称为平凡树.,平凡树,定理2 设G是

16、具有n个顶点的图，则下述命题等价：,1) G是树（ G无圈且连通）；,2) G无圈，且有n-1条边；,3) G连通，且有n-1条边；,4) G无圈，但添加任一条新边恰好产生一个圈;,5) G连通，且删去一条边就不连通了（即G为最,最小连通图）；,6) G中任意两顶点间有唯一一条路.,2）图的生成树,定义 若T是包含图G的全部顶点的子图,它又是树,则称T是G的生成树. 图G中不在生成树的边叫做弦.,定理3 图G=(V,E)有生成树的充要条件是图G是连,通的.,证明 必要性是显然的.,（II）找图中生成树的方法,可分为两种：避圈法和破圈法,A 避圈法 : 深探法和广探法,B 破圈法,A 避圈法,定

17、理3的充分性的证明提供了一种构造图的生,成树的方法.,这种方法就是在已给的图G中，每步选出一条边使它与已选边不构成圈，直到选够n-1条边为止. 这种方法可称为“避圈法”或“加边法”,在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：深探法和广探法.,a) 深探法,若这样的边的另一端均已有标号，就退到标号为,步骤如下：,i) 在点集V中任取一点u,ii) 若某点v已得标号，检,端是否均已标号.,若有边vw之w未标号,则给,w代v，重复ii).,i-1的r点,以r代v,重复ii),直到全部点得到标号为止.,给以标号0.,查一端点为v的各边，另一,w以标号i+1，记下边vw.令,例用深探法

18、求出下图10的一棵生成树,0,1,2,3,4,5,6,7,8,9,10,11,12,13,13,a) 深探法,0,1,2,3,4,5,6,7,8,9,10,11,12,步骤如下：,若这样的边的另一端均已有标号，就退到标号为,i) 在点集V中任取一点u,ii) 若某点v已得标号，检,端是否均已标号.,若有边vw之w未标号,则给,w代v，重复ii).,i-1的r点,以r代v,重复ii),直到全部点得到标号为止.,给u以标号0.,查一端点为v的各边，另一,w以标号i+1，记下边vw.令,例用深探法求出下图10的一棵生成树,3,b)广探法,步骤如下：,i) 在点集V中任取一点u,ii) 令所有标号i的

19、点集为,是否均已标号. 对所有未标,号之点均标以i+1,记下这些,iii) 对标号i+1的点重复步,步骤ii)，直到全部点得到,给u以标号0.,Vi,检查Vi,VVi中的边端点,边.,例用广探法求出下图10的一棵生成树,1,0,1,2,2,1,3,2,1,2,2,3,4,标号为止.,3,b)广探法,步骤如下：,i) 在点集V中任取一点u,ii) 令所有标号i的点集为,是否均已标号. 对所有未标,号之点均标以i+1,记下这些,iii) 对标号i+1的点重复步,步骤ii)，直到全部点得到,给u以标号0.,Vi,检查Vi,VVi中的边端点,边.,例用广探法求出下图10的一棵生成树,1,0,1,2,2

20、,1,3,2,1,2,2,3,4,标号为止.,显然图10的生成树 不唯一.,B 破圈法,相对于避圈法，还有一种求生成树的方法叫做“破圈法”. 这种方法就是在图G中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤直到图G中没有圈为止.,例 用破圈法求出,下图的一棵生成树.,B 破圈法,例 用破圈法求出下图的另一棵生成树.,不难发现，图的生成树不是唯一的 .,3) 最小生成树与算法,介绍最小树的两种算法： Kruskal算法（或避圈法）和破圈法.,A Kruskal算法（或避圈法）,步骤如下：,1) 选择边e1，使得w(e1)尽可能小；,2) 若已选定边 ，则从,中选取 ，使得:,i) 为无

21、圈图，,ii) 是满足i)的尽可能小的权，,3) 当第2)步不能继续执行时，则停止.,定理4 由Kruskal算法构作的任何生成树,都是最小树.,例10用Kruskal算法求下图的最小树.,在左图中 权值,最小的边有 任取一条,在 中选取权值,最小的边,中权值最小边有 , 从中选,任取一条边,会与已选边构成圈,故停止,得,中选取在中选取,中选取 . 但 与 都,B破圈法,算法2 步骤如下：,1) 从图G中任选一棵树T1.,2) 加上一条弦e1，T1+e1中,立即生成一个圈. 去掉此,圈中最大权边，得到新,树T2,以T2代T1,重复2)再,检查剩余的弦，直到全,部弦检查完毕为止.,例11用破圈法

22、求下图的最小树.,先求出上图的一棵生成树.,加以弦 e2,得到的圈v1v3v2v1,去掉最大的权边e2,得到一棵新,树仍是原来的树；,再加上弦e7，得到圈 v4v5v2v4,去掉最大的权边e6，得到一棵,新树；如此重复进行，直到全,全部的弦均已试过,得最小树.,5. 旅行售货员问题,定义设G=(V,E)是连通无向图，包含图G的每个,顶点的路称为G的哈密尔顿路(Hamilton路或H路).,包含图G的每个顶点的圈，称为G的哈密尔顿圈,(或Hamilton圈或H圈).,含Hamilton圈的图称为哈密尔顿图(或Hamilton,图或H图).,旅行售货员问题或货郎担问题.,一个旅行售货员想去访问若干

23、城镇，然后回,到出发地.给定各城镇之间的距离后，应怎样计划,他的旅行路线，使他能对每个城镇恰好经过一次,而总距离最小？,它可归结为这样的图论问题：在一个赋权完,全图中,找出一个最小权的H圈,称这种圈为最优圈.,但这个问题是NP-hard问题，即不存在多项式,时间算法.也就是说,对于大型网络(赋权图),目前还,没有一个求解旅行售货员问题的有效算法，因此,只能找一种求出相当好（不一定最优）的解.,一个可行的办法 :,是先求一个H圈,然后适当,修改,以得到具有较小权的另,一个H圈.,定义 若对于某一对i和j，有,则圈Cij将是圈C的一个改进.,二边逐次修正法:,在接连进行一系列修改之后,最后得一个圈

24、,不能,再用此方法改进了，这个最后的圈可能不是最优的,但是它是比较好的，为了得到更高的精度，这个,程序可以重复几次，每次都以不同的圈开始. 这种,方法叫做二边逐次修正法.,例对下图16的K6,用二边逐次修正法求较优H圈.,较优H圈:,其权为W(C3)=192,分析: 找出的这个解的好坏可用最优H圈的权,的下界与其比较而得出.即利用最小生成树可得最,优H圈的一个下界，方法如下：,设C是G的一个最优H圈，则对G的任一顶点v,C-v是G-v的路，也G-v是的生成树.如果T是G-v的,最小生成树,且e1是e2与v关联的边中权最小的两条,边,则w(T)+w(e1)+w(e2)将是w(C)的一个下界.,取

25、v=v3,得G-v3的一,最小生成树(实线),其,权w(T)=122,与v3关联,的权最小的两条边为,w(T)+w(v1v3)+w(v2v3),=178.故最优H圈的权,v1v3和v2v3,故w(C),应满足178 w(C) 192.,6. 最佳灾情巡视路线的模型的建立与求解,问题转化为在,给定的加权网,络图中寻找从,给定点O出发,行遍所有顶点,至少一次再回,回到点O ,使得,总权(路程或时,时间)最小,即,最佳旅行售货,员问题.,最佳旅行售货员问题是NP完全问题,采用一种,近似算法求其一个近似最优解，来代替最优解.,算法一 求加权图的最佳旅行售货员回路近似算法:,1) 用图论软件包求出G中任

26、意两个顶点间的最短路,构造出完全图,2) 输入图 的一个初始H圈；,3) 用对角线完全算法（见3）产生一个初始圈;,4) 随机搜索出 中若干个H圈，例如2000个；,5) 对第2)，3)，4)步所得的每个H圈，用二边逐次,修正法进行优化，得到近似最优H圈；,6) 在第5)步求出的所有H圈中，找出权最小的一个,此即要找的最优H圈的近似解.,因二边逐次修正法的结果与初始圈有关,故本算法,第2)，3)，4)步分别用三种方法产生初始圈，以保,证能得到较优的计算结果.,问题一 若分为三组巡视，设计总路程最短且各,组尽可能均衡的巡视路线.,此问题是多个售货员的最佳旅行售货员问题.,4),此问题包含两方面：

27、a)对顶点分组, b)在每组中,求(单个售货员)最佳旅行售货员回路.,因单个售货员的最佳旅行售货员回路问题不存,存在多项式时间内的精确算法.,故多,也不,而图中节点数较多，为53个，我们只能去寻求,一种较合理的划分准则，对图1进行粗步划分后,求,出各部分的近似最佳旅行售货员回路的权,再进一,进一步进行调整，使得各部分满足均衡性条件3).,从O点出发去其它点，要使路程较小应尽量走,O点到该点的最短路.,故用软件包求出O点到其余顶点的最短路.,这些最短路构成一棵O为树根的树.,将从O点出发的树枝称为干枝.,从O点出发到其它点共有6条干枝，它们的名称,分别为，.,在分组时应遵从准则：,准则1 尽量使

28、同一干枝上及其分枝上的点分在同一组.,准则2 应将相邻的干枝上的点分在同一组；,准则3 尽量将长的干枝与短的干枝分在同一组.,由上述分组准则，我们找到两种分组形式如下：,分组1:（，），（，），（，）,分组2:（，），（，），（，）,分组1极不均衡,故考虑分组2.,分组2:(,),(,),(,),对分组2中每组顶点的生成子图,用算法一求出近似最优解及相应的巡视路线.,在每个子图所构造的完全图中,取一个尽量包含上图中树上的边的H圈作为其第2)步输入的初始圈.,分组2的近似解,因为该分组的均衡度,. 所以此分法的均衡性很差.,为改善均衡性，将第组中的顶点C,2,3,D,4,分给第组（顶点2为这两组

29、的公共点），重新分,分组后的近似最优解见表2.,因该分组的均衡度,所以这种分法的均衡性较好.,问题二 当巡视人员在各乡（镇）、村的停留,停留时间一定,汽车的行驶速度一定,要在24小时内,完成巡视,至少要分几组及最佳旅行的巡视路线.,由于T=2小时,t=1小时,V=35公里/小时,需访问,的乡镇共有17个，村共有35个. 计算出在乡(镇)及,村的总停留时间为17 2+35=69小时，要在24小时,内完成巡回，若不考虑行走时间，有: 69/i24(i为,分的组数). 得i最小为4，故至少要分4组.,由于该网络的乡(镇)、村分布较为均匀,故有可,能找出停留时间尽量均衡的分组,当分4组时各组停,停留时

30、间大约为69/4=17.25小时，则每组分配在路,路途上的时间大约为24-17.25=6.75小时.而前面讨,论过,分三组时有个总路程599.8公里的巡视路线，,分4组时的总路程不会比599.8公里大太多,不妨以,599.8公里来计算.路上约用599.8/35=17小时,若平,均分配给4个组,每个组约需17/4=4.25小时6.75小,小时,故分成4组是可能办到的.,现在尝试将顶点分为4组.分组的原则：除遵从,前面准则1、2、3外，还应遵从以下准则：,准则4 尽量使各组的停留时间相等.,用上述原则在下图上将图分为4组，同时计算,各组的停留时间,然后用算法一算出各组的近似最,最佳旅行售货员巡回，得出路线长度及行走时间,从而得出完成巡视的近似最佳时间. 用算法一计,计算时，初始圈的输入与分三组时同样处理.,这4组的近似最优解见表3.,表3符号说明：加有底纹的表示前面经过并停留过,此次只经过不停留;加框的表示此点只经过不停留.,可看出,表3分组的均衡度很好,且完全满足24,小时完成巡视的要求.,该分组实际均衡度 4.62%,再见,