数学图论模型.pptx

《数学图论模型.pptx》由会员分享，可在线阅读，更多相关《数学图论模型.pptx（90页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第二章第二章 图论模型图论模型一、一、问题引入与分析问题引入与分析二、图论的基本概念二、图论的基本概念三、三、最短路问题及算法最短路问题及算法 四、最小生成树及算法四、最小生成树及算法 五、五、旅行售货员问题旅行售货员问题六、六、模型建立与求解模型建立与求解目录下页返回上页结束第1页/共90页1.98年全国大学生数学建模竞赛年全国大学生数学建模竞赛B题题“最佳灾最佳灾 今年(1998年)夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.情巡视路线情巡视路线”中的前两个问题是

2、这样的：中的前两个问题是这样的：一、问题引入与分析一、问题引入与分析目录下页返回上页结束第2页/共90页 1）若分三组（路）巡视，试设计总路程最）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线.2）假定巡视人员在各乡（镇）停留时间）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里公里/小时小时.要在要在24小时内完成巡视，至少应分小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.目录下页返回上页结束第3页/共90页公路边的数字为该路段的公里数公路边的数字为该路段的公里数.目录下页返回上页结束第4页/共90页2.2.问题分析

3、：问题分析：本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各次再回到点O，使得总权（路程或时间）最小.条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一目录下页返回上页结束第5页/共90页 如第一问是三个旅行售货员问题，第二问是四本题是旅行售货员问题的延伸-多旅行售货员问题.本题所求的分组巡视的最佳路线，也就是m条众所周知，旅行售货员问题属于NP完全问题，

4、显然本问题更应属于NP完全问题.有鉴于此，经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.个旅行售货员问题.即求解没有多项式时间算法.一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.目录下页返回上页结束第6页/共90页二、图论的基本概念二、图论的基本概念目录下页返回上页结束1)图的概念图的概念2)赋权图与子图赋权图与子图3)图的矩阵表示图的矩阵表示4)图的顶点度图的顶点度5)路和连通路和连通第7页/共90页 定义定义 一个图G是指一个二元组(V(G),E(G)，其中:其中元素称为图G的顶点.组成的集

5、合，即称为边集,其中元素称为边.定义定义 图G的阶是指图的顶点数|V(G)|,用来表示；图的边的数目|E(G)|用 来表示.也用来表示边是非空有限集，称为顶点集，1)2)E(G)是顶点集V(G)中的无序或有序的元素偶对表示图，简记 用1)图的概念目录下页返回上页结束第8页/共90页定义定义 若一个图的顶点集和边集都是有限集，则称 其为有限图.只有一个顶点的图称为平凡图，其他的 所有图都称为非平凡图.目录下页返回上页结束第9页/共90页 定义定义若图G中的边均为有序偶对(vi,vj)，称G为有向图.称边 为有向边或弧,称 是从连接 ,称 为e的尾，称 为e的头.若图G中的边均为无序偶对 ，称G为

6、无向图.称为e的端点.边 为无向边，称e连接 和 ，顶点 和 称 既有无向边又有有向边的图称为混合图.目录下页返回上页结束第10页/共90页 常用术语常用术语1)边和它的两端点称为互相关联.2)与同一条边关联的两个端点称为相邻的顶点，与同一个顶点 点关联的两条边称为相邻的边.3)端点重合为一点的边称为环，端点不相同的边称为连杆.4)若一对顶点之间有两条以上的边联结，则这些边 称为重边5)既没有环也没有重边的图，称为简单图 目录下页返回上页结束第11页/共90页常用术语常用术语6)任意两顶点都相邻的简单图,称为完全图.记为Kv.7)若 ，且X 中任意两顶点不 相邻，Y 中任意两顶点不相邻，则称为

7、二部图或 偶图；若X中每一顶点皆与Y 中一切顶点相邻,称为完全二部图或完全偶图,记为 (m=|X|,n=|Y|)8)图 叫做星.二部图目录下页返回上页结束第12页/共90页 定义定义 若图G=(V(G),E(G)的每一条边e 都赋以一个实数w(e)，称w(e)为边e的权，G 连同边上的权称为赋权图.定义定义 设 和 是两个图.1)若 ,称 是 的一个子图,记 2)若 ，则称 是 的生成子图.3)若 ，且 ，以 为顶点集，以两端点 均在 中的边的全体为边集的图 的子图，称 为 的由 导出的子图，记为 .4)若 ，且 ，以 为边集，以 的端点 集为顶点集的图 的子图，称为 的由 导出的 边导出的子

8、图,记为 .2)赋权图与子图赋权图与子图目录下页返回上页结束第13页/共90页 3)若 ，且 ，以 为顶点集，以两端点 均在 中的边的全体为边集的图 的子图，称 4)若 ，且 ，以 为边集，以 的端点 集为顶点集的图 的子图，称为 的由 导出的 边导出的子图,记为 .为 的由 导出的子图，记为 .目录下页返回上页结束第14页/共90页1)对无向图 ，其邻接矩阵 ，其中：邻接矩阵:(以下均假设图为简单图).3)图的矩阵表示图的矩阵表示目录下页返回上页结束第15页/共90页2)对有向图 ,其邻接矩阵 ,其中：目录下页返回上页结束第16页/共90页其中：3)对有向赋权图 ,其邻接矩阵 ,对于无向赋权

9、图的邻接矩阵可类似定义.目录下页返回上页结束第17页/共90页1)对无向图 ，其关联矩阵 ,其中：关联矩阵关联矩阵目录下页返回上页结束第18页/共90页2)对有向图 ，其关联矩阵 ,其中：目录下页返回上页结束第19页/共90页目录下页返回上页结束定义定义 1)在无向图G中，与顶点v关联的边的数目(环算两次),称为顶点v的度或次数，记为d(v)或 dG(v).称度为奇数的顶点为奇点，度为偶数的顶点为偶点.2)在有向图中，从顶点v引出的边的数目称为顶点 v的出度，记为d+(v)，从顶点v引入的边的数目称为 v的入度，记为d-(v).称d(v)=d+(v)+d-(v)为顶点v的 度或次数定理定理的个

10、数为偶数推论推论 任何图中奇点4)图的顶点度图的顶点度第20页/共90页目录下页返回上页结束 定义定义1)无向图G的一条途径（或通道或链）是指一个有限非空序列 ，它的项交替 地为顶点和边，使得对 ，的端点是 和 ,称W是从 到 的一条途径，或一条 途径.整数k称为W的长.顶点 和 分别称为起点和终点,而 称为W的内部顶点.2)若途径W的边互不相同但顶点可重复，则称W为迹或简单链.3)若途径W的顶点和边均互不相同，则称W为路或路径.一条起点为 ,终点为 的路称为 路记为5)路和连通路和连通第21页/共90页目录下页返回上页结束 定义定义 1)途径 中由相继项构成子序列 称为途径W的节.2)起点与

11、终点重合的途径称为闭途径.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，则定义为无穷大.第22页/共90页目录下页返回上页结束 6)图图G中任意两点皆连通的图称为中任意两点皆连通的图称为连通图连通图 类似地，可定义有向迹，有向路和有向圈.7)对于有向图G，若 ，且 有头 和尾 ，则称W为有向途径.例 在右图中：途径或链：迹或简单链：路或路径：圈或回路：第23页/共90页目录下页返回上页

12、结束三、最短路问题及算法三、最短路问题及算法 最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费用流等问题,都可通过建立最短路问题模型来求解.最短路的定义最短路问题的两种方法：Dijkstra和Floyd算法.1)1)求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路.2)求赋权图中任意两点间的最短路.第24页/共90页目录下页返回上页结束 2)在赋权图G中，从顶点u到顶点v的具有最小权 定义定义 1)若H是赋权图G的一个子图，则称H的各边的权和 为H的权.类似地，若称为路P的权若P(u,v)是赋权图G中从u到v的路,称 的路P*(u,v

13、)，称为u到v的最短路 3)把赋权图G中一条路的权称为它的长，把(u,v)路的最小权称为u和v之间的距离，并记作 d(u,v).第25页/共90页目录下页返回上页结束1)1)求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路 解决上述问题的一个方法是由Dijkstra于1959年提出的算法，此算法不仅能求出赋权图指定两点最短路.目前它是求无负权图最短路的最好方法.间的最短路，而且能求出从指定点到其余各顶点的 该算法基本原理：若 是赋权图G中从 到 的最短路，则 必为从 到的最短路，则称 是 的先驱点,记为 ,它可用于追踪最短路的路径.最短路是一条路，且最短路的任一节也是最

14、短路第26页/共90页目录下页返回上页结束 假设G为赋权有向图或无向图，G边上的权均非负若 ，则规定 求下面赋权图G中顶点v0到其余顶点的最短路第27页/共90页输入：图G的带权邻接矩阵W.目录下页返回上页结束Dijkstra算法算法:求G中从顶点 到其余顶点的最短路.对每个顶点，定义两个标记（l(v),t(v)），其中:l(v)表示从顶点到的一条路的权t(v)表示的先驱点，它可用以确定最短路的路径.算法的过程就是在每一步改进这两个标记(l(v),t(v),使最终l(v)为从顶点v0到v的最短路的权S：具有永久标号的顶点集.第28页/共90页目录下页返回上页结束Dijkstra算法步骤算法步骤

15、:用上述算法求出的用上述算法求出的l(v)就是就是v0到到v的最短路的权的最短路的权,(1)初始化操作:置S=v0,l(v0)=0,对每个 ,令 (2)设设v*是使是使l(v)取最小值的取最小值的 中的顶点，即中的顶点，即 ，则令 ，.若 ，停止.否则，转（3）.(3)更新l(v)、t(v)：对每个 ，若l(v)l(u)+w(u,v),则令l(v)=l(u)+w(u,v),转(2).从v的先驱点标记t(v)追溯到v0,就得到v0到v的最短路的路径.第29页/共90页 (1)初始化操作:置S=v0,l(v0)=0,对每个令停止.否则，转（3）.,则令 ，.若 ,(3)更新l(v)、t(v):对每

16、个 ,若l(v)l(u)+w(u,v),则令l(v)=l(u)+w(u,v),转(2).(2)设设v*是是使使l(v)取取最最小小值值的的 中中的的顶顶点点，即即 (2)设设v*是使是使l(v)取最小值的取最小值的 中的顶点中的顶点,即即置S=v0,l(v0)=0,方框把0 0框起来.给与v0相邻的顶点 分别标以l(v1)=w(v0v1)=w011,l(v2)=2,l(v4)=7,l(v6)=4,l(v7)=8.v1,v2,v4,v6,v7,其余顶点均标以 ,即l(v3)=,l(v5)=.第30页/共90页 (1)初始化操作:置S=v0,l(v0)=0,对每个令停止.否则，转（3）.,则令 ，

17、.若 ,(3)更新l(v)、t(v):对每个 ,若l(v)l(u)+w(u,v),则l(v)=l(u)+w(u,v),转(2).(2)设设v*是是使使l(v)取取最最小小值值的的 中中的的顶顶点点，即即 (2)设设v*是使是使l(v)取最小值的取最小值的 中的顶点中的顶点,即即对每个 记t(v)=v0,即它们的先驱点均为v0。在中取标号最小者l(v1)=1.用方框把1框起来.令 第31页/共90页 (1)初始化操作:置S=v0,l(v0)=0,对每个令停止.否则，转（3）.,则令 ，.若 ,(3)更新l(v)、t(v):对每个 ,若l(v)l(u)+w(u,v),则l(v)=l(u)+w(u,

18、v),转(2).(2)设设v*是是使使l(v)取取最最小小值值的的 中中的的顶顶点点，即即的算法步骤(3)重新 (2)设设v*是使是使l(v)取最小值的取最小值的 中的顶点中的顶点,即即 令用Dijkstra的标号l(v)、t(v).经计改进顶点算只有v3满足条件:则给v3标以l(v3)=4.令 t(v3)=v1,此时其它点的两个标号l(v)、t(v)保持不变。第32页/共90页 (1)初始化操作:置S=v0,l(v0)=0,对每个令停止.否则，转（3）.,则令 ，.若 ,(3)更新l(v)、t(v):对每个 ,若l(v)l(u)+w(u,v),则l(v)=l(u)+w(u,v),转(2).(

19、2)设设v*是是使使l(v)取取最最小小值值的的 中中的的顶顶点点，即即 (2)设设v*是使是使l(v)取最小值的取最小值的 中的顶点中的顶点,即即 重复上面的做法，能在改进为止。直到所有顶点的两个标号l(v)、t(v)不目录下页返回上页结束第33页/共90页目录下页返回上页结束第34页/共90页目录下页返回上页结束第35页/共90页目录下页返回上页结束定义 根据顶点v的标号l(v)的取值途径，使 到v的最短路中与v相邻的前一个顶点w，称为v的先驱点，记为t(v),即t(v)=w.先驱点可用于追踪最短路径.上例的标号过程也可按如下方式进行：首先写出左图带权邻接矩阵因G是无向图，故W是对称阵第3

20、6页/共90页目录下页返回上页结束第37页/共90页目录下页返回上页结束见Visual C+6.0程序-Dijkstra.cpp第38页/共90页目录下页返回上页结束（I）求距离矩阵的方法.（II）求路径矩阵的方法.（III）查找最短路路径的方法.Floyd算法：求任意两顶点间的最短路.举例说明2)求赋权图中任意两顶点间的最短路求赋权图中任意两顶点间的最短路算法的基本思想算法的基本思想第39页/共90页算法的基本思想算法的基本思想直接在图的带权邻接矩阵中用插入顶点的方法依次构造出v个矩阵D(1)、D(2)、D(v)，使最后得到的矩阵D(v)成为图的距离矩阵，同时 也求出插入点矩阵以便得到两点间

21、的最短路径目录下页返回上页结束第40页/共90页目录下页返回上页结束（I）求距离矩阵的方法）求距离矩阵的方法.设赋权图G的顶点集为 .1）写出赋权图写出赋权图G的带权邻接矩阵的带权邻接矩阵W，把它作为距把它作为距离离矩阵的初值，即2）对k=1,2,v，计算 其中表示从vi到vj且中间点仅为v1,v2,vk的k个点的所有路径中的最短路的长度。于是 中元素 就是从 到 的路径中间可插入任何顶点的路径中最短路的长度，即 就是所求距离矩阵.第41页/共90页目录下页返回上页结束在建立距离矩阵的同时可建立路径矩阵R（II）求路径矩阵的方法）求路径矩阵的方法.设 ，这里 的含义是从 到的最短路要经过点号为

22、 的点.算法开始于 ，迭代到第k步，即由 到 迭代，若某个元素改变（变小），则由 到 迭代中，相应元素改为k，表示到第k次迭代,从 到 的最短路过点 比过原中间点更短.在求得 时求得 ，可由 来查找任何点对之间最短路的路径.第42页/共90页然后用同样的方法再分头查找若：（III）查找最短路路径的方法）查找最短路路径的方法.目录下页返回上页结束第43页/共90页(IV)Floyd算法算法:求任意两顶点间的最短路求任意两顶点间的最短路.d(i,j)：i到j的距离r(i,j)：i到j之间的插入点输入:带权邻接矩阵 .(1)赋初值赋初值:对所有对所有i,j,d(i,j)w(i,j),r(i,j)j,

23、k 1.(2)更新更新d(i,j),r(i,j):对所有对所有i,j,若若d(i,k)+d(k,j)d(i,j),则 d(i,j)d(i,k)+d(k,j),r(i,j)k.(3)若若k=v，停止否则，停止否则k k+1，转，转(2)目录下页返回上页结束第44页/共90页目录下页返回上页结束例例 求下图中加权图的任意两点间的距离与路径.第45页/共90页目录下页返回上页结束插入点 v1，得：矩阵中带“=”的项为经迭代比较以后有变化的元素.第46页/共90页插入点 v2，得：矩阵中带“=”的项为经迭代比较以后有变化的元素.目录下页返回上页结束第47页/共90页插入点 v3，得：目录下页返回上页结

24、束第48页/共90页插入点 v4，得：插入点 v5，得：目录下页返回上页结束第49页/共90页插入点 v6，得：目录下页返回上页结束第50页/共90页故从v5到v2的最短路为8 由v6向v5追溯:由v6向v2追溯:所以从到的最短路径为：见Visual C+6.0程序Floyd.cpp如下。目录下页返回上页结束第51页/共90页四、最小生成树及算法四、最小生成树及算法目录下页返回上页结束1)树的定义与树的特征定义定义 连通且不含圈的无向图称为树常用T表示.树中的边称为树枝.树中度为1的顶点称为树叶.孤立顶点称为平凡树.平凡树第52页/共90页目录下页返回上页结束1)G是树（是树（G无圈且连通）；

25、无圈且连通）；2)G无圈，且有n-1条边；3)G连通，且有连通，且有n-1条边；条边；4)G无圈，但添加任一条新边恰好产生一个圈无圈，但添加任一条新边恰好产生一个圈;5)G连通，且删去一条边就不连通了（即连通，且删去一条边就不连通了（即G为为最最最小连通图）；6)G中任意两顶点间有唯一一条路中任意两顶点间有唯一一条路.定理定理2 设设G是具有是具有n个顶点的图，则下述命题等价：个顶点的图，则下述命题等价：第53页/共90页定义定义 若T是包含图G的全部顶点的子图,它又是树,则称T是G的生成树.图G中不在生成树的边叫做弦.定理定理3 图G=(V,E)有生成树的充要条件是图G是连 通的.证明证明:

26、必要性是显然的.2）图的生成树）图的生成树目录下页返回上页结束充分性充分性：任取 ，令集合 ，这时生成树 的边集 为空集.因为 是连通图，点集 与 之间必有边相连，设 为这样的边，第54页/共90页目录下页返回上页结束 属于 而 属于 。则得 ，。重复进行上述步骤，对于 ,仍能找到边 满足其一端在点集 ，另一端在点集 中.由于 有一端在 之外，所以 与 中的 边不构成圈.当 时，得到 ，即图 有 条边且无圈，由定理2知，这是一棵树，且为图 的一棵生成树.第55页/共90页目录下页返回上页结束可分为两种：避圈法和破圈法 A 避圈法避圈法:深探法和广探法深探法和广探法 B 破圈法（II）找图中生成

27、树的方法）找图中生成树的方法第56页/共90页目录下页返回上页结束 定理3的充分性的证明提供了一种构造图的生 成树的方法.止.这种方法可称为“避圈法”或“加边法”成树的方法可分为两种：深探法和广探法.A 避圈法避圈法 这种方法就是在已给的图G中，每步选出一条边使它与已选边不构成圈，直到选够n-1条边为 在避圈法中，按照边的选法不同，找图中生第57页/共90页目录下页返回上页结束a)深探法深探法 若这样的边的另一端均已有标号，就退到标号为步骤如下：i)在点集V中任取一点u,ii)若某点v已得标号，检端是否均已标号.若有边vw之w未标号,则给w代v，重复ii).i-1的r点,以r代v,重复ii),

28、直到全部点得到标号为止.给以标号0.查一端点为v的各边，另一w以标号i+1，记下边vw.令例用深探法求出下图10的一棵生成树 图10012345678910111213第58页/共90页目录下页返回上页结束13a)深探法深探法图100123456789101112步骤如下：若这样的边的另一端均已有标号，就退到标号为i)在点集V中任取一点u,ii)若某点v已得标号，检端是否均已标号.若有边vw之w未标号,则给w代v，重复ii).i-1的r点,以r代v,重复ii),直到全部点得到标号为止.给u以标号0.查一端点为v的各边，另一w以标号i+1，记下边vw.令例用深探法求出下图10的一棵生成树 第59

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

30、直到全部点得到给u以标号0.Vi,检查Vi,VVi中的边端点边.例例用广探法求出下图用广探法求出下图10的一棵生成树的一棵生成树 图101012213212234标号为止.显然图10的生成树不唯一.第61页/共90页目录下页返回上页结束意舍弃一条边，将这个圈破掉，重复这个步骤直例 用破圈法求出下图的一棵生成树.B 破圈法破圈法 相对于避圈法，还有一种求生成树的方法叫做“破圈法”.这种方法就是在图G中任取一个圈，任到图G中没有圈为止.第62页/共90页目录下页返回上页结束例 用破圈法求出下图的另一棵生成树.B 破圈法破圈法不难发现，图的生成树不是唯一的.第63页/共90页 介绍最小树的两种算法：

31、Kruskal算法（或避圈法）和破圈法.3)最小生成树与算法最小生成树与算法目录下页返回上页结束第64页/共90页目录下页返回上页结束步骤如下：1)选择边e1，使得w(e1)尽可能小；2)若已选定边 ，则从中选取 ，使得:i)为无圈图，ii)是满足i)的尽可能小的权，3)当第2)步不能继续执行时，则停止.定理定理4 由Kruskal算法构作的任何生成树都是最小树.A Kruskal算法（或避圈法）算法（或避圈法）第65页/共90页目录下页返回上页结束例10用Kruskal算法求下图的最小树.在左图中 权值最小的边有 任取一条 在 中选取权值最小的边 中权值最小边有 ,从中选任取一条边会与已选边

32、构成圈,故停止,得中选取在中选取 中选取 .但 与 都第66页/共90页目录下页返回上页结束算法2 步骤如下：1)从图G中任选一棵树T1.2)加上一条弦e1，T1+e1中 立即生成一个圈.去掉此 圈中最大权边，得到新树T2,以T2代T1,重复2)再检查剩余的弦，直到全部弦检查完毕为止.例11用破圈法求下图的最小树.先求出上图的一棵生成树.加以弦 e2,得到的圈v1v3v2v1,去掉最大的权边e2,得到一棵新树仍是原来的树；B破圈法破圈法 再加上弦e7，得到圈 v4v5v2v4,去掉最大的权边e6，得到一棵新树；如此重复进行，直到全全部的弦均已试过,得最小树.第67页/共90页目录下页返回上页结

33、束五、旅行售货员问题五、旅行售货员问题 定义定义设G=(V,E)是连通无向图，包含图G的每个顶点的路称为G的哈密尔顿路(Hamilton路或H路).包含图G的每个顶点的圈，称为G的哈密尔顿圈(或Hamilton圈或H圈).含Hamilton圈的图称为哈密尔顿图(或Hamilton图或H图).第68页/共90页目录下页返回上页结束 一个旅行售货员想去访问若干城镇，然后回到出发地.给定各城镇之间的距离后，应怎样计划他的旅行路线，使他能对每个城镇恰好经过一次而总距离最小？它可归结为这样的图论问题：在一个赋权完全图中,找出一个最小权的H圈,称这种圈为最优圈.但这个问题是NP-hard问题，即不存在多项

34、式时间算法.也就是说,对于大型网络(赋权图),目前还没有一个求解旅行售货员问题的有效算法，因此只能找一种求出相当好（不一定最优）的解.旅行售货员问题或货郎担问题.第69页/共90页目录下页返回上页结束 是先求一个H圈,然后适当修改,以得到具有较小权的另一个H圈.一个可行的办法一个可行的办法 :设找到一个初始H圈 ，则对所有适合 的 和 ，总可得到一个新的H 圈：，它是由C 删去边 和 ，以及添加边 和而得到，如右图所示。第70页/共90页目录下页返回上页结束定义 若对于某一对i和j，有则圈Cij将是圈C的一个改进.二边逐次修正法:在接连进行一系列修改之后,最后得一个圈,不能再用此方法改进了，这

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

36、,则w(T)+w(e1)+w(e2)将是w(C)的一个下界.取v=v3,得G-v3的一最小生成树(实线),其权w(T)=122,与v3关联的权最小的两条边为w(T)+w(v1v3)+w(v2v3)=178.故最优H圈的权v1v3和v2v3,故w(C)应满足178 w(C)192.第73页/共90页目录下页返回上页结束六、最佳灾情巡视路线的模型的建立与求解六、最佳灾情巡视路线的模型的建立与求解问题转化为在给定的加权网络图中寻找从给定点O出发,行遍所有顶点至少一次再回回到点O,使得总权(路程或时时间)最小,即最佳旅行售货员问题.第74页/共90页目录下页返回上页结束最佳旅行售货员问题是NP完全问题

37、,采用一种近似算法求其一个近似最优解，来代替最优解.算法一算法一 求加权图的最佳旅行售货员回路近似算法:1)用图论软件包求出用图论软件包求出G中任意两个顶点间的最短路中任意两个顶点间的最短路,构造出完全图2)输入图输入图 的一个初始的一个初始H圈；圈；3)用对角线完全算法（见用对角线完全算法（见3）产生一个初始圈）产生一个初始圈;4)随机搜索出随机搜索出 中若干个中若干个H圈，例如圈，例如2000个；个；5)对第对第2)，3)，4)步所得的每个步所得的每个H圈，用二边逐次圈，用二边逐次修正法进行优化，得到近似最优H圈；6)在第在第5)步求出的所有步求出的所有H圈中，找出权最小的一个圈中，找出权

38、最小的一个,此即要找的最优H圈的近似解.因二边逐次修正法的结果与初始圈有关,故本算法第2)，3)，4)步分别用三种方法产生初始圈，以保证能得到较优的计算结果.第75页/共90页 问题一问题一 若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线.此问题是多个售货员的最佳旅行售货员问题.4)目录下页返回上页结束第76页/共90页目录下页返回上页结束 此问题包含两方面：a)对顶点分组,b)在每组中求(单个售货员)最佳旅行售货员回路.因单个售货员的最佳旅行售货员回路问题不存存在多项式时间内的精确算法.故多也不第77页/共90页目录下页返回上页结束 而图中节点数较多，为53个，我们只能去寻求一种较

39、合理的划分准则，对图1进行粗步划分后,求出各部分的近似最佳旅行售货员回路的权,再进一进一步进行调整，使得各部分满足均衡性条件3).从O点出发去其它点，要使路程较小应尽量走O点到该点的最短路.故用软件包求出O点到其余顶点的最短路.这些最短路构成一棵O为树根的树.将从O点出发的树枝称为干枝.第78页/共90页从O点出发到其它点共有6条干枝，它们的名称分别为，.在分组时应遵从准则：准则1 尽量使同一干枝上及分枝上的点分在同一组.准则2 应将相邻的干枝上的点分在同一组；准则3 尽量将长的干枝与短的干枝分在同一组.分组1极不均衡,故考虑分组2.由上述分组准则，我们找到两种分组形式如下：分组1:（，），（

40、，），（，）分组2:（，），（，），（，）第79页/共90页目录下页返回上页结束分组2:(,),(,),(,)对分组2中每组顶点的生成子图,用算法一求出近似最优解及相应的巡视路线.在每个子图所构造的完全图中,取一个尽量包含上图中树上的边的H圈作为其第2)步输入的初始圈.第80页/共90页分组2的近似解 第81页/共90页目录下页返回上页结束因为该分组的均衡度.所以此分法的均衡性很差.为改善均衡性，将第组中的顶点C,2,3,D,4分给第组（顶点2为这两组的公共点），重新分分组后的近似最优解见表2.第82页/共90页第83页/共90页目录下页返回上页结束因该分组的均衡度 所以这种分法的均衡性较好.

41、问题二问题二 当巡视人员在各乡（镇）、村的停留停留时间一定,汽车的行驶速度一定,要在24小时内完成巡视,至少要分几组及最佳旅行的巡视路线.第84页/共90页目录下页返回上页结束 由于T=2小时,t=1小时,V=35公里/小时,需访问的乡镇共有17个，村共有35个.计算出在乡(镇)及村的总停留时间为17 2+35=69小时，要在24小时内完成巡回，若不考虑行走时间，有:69/i24(i为分的组数).得i最小为4，故至少要分4组.由于该网络的乡(镇)、村分布较为均匀,故有可能找出停留时间尽量均衡的分组,当分4组时各组停停留时间大约为69/4=17.25小时，则每组分配在路路途上的时间大约为24-1

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