最短路与最优问题.ppt

《最短路与最优问题.ppt》由会员分享，可在线阅读，更多相关《最短路与最优问题.ppt（67页珍藏版）》请在三一办公上搜索。

1、数学建模暑期培训,主讲：陈六新,最短路径与最优匹配问题,图论问题的起源,18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块，它们通过七座桥相互连接，如下图。当时该城的市民热衷于这样一个游戏:“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？”,七桥问题的分析,七桥问题看起来不难，很多人都想试一试，但没有人找到答案。后来有人写信告诉了当时的著名数学家欧拉。千百人的失败使欧拉猜想，也许那样的走法根本不可能。1876年，他证明了自己的猜想。Euler把南北两岸和四个岛抽象成四个点，将连接这些陆地的桥用连接相应两点的一条线来表示，就得到如下一个简图:,欧拉的结论,欧拉指出:一个线图中存在通

2、过每边一次仅一次回到出发点的路线的充要条件是 1)图是连通的，即任意两点可由图中的一些边连接起来;2)与图中每一顶点相连的边必须是偶数。由此得出结论:七桥问题无解。欧拉由七桥问题所引发的研究论文是图论的开篇之作，因此称欧拉为图论之父。,图的作用,图是一种表示工具。改变问题的描述方式，往往是创造性的启发式解决问题的手段。一种描述方式就好比我们站在一个位置和角度观察目标，有的东西被遮挡住了，但如果换一个位置和角度，原来隐藏着的东西就可能被发现。采用一种新的描述方式，可能会产生新思想。图论中的图提供了一种直观，清晰表达已知信息的方式。它有时就像小学数学应用题中的线段图一样，能使我们用语言描述时未显示

3、的或不易观察到的特征、关系，直观地呈现在我们面前，帮助我们分析和思考问题，激发我们的灵感。,图的广泛应用,图的应用是非常广泛的，在工农业生产、交通运输、通讯和电力领域经常都能看到许多网络，如河道网、灌溉网、管道网、公路网、铁路网、电话线网、计算机通讯网、输电线网等等。还有许多看不见的网络，如各种关系网，像状态转移关系、事物的相互冲突关系、工序的时间先后次序关系等等，这些网络都可以归结为图论的研究对象图。其中存在大量的网络优化问题需要我们解决。还有象生产计划、投资计划、设备更新等问题也可以转化为网络优化的问题。,基本的网络优化问题,基本的网络优化问题有：最短路径问题、最小生成树问题、最大流问题和

4、最小费用问题。图论作为数学的一个分支，已经有有效的算法来解决这些问题。当然这当中的有些问题也可以建立线性规划的模型，但有时若变量特别多，约束也特别多，用线性规划的方法求解效率不高甚至不能在可忍受的时间内解决。而根据这些问题的特点，采用网络分析的方法去求解可能会非常有效。,例如，在1978年，美国财政部的税务分析部门在对卡特尔税制改革做评估的过程中，就有一个100000个约束以上，25000000个变量的问题，若用普通的线性规划求解，预计要花7个月的时间。他们利用网络分析的方法，将其分解成6个子问题，利用特殊的网络计算机程序，花了大约7个小时问题就得到了解决。,目的,内容,2.会用MATLAB软

5、件求最短路与最优匹配,1.了解最短路与最优匹配的算法及其应用,1.图 论 的 基 本 概 念,2.最 短 路 问 题 及 其 算 法,3.最 短 路 的 应 用,5.建模案例：最优截断切割问题,6.实验作业,4.最优匹配及算法,图 论 的 基 本 概 念,一、图 的 概 念,1.图的定义,2.顶点的次数,3.子图,二、图 的 矩 阵 表 示,1.关联矩阵,2.邻接矩阵,返回,图的定义,定义,定义,返回,完全图,二分图,完全二分图,顶点的次数,例 在一次聚会中，认识奇数个人的人数一定是偶数。,返回,子图,返回,关联矩阵,注：假设图为无向简单图,返回,邻接矩阵,注：假设图为简单无向图,返回,最 短

6、 路 问 题 及 其 算 法,一、基 本 概 念,二、固 定 起 点 的 最 短 路,三、每 对 顶 点 之 间 的 最 短 路,返回,基 本 概 念,返回,固 定 起 点 的 最 短 路,最短路是一条路径，且最短路的任一段也是最短路。,假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树。,因此，可采用树生长的过程来求指定顶点到其余顶点的最短路。,算法步骤：,TO MATLAB(road1),1,2,3,4,5,6,7,8,返回,每 对 顶 点 之 间 的 最 短 路,1.求距离矩阵的方法,2.求路径矩阵的方法,3.查找最短路路径的方法,（一）算法的基本思想

7、,（三）算法步骤,返回,算法的基本思想,返回,算法原理 求距离矩阵的方法,返回,算法原理 求路径矩阵的方法,在建立距离矩阵的同时可建立路径矩阵R。,即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得，可由 来查找任何点对之间最短路的路径。,返回,算法原理 查找最短路路径的方法,pk,p2,p1,p3,q1,q2,qm,则由点i到j的最短路的路径为：,返回,算法步骤,TOMATLAB(road2(floyd),返回,一、可化为最短路问题的多阶段决策问题,二、选 址 问 题,1.中心问题,2.重心问题,返回,可化为最短路问题的多阶段决策问题,返回,选址问题-中心问题,TO MA

8、TLAB(road3(floyd),S(v1)=10，S(v2)=7，S(v3)=6，S(v4)=10，S(v5)=7，S(v6)=7，S(v7)=8.5,S(v3)=6，故应将消防站设在v3处。,返回,选址问题-重心问题,返回,匹配,匹配问题是运筹学的重要问题之一，也是图论研究的重点内容，它提供了解决“人员分配问题”和“最优分配问题”一种新的思想。定义1 设G=是无环图，ME(G)，M，若M中任意两条边都不相邻，则称M是图G的一个匹配。若对图G的任何匹配M，均有M M，则称M是图G的最大匹配，记作(G)。定义2 设M是图G的匹配，G中与M中的边关联的顶点称为M饱和点。若图G的顶点都是M饱和，

9、则称为G的完美匹配。,说明:(1)完美匹配是最大匹配，反之未然;(2)匹配的定义与边的方向无关，故匹配是针对无向图而言。(3)图G的边不交匹配的最小数目即为G的边色数。定义3(可增广路):设M是图G的匹配，P是G的一条路，且在P中，M的边和E(G)-M的边交替出现，则称P是G的一条交错路。若M交错路P的两个端点为M非饱和点，则称P为M可增广路。例1 求下图G的一条交错路和一条可增广路。,匹配的几个性质定理,定理1 设M1和M2是图G的两个不同匹配，由M1M2导出的G的边导出子图记作H，则H的任意连通分支是下列情况之一:(1)边在M1和M2中交错出现的偶圈。(2)边在M1和M2中交错出现的路。证

10、明:记H=M1M2，因为H是边导出子图，所以(H)1。由于M1和M2是图G的两个不同匹配，所以H的任意顶点x至多与一条M1的边关联，同时也至多与一条M2的边关联，所以Deg(x)2，所以 2，故H的每个连通分支或者是一条路或者是一个圈。据匹配的定义，H的任意两条邻接边一定分别属于不同的匹配M1和M2，从而每条路或者圈的边交错地属于M1和M2且每个圈是偶圈。,定理2 M是图G的最大匹配，当且仅当G中不存在M可增广路。证明:()假设存在M可增广路P，则M=MP是G的一个新的匹配，且|M|M|1|M|，矛盾。()若M不是G的最大匹配，则存在匹配M，使得|M|M|，作H=MM，由定理1，H的任意边导出

11、子图Q是下列两种情况之一:(1)交错偶圈:Q中每个结点度数为2。(2)交错路。Q中除端点外，其余结点度数均为2。因为|M|M|，故|E(H)M|E(H)M|，因而H中必有一条起始于M且终止于M的连通分支P，故P是M可增广路，矛盾，所以命题正确。定义:NG(S):设S是图G的任意顶点子集，G中与S的顶点邻接的所有顶点的集合，称为S的邻集，记做NG(S)。,定理3(Hall定理，1935)设G是有二部划分(V1，V2)的二分图，则G含有饱和V1的每个顶点的匹配M的充要条件是，对SV1，有N(S)S。证明:()对SV1，匹配M将S中的每个顶点与N(S)中的顶点配对，所以N(S)S。()当对SV1，有

12、N(S)S时。可按下述方法作出饱和V1的匹配M。先作一初始匹配M1，若已经饱和V1，定理得证。否则，V1中至少有一非饱和点x1，检查以x1为起点，终点在V2中的交错路。考虑下面两种情形:,(1)不存在任何一条交错路可以到达V2的非饱和点。此时从X1开始的一切交错路的终点还是在V1中。故存在AV1，使得N(A)M1，因此，重复该过程就可以找到饱和V1的全部顶点的匹配M。,推论1 具有二部划分(V1，V2)的二分图G有完美匹配 V1=V2，且对SV1(或V2)，有N(S)S。证明:必要性。若二分图G有完美匹配，由定理3有V2=N(V1)V1，即V2V1，同理V1V2，因此V1=V2。充分性:因为对

13、SV1，有N(S)S，由定理1，G中存在饱和V1的每个顶点匹配M，又G是二分图，故匹配M的每一边的两个端点分别属于V1和V2，据V1=V2即知M饱和V2，所以M为完美匹配。,推论2 设G是k(0)正则二分图，则G有完美匹配。证明:因为G是二部划分(V1，V2)的k正则二分图，故 kV1=E(G)=kV2 又k0，所以V1=V2。任取SV1，并用E1和E2分别表示G中与S和N(S)中关联的边集，则E1E2，则 kN(S)=E2E1=kS即N(S)S，SV1，由定理3可知，G有饱和V1的匹配M，再据V1=V2和推论1即知M是完美匹配。,推论3 设G是二部划分(V1，V2)的简单二分图，且V1=V2

14、=n，若(G)n/2，则G有完美匹配。证明:SV1，(1)若S中至少有两个顶点，由(G)n/2可知N(S)n/2+n/2=n=V1S(2)若S中只有一个顶点，由(G)n/2可知N(S)n/2，所以 N(S)1S=1。综上，对SV1，均有N(S)S，所以G中有完美匹配。,定理4 G有完美匹配O(G-S)S，SV(G)，其中O(G-S)是G-S的奇数阶连通分支数目。(不证)例1 有n张纸牌，每张纸牌的正反两面都写上1，2，n的某一个数。证明:如果每个数字恰好出现两次，则这些纸牌一定可以这样摊开，使朝上的面中1，2，n都出现。证明:作一个二分图G=，其中V1=1，2，n，V2=y1，y2，yn表示这

15、n张纸牌。i与yi之间连接的边数等于数i在纸牌yj中出现的次数，这样得到的图G是一个2-正则二分图，因此图G中有完美匹配，设为M=1yi1，2yi2，nyin 则只要把纸牌yi1中的1朝上，yi2中的2朝上，yin的n朝上，这样摊开，这样摊开的纸牌就能使上面中1，2，n都出现。,例2 某工厂生产由6种不同颜色的纱布织成的双色布，由该厂所生产的双色布中，每一种颜色至少和其他三种颜色搭配.证明可以挑选出三种不同的双色布，它们含有所有的6种颜色。证明:构造图G=，其中V=v1，v2，v3，v4，v5，v6表示6种颜色，工厂生产出一种颜色vi与vj搭配而成的双色布边vi，vjE(G)。由题意知，G为简

16、单图，且每个结点的度数至少为3，下证G中含有一个完美匹配。今设v1，v2E(G)，由于d(v3)3，所以存在一个不同于v1和v2的顶点vi(4i6)，使v3，viE(G)，不妨设vi=4，即v3，v4E(G)。,如果边v5，v6E(G)，由于d(v5)3，v1，v2，v3，v4中至少有3个顶点与v5相邻，即v5与边v1，v2，v3，v4中的每一边的某一个端点相邻，不妨设v1，v5E(G)和v3，v5E(G)。对于顶点v6，同样与v1，v2，v3，v4中至少3个顶点相邻，即在v2和v4中至少有一个顶点与v6相邻。如果v2，v6 E(G)，则边v1，v5，v3，v4，v2，v6是G的一个完美匹配;

17、如果v4，v6E(G)，则v1，v5，v3，v5，v4，v6是G的一个完美匹配。综上所述，G总存在完美匹配，完美匹配中的三条边所对应的三种双色布即为所求。,最大匹配的生成算法-匈牙利算法,定义1 根在x的M交错子图:设M是图G的匹配，x是G中非M饱和点。G中由起点为x的M交错路所能连接的顶点集所导出的G的导出子图称为根在x的M交错子图。定理1 设M是具有二部划分(V1，V2)的二分图G的匹配，xV1是非M饱和点，H是G中根在x的M交错子图的顶点集S=HV1，T=HV2，则:(1)TNG(S);(2)下述三条等价:(a)G中不存在以x为端点的M可增广路;(b)x是H中唯一的非M饱和点;(c)T=

18、NG(S)，且T=S-1。,证明:(1)yT，则G中存在以x和y为端点的M交错路P。令uNp(y)，由于G是二分图且yTV2，所以uHV1=S，即yNG(S)，因而T NG(S)，。(2)(a)(b)设y是H中异于x的非M饱和点，则G中存在以x和y为端点的M交错路P。P是G中以x为端点的M可增广路，与(a)矛盾。(b)(c)任取yNG(S)V2，则存在uS=H V1和边eE(G)使G(e)=u，y。若u=x，显然有yT。若ux，则G中存在以x和u为端点的交错路P。因为x是唯一非M饱和点，所以u为M饱和点。若P不含y，则eM。由H的定义知，y HV2=T，所以NG(S)T，再由(1)，T=NG(

19、S)。,显然yT(交错路中不可能含有两个非M饱和点)，与T=NG(S)矛盾。若yS，则显然有T=S-2。矛盾。所以G中不存在以x为端点的M可增广路。,(3)(c)(a)反设G中存在以x为端点的M可增广路，则G中至少还存在一个异于x的非M饱和点y，若yS，则yT NG(S)，,匈牙利算法,基本思想:设G是具有二部划分(V1，V2)的二分图，从图G的任意匹配M开始。若M饱和V1，则M是G的匹配。若M不能饱和V1，则在V1中选择一个非M饱和点x，若G中存在以x为起点的M可增广路P，则M=MP就是比M更大的匹配，利用M代替M，并重复这个过程。若G中不存在以x为起点的M可增广路，则令H是根在x的M交错子

20、图的顶点集，并令S=HV1，T=HV2，由定理1，T=NG(S)，且G中不存在以x为起点的M可增广路，此时称x为检验过的非M饱和点。对V1中其它未检验过的非M饱和点重复该过程，直到V1中的所有非M饱和点全部检验过为止。当整个过程结束时，由于G中不存在M可增广路，从而M为G的最大匹配。,匈牙利算法步骤:设G是具有二部划分(V1，V2)的二分图。(1)任给初始匹配M;(2)若M饱和V1则结束。否则转(3);(3)在V1中找一非M饱和点x，置S=x，T=;(4)若N(S)=T，则停止，否则任选一点yN(S)-T;(5)若y为M饱和点转(6)，否则作求一条从x到y的M可增广路P，置M=MP，转(2)(

21、6)由于y是M饱和点，故M中有一边y，u，置S=Su，T=Ty，转(4)。,例1 如图G所示，V1=x1，x2，x3，x4，x5，V2=y1，y2，y3，y4，y5，试求图G的最大匹配。,解：任取初始匹配M=x2y2，x3y3，x5y5，如图(a)中虚线所示。解题过程如下表:,因此，M=x1y2，x2y1，x3y3，x5y5即为图G的最大匹配，如图(b)虚线所示。匈牙利算法的时间复杂度分析:设二分图G有n个结点，m条边，利用匈牙利算法求G的最大匹配时，初始匹配可为空，因此算法最多可找n条可增广路，每找一条可增广路，最多比较m条边，从而算法的时间复杂度为O(mn)，故匈牙利算法为有效算法。,最优

22、匹配,定义1 最优匹配:在加权图中求一个总权最大的完美匹配，这种匹配称为最优匹配。定义2 已知G是具有二部划分(V1，V2)的完全加权二分图，映射l:V(G)R，满足对G的每条边e=x，y，均有l(x)+l(y)(x，y)，其中(x，y)表示边x，y的权，则称l为G的可行顶标。令El=x，yx，yE(G)，l(x)+l(y)=(x，y)，Gl为以El为边集的G的生成子图，则称Gl为l等子图。说明:可行顶标总是存在的，例如:,定理1 设l是G的可行顶标。若l等子图Gl有完美匹配M，则M是G的最优匹配。基于定理1的在一个加权二分图(Km，n，)中求最优匹配的有效算法Kuhn-munkres算法:(1)从任意可行顶标(如平凡标号)l开始，确定l等子图Gl，并且在Gl中选取匹配M。若M饱和V1，则M是完美匹配，也即M是最优匹配，算法终止，否则转入(2)步。(2)匈牙利算法终止于SV1，T V2且使NGl(S)=T，计算，确定新的可行顶标l，并以l替代l，以Gl替代Gl转入(1)步。,例1 已知完全二分图k5，5，其中V1=x1，x2，x3，x4，x5，V2=y1，y2，y3，y4，y5，且k5，5的权矩阵为A，求k5，5的最优匹配。,