数学建模基础知识幻灯片.ppt

数学建模基础知识第1页，共71页，编辑于2022年，星期六我们介绍三种优化模型：n n图论图论n n动态优化动态优化n n排队论排队论重点：图论模型的数学建模案例分析重点：图论模型的数学建模案例分析 第2页，共71页，编辑于2022年，星期六基本方法机理分析机理分析测试分析测试分析根据对客观事物特性的认识，找出反映内部机理的数量规律将研究对象看作“黑箱”,通过对量测数据的统计分析，找出与数据拟合最好的模型二者结合二者结合机理分析建立模型结构,测试分析确定模型参数 数学建模的方法和步骤数学建模的方法和步骤第3页，共71页，编辑于2022年，星期六数数 学学 建建 模模 的的 一一 般般 步步 骤骤模型准备模型准备模型假设模型假设模型构成模型构成模型求解模型求解模型分析模型分析模型检验模型检验模型应用模型应用第4页，共71页，编辑于2022年，星期六一、图论方法一、图论方法最短路问题最短路问题最短路问题最短路问题两个指定顶点之间的最短路径两个指定顶点之间的最短路径两个指定顶点之间的最短路径两个指定顶点之间的最短路径给出了一个连接若干个城镇的铁给出了一个连接若干个城镇的铁给出了一个连接若干个城镇的铁给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线路网络，在这个网络的两个指定城镇间，找一条最短铁路线路网络，在这个网络的两个指定城镇间，找一条最短铁路线路网络，在这个网络的两个指定城镇间，找一条最短铁路线 （DijkstraDijkstra算法算法算法算法 ）每对顶点之间的最短路径每对顶点之间的最短路径每对顶点之间的最短路径每对顶点之间的最短路径 （DijkstraDijkstra算法、算法、算法、算法、FloydFloyd算法算法算法算法 ）最小生成树问题最小生成树问题连线问题连线问题连线问题连线问题欲修筑连接多个城市的铁路设计一个线路图，使欲修筑连接多个城市的铁路设计一个线路图，使欲修筑连接多个城市的铁路设计一个线路图，使欲修筑连接多个城市的铁路设计一个线路图，使总造价最低（总造价最低（总造价最低（总造价最低（primprim算法算法算法算法、KruskalKruskal算法算法算法算法 ）图的匹配问题图的匹配问题图的匹配问题图的匹配问题人员分派问题：人员分派问题：人员分派问题：人员分派问题：n n个工作人员去做个工作人员去做个工作人员去做个工作人员去做n n份工作，每人适合做其中一份份工作，每人适合做其中一份份工作，每人适合做其中一份份工作，每人适合做其中一份或几份，问能否每人都有一份适合的工作？如果不能，最多几人或几份，问能否每人都有一份适合的工作？如果不能，最多几人或几份，问能否每人都有一份适合的工作？如果不能，最多几人或几份，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？可以有适合的工作？可以有适合的工作？可以有适合的工作？(匈牙利算法匈牙利算法匈牙利算法匈牙利算法)第5页，共71页，编辑于2022年，星期六遍历性问题遍历性问题遍历性问题遍历性问题中国邮递员问题中国邮递员问题邮递员发送邮件时，要从邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线一条行程最短的路线最小费用最大流问题最小费用最大流问题在运输问题中，人们总是希望在完成运输任在运输问题中，人们总是希望在完成运输任务的同时，寻求一个使总的运输费用最小的务的同时，寻求一个使总的运输费用最小的运输方案运输方案 第6页，共71页，编辑于2022年，星期六（1）基基本本概概念念（2）固）固定定起起点点的的最最短短路路（3）每）每对对顶顶点点之之间间的的最最短短路路1 1、最短路问题、最短路问题第7页，共71页，编辑于2022年，星期六基基 本本 概概 念念第8页，共71页，编辑于2022年，星期六固固 定定 起起 点点 的的 最最 短短 路路从甲地到乙地之间是否有公路连通?在有多条通路的情况下，哪一条路最短?交通网络可用带权图来表示。顶点表示城市名称，边表示两个城市有路连通，边上的权值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径，不是指路径上边数之和最少，而是指路径上各边的权值之和最小。另外，若两个顶点之间没有边，则认为两个顶点无通路，但有可能有间接通路(从其它顶点达到)。路径上的开始顶点(出发点)称为源点，路径上的最后一个顶点称为终点，并假定讨论的权值不能为负数。第9页，共71页，编辑于2022年，星期六从一个顶点到其余各顶点的最短路径从一个顶点到其余各顶点的最短路径 问问 题题：给给定定一一个个带带权权有有向向图图G与与源源点点v,求求从从v到到G中中其其他顶点的最短他顶点的最短 路径路径,并限定各边上的权值大于或等于并限定各边上的权值大于或等于0。第10页，共71页，编辑于2022年，星期六 采用采用狄克斯特拉狄克斯特拉(Dijkstra)算法求解算法求解 基基本本思思想想是是：设设G=(V,E)是是一一个个带带权权有有向向图图,把把图图中中顶点集合顶点集合V分成两组：分成两组：第第一一组组为为已已求求出出最最短短路路径径的的顶顶点点集集合合(用用S表表示示,初初始始时时S中中只只有有一一个个源源点点,以以后后每每求求得得一一条条最最短短 路路径径v,vk,就就将将vk加加入入到到集集合合S中中,直直到到全全部部顶顶点点都都加加入入到到S中中,算算法法就就结束了结束了)第二组为其余未确定最短第二组为其余未确定最短 路径的顶点集合路径的顶点集合(用用U表示表示)。按按最最短短 路路径径长长度度的的递递增增次次序序依依次次把把第第二二组组的的顶顶点点加加入入S中中。在在加加入入的的过过程程中中,总总保保持持从从源源点点v到到S中中各各顶顶点点的的最最短短路路径径长长度度不不大大于于从从源源点点v到到U中中任任何何顶顶点点的的最最短短路路径径长长度度。此此外外,每每个个顶顶点点对对应应一一个个距距离离,S中中的的顶顶点点的的距距离离就就是是从从v到到此此顶顶点点的的最最短短 路路径径长长度度,U中中的的顶顶点点的的距距离离从从v到到此此顶顶点点只只包括包括S中的顶点为中间顶点的当前最短中的顶点为中间顶点的当前最短 路径长度。路径长度。第11页，共71页，编辑于2022年，星期六狄克斯特拉算法的具体步骤如下：狄克斯特拉算法的具体步骤如下：(1)初初始始时时,S只只包包含含源源点点,即即S=v,v的的距距离离为为0。U包包含含除除v外外的的其其他他顶顶点点,U中中顶顶点点u距距离离为为边边上上的的权权(若若v与与u有有边边)或或(若若u不是不是v的出边邻接点的出边邻接点)。(2)从从U中中选选取取一一个个距距离离v最最小小的的顶顶点点k,把把k加加入入S中中(该该选选定的距离就是定的距离就是v到到k的最短路径长度的最短路径长度)。(3)以以k为为新新考考虑虑的的中中间间点点,修修改改U中中各各顶顶点点的的距距离离：若若从从源源点点v到到顶顶点点u(uU)的的距距离离(经经过过顶顶点点k)比比原原来来距距离离(不不经经过过顶顶点点k)短短,则则修修改改顶顶点点u的的距距离离值值,修修改改后后的的距距离离值值的的顶顶点点k的的距距离加上边离加上边上的权。上的权。(4)重复步骤重复步骤(2)和和(3)直到所有顶点都包含在直到所有顶点都包含在S中。中。第12页，共71页，编辑于2022年，星期六S U v0到到06各顶点的距离各顶点的距离0 1,2,3,4,5,6 0,4,6,6,0,1 2,3,4,5,6 0,4,5,6,11,0,1,2 3,4,5,6 0,4,5,6,11,9,0,1,2,3 4,5,6 0,4,5,6,11,9,190,1,2,3,5 4,6 0,4,5,6,10,9,170,1,2,3,5,4 6 0,4,5,6,10,9,160,1,2,3,5,4,6 0,4,5,6,10,9,16 则则v0到到v1v6各各顶顶点点的的最最短短距距离离分分别别为为4、5、6、10、9和和16。第13页，共71页，编辑于2022年，星期六狄克斯特拉算法如下狄克斯特拉算法如下(n为图为图G的顶点数的顶点数,v0为源点编号为源点编号)：void Dijkstra(int costMAXV,int n,int v0)int distMAXV,pathMAXV;int sMAXV;int mindis,i,j,u;for(i=0;in;i+)disti=costv0i;/*距离初始化距离初始化*/si=0;/*s置空置空*/if(costv0iINF)/*路径初始化路径初始化*/pathi=v0;else pathi=-1;sv0=1;pathv0=0;/*源点编号源点编号v0放入放入s中中*/第14页，共71页，编辑于2022年，星期六 for(i=0;in;i+)/*循环直到所有顶点的最短路径都求出循环直到所有顶点的最短路径都求出*/mindis=INF;u=-1;for(j=0;jn;j+)/*选取不在选取不在s中且具有最小距离的顶点中且具有最小距离的顶点u*/if(sj=0&distjmindis)u=j;mindis=distj;su=1;/*顶点顶点u加入加入s中中*/for(j=0;jn;j+)/*修改不在修改不在s中的顶点的距离中的顶点的距离*/if(sj=0)if(costujINF&distu+costujdistj)distj=distu+costuj;pathj=u;Dispath(dist,path,s,n,v0);/*输出最短路径输出最短路径*/第15页，共71页，编辑于2022年，星期六void Ppath(int path,int i,int v0)/*前向递归查找路径上的顶点前向递归查找路径上的顶点*/int k;k=pathi;if(k=v0)return;/*找到了起点则返回找到了起点则返回*/Ppath(path,k,v0);/*找找k顶点的前一个顶点顶点的前一个顶点*/printf(%d,k);/*输出输出k顶点顶点*/第16页，共71页，编辑于2022年，星期六void Dispath(int dist,int path,int s,int n,int v0)int i;for(i=0;in;i+)if(si=1)printf(“从从%d到到%d的最短路径长度为的最短路径长度为:%dt路径为路径为:,v0,i,disti);printf(%d,v0);/*输出路径上的起点输出路径上的起点*/Ppath(path,i,v0);/*输出路径上的中间点输出路径上的中间点*/printf(%dn,i);/*输出路径上的终点输出路径上的终点*/else printf(从从%d到到%d不存在路径不存在路径n,v0,i);第17页，共71页，编辑于2022年，星期六每对顶点之间的最短路径每对顶点之间的最短路径 问问题题：对对于于一一个个各各边边权权值值均均大大于于零零的的有有向向图图,对对每每一一对顶点对顶点vivj,求出求出vi与与vj之间的最短路径和最短路径长度。之间的最短路径和最短路径长度。可可以以通通过过以以每每个个顶顶点点作作为为源源点点循循环环求求出出每每对对顶顶点点之之间间的的最最短短路路径径。除除此此之之外外,弗弗洛洛伊伊德德(Floyd)算算法法也也可可用用于于求求两顶点之间最短路径。两顶点之间最短路径。第18页，共71页，编辑于2022年，星期六 假假设设有有向向图图G=(V,E)采采用用邻邻接接矩矩阵阵cost存存储储,另另外外设设置置一一个个二二维维数数组组A用用于于存存放放当当前前顶顶点点之之间间的的最最短短路路径径长长度度,分分量量Aij表表示示当当前前顶顶点点vi到到顶顶点点vj的的最最短短路路径径长长度度。弗弗洛洛伊伊德德算算法法的的基基本本思思想想是是递递推推产产生生一一个个矩矩阵阵序序列列A0,A1,Ak,An,其其中中Akij表表示示从从顶顶点点vi到到顶顶点点vj的的路径上所经过的顶点编号不大于路径上所经过的顶点编号不大于k的最短路径长度。的最短路径长度。第19页，共71页，编辑于2022年，星期六 初初始始时时,有有A-1ij=costij。当当求求从从顶顶点点vi到到顶顶点点vj的的路路径径上上所所经经过过的的顶顶点点编编号号不不大大于于k+1的的最最短短路路径径长长度时度时,要分两种情况考虑：要分两种情况考虑：一一种种情情况况是是该该路路径径不不经经过过顶顶点点编编号号为为k+1的的顶顶点点,此此时时该该路路径径长长度度与与从从顶顶点点vi到到顶顶点点vj的的路路径径上上所所经经过过的的顶顶点点编编号号不大于不大于k的最短路径长度相同；的最短路径长度相同；另另一一种种情情况况是是从从顶顶点点vi到到顶顶点点vj的的最最短短路路径径上上经经过过编编号号为为k+1的顶点。的顶点。那那么么,该该路路径径可可分分为为两两段段,一一段段是是从从顶顶点点vi到到顶顶点点vk+1的的最最短短路路径径,另另一一段段是是从从顶顶点点vk+1到到顶顶点点vj的的最最短短路路径径,此此时时最最短短路路径径长长度度等等于于这这两两段段路路径径长长度度之之和和。这这两两种种情情况况中中的的较较小小值值,就就是是所所要要求求的的从从顶顶点点vi到到顶顶点点vj的的路路径径上上所所经经过过的的顶顶点点编编号号不不大于大于k+1的最短路径。的最短路径。第20页，共71页，编辑于2022年，星期六 弗洛伊德思想可用如下的表达式来描述：弗洛伊德思想可用如下的表达式来描述：A-1ij=costij Ak+1ij=minAkij,Akik+1+Akk+1j(0kn-1)第21页，共71页，编辑于2022年，星期六 采用弗洛伊德算法求解过程采用弗洛伊德算法求解过程 第22页，共71页，编辑于2022年，星期六 考考虑虑顶顶点点v0,A0ij表表示示由由vi到到vj,经经由由顶顶点点v0的的最最短短路路径径。只只有有从从v2到到v1经经过过v0的的路路径径和和从从v2到到v3经经过过v0的的路路径径,不不影影响响v2到到v1和和v2到到v3的路径长度的路径长度,因此因此,有：有：第23页，共71页，编辑于2022年，星期六 考考虑虑顶顶点点v1,A1ij表表示示由由vi到到vj,经经由由顶顶点点v1的的最最短短路路径径。存存在在路路径径v0-v1-v2,路路径径长长度度为为9,将将A02改改为为9,path02改为改为1,因此因此,有有：第24页，共71页，编辑于2022年，星期六考考虑虑顶顶点点v2,A2ij表表示示由由vi到到vj,经经由由顶顶点点v2的的最最短短路路径径。存存在在路路径径v3-v2-v0,长长度度为为4,将将A30改改为为4；存存在在路路径径v3-v2-v1,长长度度为为4,将将A31改改为为4。存存在在路路径径v1-v2-v0,长长 度度 为为 7,将将 A10改改 为为 7。将将path30、path31和和path10均均改改为为2。因此。因此,有：有：第25页，共71页，编辑于2022年，星期六 考虑顶点考虑顶点v3,A3ij表示由表示由vi到到vj,经经由顶点由顶点v3的最短路径。存在路径的最短路径。存在路径v0-v3-v2,长度为长度为8比原长度短比原长度短,将将A02改为改为8；存在路径存在路径v1-v3-v2-v0,长度为长度为6(A13+A30=2+4=6)比原长度短比原长度短,将将A10改为改为6；存在路径；存在路径v1-v3-v2,长度为长度为3,比原长度短比原长度短,将将A12改为改为3；将；将path02、path10后后path12均改为均改为3。因此。因此,有：有：第26页，共71页，编辑于2022年，星期六 因此因此,最后求得的各顶点最短路径长度最后求得的各顶点最短路径长度A和和Path矩阵为：矩阵为：从从0到到0路径为：路径为：0,0路径长度为：路径长度为：0从从0到到1路径为：路径为：0,1路径长度为：路径长度为：5从从0到到2路径为：路径为：0,3,2路径长度为：路径长度为：8从从0到到3路径为：路径为：0,3路径长度为：路径长度为：7从从1到到0路径为：路径为：1,3,2,0 路径长度为：路径长度为：6从从1到到1路径为：路径为：1,1路径长度为：路径长度为：0从从1到到2路径为：路径为：1,3,2 路径长度为：路径长度为：3从从1到到3路径为：路径为：1,3路径长度为：路径长度为：2第27页，共71页，编辑于2022年，星期六从从2到到0路径为：路径为：2,0路径长度为：路径长度为：3从从2到到1路径为：路径为：2,1路径长度为：路径长度为：3从从2到到2路径为：路径为：2,2路径长度为：路径长度为：0从从2到到3路径为：路径为：2,3路径长度为：路径长度为：2从从3到到0路径为：路径为：3,2,0 路径长度为：路径长度为：4从从3到到1路径为：路径为：3,2,1 路径长度为：路径长度为：4从从3到到2路径为：路径为：3,2路径长度为：路径长度为：1从从3到到3路径为：路径为：3,3路径长度为：路径长度为：0第28页，共71页，编辑于2022年，星期六弗洛伊德算法如下：弗洛伊德算法如下：void Floyd(int costMAXV,int n)int AMAXVMAXV,pathMAXVMAXV;int i,j,k;for(i=0;in;i+)for(j=0;jn;j+)Aij=costij;pathij=-1;for(k=0;kn;k+)for(i=0;in;i+)for(j=0;j(Aik+Akj)Aij=Aik+Akj;pathij=k;Dispath(A,path,n);/*输出最短路径输出最短路径*/第29页，共71页，编辑于2022年，星期六最小生成树概念最小生成树概念1.1.设无向连通图设无向连通图设无向连通图设无向连通图G=G=（V V，EE），），），），其子图其子图其子图其子图G=G=（V V，TT）满足：满足：满足：满足：V(G V(G V(G V(G)=V(G)n)=V(G)n)=V(G)n)=V(G)n个顶点个顶点个顶点个顶点 G G G G 是连通的是连通的是连通的是连通的 G G G G 中无回路中无回路中无回路中无回路则则则则G G G G 是是是是G G G G的生成树的生成树的生成树的生成树2 2、最小生成树问题、最小生成树问题 第30页，共71页，编辑于2022年，星期六具有具有具有具有n n个顶点的无向连通图个顶点的无向连通图个顶点的无向连通图个顶点的无向连通图GG 其任一生成树恰好含其任一生成树恰好含其任一生成树恰好含其任一生成树恰好含n-1n-1n-1n-1条边条边条边条边 生成树不一定唯一，如生成树不一定唯一，如深度优先搜索生成树和广度优先搜索生成树。深度优先搜索生成树和广度优先搜索生成树。第31页，共71页，编辑于2022年，星期六生成树代价生成树代价对图中每条边赋于一个权值（代价），则构成一个网，对图中每条边赋于一个权值（代价），则构成一个网，对图中每条边赋于一个权值（代价），则构成一个网，对图中每条边赋于一个权值（代价），则构成一个网，网的生成树网的生成树G=(V，T)的的代价代价代价代价是是T中各边的权值之中各边的权值之和，和，最小生成树就是网上所有可能的生成树中，代价最小的一最小生成树就是网上所有可能的生成树中，代价最小的一最小生成树就是网上所有可能的生成树中，代价最小的一最小生成树就是网上所有可能的生成树中，代价最小的一类生成树。类生成树。类生成树。类生成树。最小生成树也不一定唯一。最小生成树也不一定唯一。最小生成树也不一定唯一。最小生成树也不一定唯一。第32页，共71页，编辑于2022年，星期六 最小生成树的实用例子最小生成树的实用例子最小生成树的实用例子最小生成树的实用例子例例例例1 1：N N台计算机之间建立通讯网台计算机之间建立通讯网台计算机之间建立通讯网台计算机之间建立通讯网顶点表示顶点表示顶点表示顶点表示computercomputer边表示通讯线边表示通讯线边表示通讯线边表示通讯线权值表示通讯线的代价（通讯权值表示通讯线的代价（通讯权值表示通讯线的代价（通讯权值表示通讯线的代价（通讯线长度，线长度，线长度，线长度，computercomputer间距离等）间距离等）间距离等）间距离等）要求：要求：要求：要求：n n n n台计算机中的任何两台能通过网进行通讯；台计算机中的任何两台能通过网进行通讯；台计算机中的任何两台能通过网进行通讯；台计算机中的任何两台能通过网进行通讯；使总的代价最小。使总的代价最小。使总的代价最小。使总的代价最小。-求最小生成树求最小生成树求最小生成树求最小生成树TTTT第33页，共71页，编辑于2022年，星期六例例2：邮递员送信线路邮递员送信线路邮递员送信线路邮递员送信线路TT顶点表示投递点顶点表示投递点顶点表示投递点顶点表示投递点边表示街道边表示街道边表示街道边表示街道权值表示街道的长度权值表示街道的长度权值表示街道的长度权值表示街道的长度要求：要求：完成完成完成完成n n n n个投递点的投递；个投递点的投递；个投递点的投递；个投递点的投递；使总路径长度最短使总路径长度最短使总路径长度最短使总路径长度最短,即求最小生成树即求最小生成树即求最小生成树即求最小生成树TTTT第34页，共71页，编辑于2022年，星期六设设设设 N=N=（V V，EE）是一个连通网，）是一个连通网，）是一个连通网，）是一个连通网，V=1V=1，2 2，nn是是是是N N的顶点集合，的顶点集合，的顶点集合，的顶点集合，辅助集合辅助集合辅助集合辅助集合U U，初值为，初值为Uo，用来存放当前所得到的最小生成树的顶点；用来存放当前所得到的最小生成树的顶点；用来存放当前所得到的最小生成树的顶点；用来存放当前所得到的最小生成树的顶点；辅助集合辅助集合辅助集合辅助集合TETETETE，初值为，初值为，初值为，初值为，用来存放当前所得到的最小生成树的边。用来存放当前所得到的最小生成树的边。1）普里姆（）普里姆（Prim）算法）算法第35页，共71页，编辑于2022年，星期六PrimPrim算法步骤算法步骤算法步骤算法步骤1.TE=1.TE=,U=u,U=u,U=u,U=u0 0 0 0 2.2.2.2.当当当当UVUVUVUV，重复下列步骤：，重复下列步骤：，重复下列步骤：，重复下列步骤：(1)(1)(1)(1)选取（选取（选取（选取（u u u u0 0 0 0,v,v,v,v0 0 0 0)=mincost(u,v)|uU,vV-U)=mincost(u,v)|uU,vV-U)=mincost(u,v)|uU,vV-U)=mincost(u,v)|uU,vV-U，保证不形成回路保证不形成回路保证不形成回路保证不形成回路(2)TE=TE+(2)TE=TE+(2)TE=TE+(2)TE=TE+（u u u u0 0 0 0,v,v,v,v0 0 0 0),),),),边（边（边（边（u u u u0 0 0 0,v,v,v,v0 0 0 0)并入并入并入并入TETETETE(3)U=U+V(3)U=U+V(3)U=U+V(3)U=U+V0 0 0 0 ，顶点顶点顶点顶点V V V V0 0 0 0 并入并入并入并入U U U U初始化：初始化：5 52 21 13 34 46 66 65 55 56 6 1 1第第1步：步：6 61 14 4第第2步：步：6 61 14 42 2第第3步：步：5 56 61 14 42 2第第4步：步：23 3 5 56 61 14 4第5步：特点特点特点特点:以连通为主以连通为主以连通为主以连通为主选代价最小的邻接边选代价最小的邻接边选代价最小的邻接边选代价最小的邻接边第36页，共71页，编辑于2022年，星期六Prim算法的实现算法的实现void graph:mintree(char u)for(int k=0;kvexnum;k+)if(vexsk=u)break;for(int j=0;jvexnum;j+)if(j!=k)closedgej.index=k;closedgej.lowcost=arcskj;/给结构体数组赋值给结构体数组赋值closedgek.lowcost=0;/初始化初始化for(int i=1;ivexnum;i+)/找到与顶点找到与顶点u相邻的权值最小的相邻的权值最小的int k=closedge0.lowcost;for(int x=0;xvexnum;x+)（邻接矩阵存储）（邻接矩阵存储）第37页，共71页，编辑于2022年，星期六if(closedgex.lowcostk)k=closedgex.lowcost;cout(vexsclosedgek.index,vexsk);closedgek.lowcost=0;/第第k顶点并入顶点并入U集合集合for(j=0;jvexnum;j+)if(arcskjclosedgej.lowcost)closedgej.index=vexsk;closedgej.lowcost=arcskj;/新的顶点并入新的顶点并入U后，从新调整辅助数组后，从新调整辅助数组第38页，共71页，编辑于2022年，星期六2 2、KruskalKruskal算法算法（1）定理2设图G有n个结点，以下算法产生一颗最小生成树：(1)取最小权边e1，令i=1；(2)若i=n-1，则结束。否则转3；(3)设已选中n的边为e1，e2，ei。在G中选不同于e1，e2，ei的边ei+1，使e1，e2，ei，ei+1构成的路中无回路，且ei+1是满足此条件的最小权边；(4)i=i+1，转(2)。上面的算法也叫避圈法。实际求解时有两种方式：上面的算法也叫避圈法。实际求解时有两种方式：（1）从边权最小的边所关联的两个结点出发，逐步添补边权最小）从边权最小的边所关联的两个结点出发，逐步添补边权最小的边，但始终保持连通性且无回路，直到边数达到的边，但始终保持连通性且无回路，直到边数达到n-1条为止。条为止。（2）不断删除边权最大的边而保持图的连通性且无回路。）不断删除边权最大的边而保持图的连通性且无回路。直到边数剩直到边数剩n-1条停时止。条停时止。第39页，共71页，编辑于2022年，星期六2 2、KruskalKruskal算法算法（2 2）KruskalKruskal算法举例：在下图中求最小生成树算法举例：在下图中求最小生成树(方法方法1)1)。第40页，共71页，编辑于2022年，星期六2 2、KruskalKruskal算法算法（3 3）KruskalKruskal算法举例：在下图中求最小生成树算法举例：在下图中求最小生成树(方法方法2)2)。第41页，共71页，编辑于2022年，星期六3 3、图的匹配问题、图的匹配问题实例一：实例一：握手的次数握手的次数 n n史密斯先生和他太太邀请四对夫妻参加晚会。每个人到的时候，史密斯先生和他太太邀请四对夫妻参加晚会。每个人到的时候，房间里的一些人都要与别的一些人握手。当然，每个人都不会房间里的一些人都要与别的一些人握手。当然，每个人都不会与自己的配偶握手，也不会跟同一个人握手两次。与自己的配偶握手，也不会跟同一个人握手两次。之后，史之后，史密斯先生问每个人和别人握了几次手，他们的答案都不一样。密斯先生问每个人和别人握了几次手，他们的答案都不一样。那么，史密斯太太和别人握了几次手呢那么，史密斯太太和别人握了几次手呢?n n这个问题具有挑战性的原因是因为它没有一个明显的起始点，这个问题具有挑战性的原因是因为它没有一个明显的起始点，但如果对此建立一个图模型，问题就变得很简单了。但如果对此建立一个图模型，问题就变得很简单了。第42页，共71页，编辑于2022年，星期六n n分析：从题目我们得到了哪些信息分析：从题目我们得到了哪些信息?n n史密斯和太太邀请四对夫妻参加晚会史密斯和太太邀请四对夫妻参加晚会-房间里共有房间里共有10 10 人。人。n n每个人都不会与自己的配偶握手每个人都不会与自己的配偶握手-握手的两个人不是配偶握手的两个人不是配偶 。n n每个人都不会跟同一人握手两次每个人都不会跟同一人握手两次-两个人间的握手最多是一次。两个人间的握手最多是一次。n n史密斯先生问每个人和别人握了几次手，他们的答案都不一样史密斯先生问每个人和别人握了几次手，他们的答案都不一样-除史除史密斯先生外，每个人和别人握手的次数都不一样。密斯先生外，每个人和别人握手的次数都不一样。n n除史密斯先生外，每人握手的次数最多是除史密斯先生外，每人握手的次数最多是8 8次，最少为次，最少为0 0次。次。n n房间里除了史密斯先生外的房间里除了史密斯先生外的9 9个人，他们与别人握手的次数分别为个人，他们与别人握手的次数分别为0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7，8 8次。次。n n要知道史密斯太太和别人握手的次数，只需确定除史密斯先生外的要知道史密斯太太和别人握手的次数，只需确定除史密斯先生外的9 9人人中哪一个是史密斯太太即可。中哪一个是史密斯太太即可。n n根据以上信息，建立图模型根据以上信息，建立图模型第43页，共71页，编辑于2022年，星期六 0-8号分别代表握手次数为号分别代表握手次数为0-8次的次的9个人（史密斯先生除外）。个人（史密斯先生除外）。8号握手号握手8次，则其配偶肯定是次，则其配偶肯定是0号；以此类推，号；以此类推，7号的配偶是号的配偶是1号，号，6号的配偶是号的配偶是2号，号，5号的号的配偶是配偶是3号。所以，史密斯夫人是号。所以，史密斯夫人是4号，即史密斯夫人握手次数为号，即史密斯夫人握手次数为4次。次。第44页，共71页，编辑于2022年，星期六n n由图可知：n n8号的配偶是0号；n n7号的配偶是1号；n n6号的配偶是2号；n n5号的配偶是3号；n n史密斯太太是4号，所以史密斯太太和别人握了4次手。第45页，共71页，编辑于2022年，星期六实例二：商人安全过河问题三名商人各带一个随从乘船渡河，现有一只小船三名商人各带一个随从乘船渡河，现有一只小船只能容纳两个人，由他们自己划行，随从们密约，在只能容纳两个人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。河的任一岸，一旦随从的人数比商人多，就杀人越货。但如何乘船渡河由商人决定，试给出一个商人安全渡但如何乘船渡河由商人决定，试给出一个商人安全渡河的方案。河的方案。第46页，共71页，编辑于2022年，星期六问题分析问题分析多步决策过程多步决策过程决策决策：每一步每一步(此岸到彼岸或彼岸到此岸此岸到彼岸或彼岸到此岸)船上的人员。船上的人员。要求要求：在安全的前提下在安全的前提下(两岸的随从数不比商人多两岸的随从数不比商人多),),经有限步经有限步使全体人员过河。使全体人员过河。商人仆人k为奇数k为偶数此岸彼岸第47页，共71页，编辑于2022年，星期六建模商人仆人设k次渡河前此岸的商人数为xk，随从数为yk，则xk，yk=0，1，2，3定义状态向量Sk=(xk,yk)定义决策：第k次渡船上的商人数为uk，随从数为vk，则d=(uk,vk)允许决策集合：D=(u,v)|1u+v2,u,v=0,1,2k为奇数k为偶数此岸彼岸状态转移规律：第48页，共71页，编辑于2022年，星期六模型构成模型构成xk第第k次渡河前此岸的商人数次渡河前此岸的商人数yk第第k次渡河前此岸的随从数次渡河前此岸的随从数xk,yk=0,1,2,3;k=1,2,sk=(xk,yk)过程的状态过程的状态S=(x,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2S 允许状态集合允许状态集合uk第第k次渡船上的商人数次渡船上的商人数vk第第k次渡船上的随从数次渡船上的随从数dk=(uk,vk)决策决策uk,vk=0,1,2;k=1,2,sk+1=sk dk+(-1)k状态转移律状态转移律求求dk D(k=1,2,n),使使sk S,并按并按转移转移律律由由 s1=(3,3)到达到达 sn+1=(0,0).多步决策多步决策问题问题第49页，共71页，编辑于2022年，星期六模型求解模型求解xy3322110 穷举法穷举法 编程上机编程上机 图解法图解法状态状态s=(x,y)16个格点个格点 10个个 点点允许决策允许决策 移动移动1或或2格格;k奇奇,左下移左下移;k偶偶,右上移右上移.s1sn+1d1,，d11给出安全渡河方案给出安全渡河方案考虑考虑4名商人各带一随从的情况名商人各带一随从的情况d1d11允许状态允许状态S=(x,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2第50页，共71页，编辑于2022年，星期六用图的邻接矩阵求解：用图的邻接矩阵求解：首先介绍图论中的一个定理首先介绍图论中的一个定理G G是一个图，是一个图，V V（G G）为）为G G的顶点集，的顶点集，E(G)E(G)为为G G的边集。的边集。设设G G中有中有n n个顶点个顶点 ;为为G G的邻接距阵，其中的邻接距阵，其中 定理定理1 1：设：设A A（G G）为图）为图G的邻接距阵，则的邻接距阵，则G中从顶点中从顶点 到顶点到顶点 ，长度为，长度为 k k的道路的条数为的道路的条数为 中的中的i i 行行j j 列元素列元素.第51页，共71页，编辑于2022年，星期六下面分析及求解下面分析及求解假假设设渡渡河河是是从从南南岸岸到到北北岸岸，（m，n）表表示示南南岸岸有有m个个商商人人，n个随从，全部的允许状态共有个随从，全部的允许状态共有10个个以以 为为顶顶点点集集，考考虑虑到到奇奇数数次次渡渡河河及及偶偶数数次次渡河的不同，我们建立两个邻接距阵渡河的不同，我们建立两个邻接距阵 第52页，共71页，编辑于2022年，星期六其中其中A表示从南岸到北岸渡河的图的邻接距阵，表示从北岸到南岸渡河的图的邻接距阵。由定理1、我们应考虑最小的k，中1行10列的元素不为0，此时 即为最少的渡河次数，而矩阵 中1行10列的元素为最佳的路径数目。经过计算K=5时,的第1行10列元素为2，所以需11次渡河，有两条最佳路径.第53页，共71页，编辑于2022年，星期六n n实例三实例三 渡河问题渡河问题 n n某人带狗、羊、以及蔬菜渡河，一小船除需某人带狗、羊、以及蔬菜渡河，一小船除需人划外，每次只能载一物过河。而人不在人划外，每次只能载一物过河。而人不在场时，狗要吃羊，羊要吃菜，问此人应如场时，狗要吃羊，羊要吃菜，问此人应如何过河？何过河？n n模型构成模型构成：n n此问题可化为状态转移问题，用四维向量此问题可化为状态转移问题，用四维向量（人，狗，羊，菜）来表示状态，当一物（人，狗，羊，菜）来表示状态，当一物在此岸时相应分量取在此岸时相应分量取1，而在彼岸时则取，而在彼岸时则取0。第54页，共71页，编辑于2022年，星期六(1)(1)可取状态可取状态 人在此岸人在此岸 ：(1,1,1,1)(1,1,1,1)，(1,1,1,0)(1,1,1,0)，(1,1,0,1)(1,1,0,1)，(1,0,1,1)(1,0,1,1)，(1,0,1,0)(1,0,1,0)人在彼岸：人在彼岸：(0,0,0,0)(0,0,0,0)，(0,0,0,1)(0,0,0,1)，(0,0,1,0)(0,0,1,0)，(0,1,0,0)(0,1,0,0)，(0,1,0,1)(0,1,0,1)总共有十个可取状态。总共有十个可取状态。(2)(2)现在用状态运算来完成状态转移。由于摆一次游戏即可改变现有状态，为现在用状态运算来完成状态转移。由于摆一次游戏即可改变现有状态，为此再引入一个四维转移向量，用它来反映摆渡情况用此再引入一个四维转移向量，用它来反映摆渡情况用1 1表示过河，表示过河，0 0表示未表示未过河。例