最短路径问题

数学建模讲座主讲人：王晓峰内容1：数学建模及其竞赛2：中国大学生数学建模竞赛历程3：建模过程与方法4：建模案例分析5：数学建模论文的撰写1.数学建模及其竞赛

——什么是数学建模数学建模是构造刻划客观事物原型的数学模型并用以分析、研究和解决实际问题的一种科学方法。运用这种科学方法，必须从实际问题出发，遵循从实践到认识再实践的认识规律，围绕建模的目的，运用观察力、想象力的抽象概括能力，对实际问题进行抽象、简化，反复探索，逐步完善，直到构造出一个能够用于分析、研究和解决实际问题的数学模型。因此，数学建模是一种定量解决实际问题的创新过程。1.数学建模及其竞赛

——数学建模竞赛题目

数学建模竞赛的题目由日常生活、工程技术、经济管理、社会生活等领域中的实际问题简化加工而成，它对数学知识要求不一定深，一般没有事先设定的标准答案，但留有充分余地供参赛者发挥其聪明才智和创造精神。从下面一些题目的标题可以看出其实用性和挑战性：“DNA序列分类”、“血管的三维重建”、“公交车调度”、“SARS的传播”、“奥运会临时超市网点设计”、“长江水质的评价和预测”——1.数学建模及其竞赛

——数学建模竞赛题目1998A、投资的收益和风险；B、灾情巡视路线1999A、自动化车床管理；B、钻井布局2000A、DNA序列分类；B、钢管订购和运输；2001A、血管的三维重建；B、公交车调度；2002A、车灯线光源优化设计；B、彩票中的数学；2003A、SARS的传播；B、露天矿生产的车辆安排；2004A、奥运会临时超市网点设计；B、电力市场的输电阻塞管理；2005A、长江水质的评价和预测；B、DVD在线租赁；2006A、出版社的资源配置；B、艾滋病疗法的评价及疗效的预测；A、国人口增长预测；B、乘公交，看奥运。

A、数码相机定位;B、高等教育学费标准探讨A、制动器试验台的控制方法分析B、眼科病床的合理安排A、储油罐的变位识别与罐容表标定B、2010年上海世博会影响力的定量评估1.数学建模及其竞赛

——数学建模竞赛的形式

竞赛评奖以假设的合理性、建模的创造性、结果的正确性和文字表述的清晰程度为主要标准。可以看出，这项竞赛从内容到形式与传统的数学竞赛不同，既丰富、活跃了广大同学的课外生活，也为优秀学生脱颖而出创造了条件。数学建模竞赛以通讯形式进行。三名大学生组成一队，可自由地收集资料、调查研究，使用计算机和任何软件，甚至上网查询，但不得与队外任何人包括指导教师讨论。时间：三天。要求每个队完成一篇包括模型的假设、建立和求解，计算方法的设计和计算机实现，结果的分析和检验，模型的改进等方面的论文。1.数学建模及其竞赛

——数学建模竞赛的特点竞赛让同学们面对一个从未接触过的实际问题，运用数学方法和计算机技术加以分析、解决，他们必须开动脑筋、拓宽思路，充分发挥创造力和想象力，培养同学们创新意识及主动学习、独立研究的能力。竞赛紧密结合社会热点问题，富有挑战性，吸引着学生关心、投身国家的各项建设事业，培养他们理论联系实际的学风。竞赛需要学生在很短时间内获取与赛题有关的知识，锻炼同学们收集资料的能力，提高撰写科技论文的文字表达水平。竞赛要三个同学共同完成一篇论文，在竞赛中要分工合作、取长补短、求同存异，既有相互启发，也有相互争论，培养了学生们同舟共济的团队精神和进行协调的组织能力。竞赛是开放型的，三天中没有或者很少有外部的强制约束，同学们要自觉地遵守竞赛纪律，公平地开展竞争。诚信意识和自律精神是建设和谐社会的基本要素之一，同学们能在竞赛中得到这种品格锻炼对他们的一生是非常有益的。

内容1：数学建模及其竞赛2：中国大学生数学建模竞赛历程3：建模过程与方法3：建模案例分析4：数学建模论文的撰写中国大学生数学建模竞赛历程（1）

1988.6大学生数学建模竞赛最早是1985年在美国出现的，叶其孝教授在美国讲学期间向美国大学生数学建模竞赛发起者和负责人Fusaro教授了解这项竞赛的情况，商讨中国学生参赛的办法和规则。1989.2.24～26

我国大学生（北京大学、清华大学、北京理工大学共4个队）首次参加美国大学生数学建模竞赛，自此每年我国都有同学参加这项竞赛。中国大学生数学建模竞赛历程（2）1989.3《高校应用数学学报》第4卷第1期发表叶其孝教授的文章“美国大学生数学建模竞赛及一些想法”，第一次向国内介绍这项竞赛。1990.12.7～9上海市举办大学生（数学类）数学模型竞赛，这是我国省、市级首次举办数学建模竞赛。中国大学生数学建模竞赛历程（3）1992.11.27～291992年部分城市大学生数学模型联赛举行，这是全国性的首届竞赛，10省（市）79所院校的314队参加。1993.10.15～171993年全国大学生数学建模竞赛举行，16省（市）101所院校的420队参加。中国大学生数学建模竞赛历程（4）1994.10.28～301994年全国大学生数学建模竞赛举行，21省（市、自治区）196所院校的870队参加。内容1：数学建模及其竞赛2：中国大学生数学建模竞赛历程3：建模过程与方法4：建模案例分析5：数学建模论文的撰写3.建模过程简介

----什么是数学建模

把现实世界中的实际问题加以提炼，抽象为数学模型，求出模型的解，验证模型的合理性，并用该数学模型所提供的解答来解释现实问题，我们把数学知识的这一应用过程称为数学建模。3.建模过程简介

----数学建模的几个过程（1）模型准备（2）模型假设（3）模型建立（4）模型构成（5）模型求解（6）模型分析（7）模型检验（8）模型应用

（1）模型准备

了解问题的实际背景，明确其实际意义与建模目的，掌握对象的各种信息（要收集）。用数学语言来描述问题。（2）模型假设

根据实际对象的特征和建模的目的，对问题进行必要的、合理的简化，并用精确的语言提出一些恰当的假设，是建模至关重要的一步。如果对问题的所有因素一概考虑，是不现实的，所以高超的建模者能充分发挥想象力、洞察力和判断力，善于辨别主次，而且为了使处理方法简单，应尽量使问题线性化、均匀化。

（3）模型建立

在假设的基础上，利用适当的数学工具来刻划各变量之间的数学关系，建立相应的数学结构。（尽量用简单的数学工具）（4）模型构成

根据所作的假设分析对象的因果关系，利用对象的内在规律和适当的数学工具，构造各个量间的等式关系或其它数学结构。有高数、概率统计、图论、排队论、线性规划、对策论等等。提示：建立数学模型是为了让更多的人明了并能加以应用，因此工具愈简单愈有价值。

（5）模型求解

利用获取的数据资料，对模型的所有参数做出计算（估计）。可以采用解方程、画图形、证明定理、逻辑运算、数值运算等各种传统的和近代的数学方法，特别是计算机技术。实际问题的解决往往需要纷繁的计算，许多时候还得将系统运行情况用计算机模拟出来，因此编程和熟悉数学软件的能力非常重要。（6）模型检验

将模型分析结果与实际情形进行比较，以此来验证模型的准确性、合理性和适用性。如果模型与实际较吻合，则要对计算结果给出其实际含义，并进行解释。如果模型与实际吻合较差,则应该修改假设，在次重复建模过程。3.建模过程与方法

----建模全过程示意图3.建模过程与方法

----具备的数学知识1、数学分析2、高等代数3、概率与数理统计4、最优化理论5、图论6、组合数学7、微分方程稳定性分析8、排队论3.建模过程与方法

----具备的应用软件知识1、综合类：Matlab,Mathematic2、统计类：Spss,SAS,Statistics3、最优解：Lindo,Lingo3.建模过程与方法

----图论方法最短路问题两个指定顶点之间的最短路径—给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线（Dijkstra算法）每对顶点之间的最短路径（Dijkstra算法、Floyd算法）最小生成树问题连线问题—欲修筑连接多个城市的铁路设计一个线路图，使总造价最低（prim算法、Kruskal算法）图的匹配问题人员分派问题：n个工作人员去做件n份工作，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？(匈牙利算法)遍历性问题中国邮递员问题—邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线最大流问题运输问题最小费用最大流问题在运输问题中，人们总是希望在完成运输任务的同时，寻求一个使总的运输费用最小的运输方案3.建模过程与方法

----图论方法（1）基本概念（2）固定起点的最短路（3）每对顶点之间的最短路3.建模过程与方法

----最短路问题基本概念固定起点的最短路

从甲地到乙地之间是否有公路连通?在有多条通路的情况下，哪一条路最短?交通网络可用带权图来表示。顶点表示城市名称，边表示两个城市有路连通，边上的权值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径，不是指路径上边数之和最少，而是指路径上各边的权值之和最小。另外，若两个顶点之间没有边，则认为两个顶点无通路，但有可能有间接通路(从其它顶点达到)。路径上的开始顶点(出发点)称为源点，路径上的最后一个顶点称为终点，并假定讨论的权值不能为负数。从一个顶点到其余各顶点的最短路径

问题：给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径,并限定各边上的权值大于或等于0。

采用狄克斯特拉(Dijkstra)算法求解基本思想是：设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组：第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径v,…vk,就将vk加入到集合S中,直到全部顶点都加入到S中,算法就结束了)第二组为其余未确定最短路径的顶点集合(用U表示)。按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。狄克斯特拉算法的具体步骤如下：(1)初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,U中顶点u距离为边上的权(若v与u有边<v,u>)或∞(若u不是v的出边邻接点)。(2)从U中选取一个距离v最小的顶点k,把k加入S中(该选定的距离就是v到k的最短路径长度)。(3)以k为新考虑的中间点,修改U中各顶点的距离：若从源点v到顶点u(u∈U)的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边<k,u>上的权。(4)重复步骤(2)和(3)直到所有顶点都包含在S中。S U v0到0～6各顶点的距离{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,19}{0,1,2,3,5}{4,6} {0,4,5,6,10,9,17}{0,1,2,3,5,4} {6} {0,4,5,6,10,9,16}{0,1,2,3,5,4,6}{} {0,4,5,6,10,9,16}则v0到v1～v6各顶点的最短距离分别为4、5、6、10、9和16。狄克斯特拉算法如下(n为图G的顶点数,v0为源点编号)：voidDijkstra(intcost[][MAXV],intn,intv0){intdist[MAXV],path[MAXV];ints[MAXV];intmindis,i,j,u;for(i=0;i<n;i++){dist[i]=cost[v0][i]; /*距离初始化*/ s[i]=0; /*s[]置空*/ if(cost[v0][i]<INF) /*路径初始化*/ path[i]=v0; else path[i]=-1; } s[v0]=1;path[v0]=0; /*源点编号v0放入s中*/

for(i=0;i<n;i++)/*循环直到所有顶点的最短路径都求出*/{mindis=INF; u=-1; for(j=0;j<n;j++)/*选取不在s中且具有最小距离的顶点u*/ if(s[j]==0&&dist[j]<mindis) {u=j;mindis=dist[j]; } s[u]=1; /*顶点u加入s中*/ for(j=0;j<n;j++)/*修改不在s中的顶点的距离*/ if(s[j]==0) if(cost[u][j]<INF&&dist[u]+cost[u][j]<dist[j]) {dist[j]=dist[u]+cost[u][j];path[j]=u;}}Dispath(dist,path,s,n,v0); /*输出最短路径*/}voidPpath(intpath[],inti,intv0)/*前向递归查找路径上的顶点*/{intk;k=path[i];if(k==v0)return; /*找到了起点则返回*/Ppath(path,k,v0); /*找k顶点的前一个顶点*/printf("%d,",k); /*输出k顶点*/}voidDispath(intdist[],intpath[],ints[],intn,intv0){inti;for(i=0;i<n;i++) if(s[i]==1) {printf(“从%d到%d的最短路径长度为:%d\t路径为:",v0,i,dist[i]); printf("%d,",v0); /*输出路径上的起点*/Ppath(path,i,v0); /*输出路径上的中间点*/printf("%d\n",i); /*输出路径上的终点*/ } elseprintf("从%d到%d不存在路径\n",v0,i);}每对顶点之间的最短路径

问题：对于一个各边权值均大于零的有向图,对每一对顶点vi≠vj,求出vi与vj之间的最短路径和最短路径长度。

可以通过以每个顶点作为源点循环求出每对顶点之间的最短路径。除此之外,弗洛伊德(Floyd)算法也可用于求两顶点之间最短路径。

假设有向图G=(V,E)采用邻接矩阵cost存储,另外设置一个二维数组A用于存放当前顶点之间的最短路径长度,分量A[i][j]表示当前顶点vi到顶点vj的最短路径长度。弗洛伊德算法的基本思想是递推产生一个矩阵序列A0,A1,…,Ak,…,An,其中Ak[i][j]表示从顶点vi到顶点vj的路径上所经过的顶点编号不大于k的最短路径长度。

初始时,有A-1[i][j]=cost[i][j]。当求从顶点vi到顶点vj的路径上所经过的顶点编号不大于k+1的最短路径长度时,要分两种情况考虑：一种情况是该路径不经过顶点编号为k+1的顶点,此时该路径长度与从顶点vi到顶点vj的路径上所经过的顶点编号不大于k的最短路径长度相同；另一种情况是从顶点vi到顶点vj的最短路径上经过编号为k+1的顶点。那么,该路径可分为两段,一段是从顶点vi到顶点vk+1的最短路径,另一段是从顶点vk+1到顶点vj的最短路径,此时最短路径长度等于这两段路径长度之和。这两种情况中的较小值,就是所要求的从顶点vi到顶点vj的路径上所经过的顶点编号不大于k+1的最短路径。

弗洛伊德思想可用如下的表达式来描述：A-1[i][j]=cost[i][j]Ak+1[i][j]=min{Ak[i][j],Ak[i][k+1]+Ak[k+1][j]}(0≤k≤n-1)

采用弗洛伊德算法求解过程

考虑顶点v0,A0[i][j]表示由vi到vj,经由顶点v0的最短路径。只有从v2到v1经过v0的路径和从v2到v3经过v0的路径,不影响v2到v1和v2到v3的路径长度,因此,有：

考虑顶点v1,A1[i][j]表示由vi到vj,经由顶点v1的最短路径。存在路径v0-v1-v2,路径长度为9,将A[0][2]改为9,path[0][2]改为1,因此,有：

考虑顶点v2,A2[i][j]表示由vi到vj,经由顶点v2的最短路径。存在路径v3-v2-v0,长度为4,将A[3][0]改为4；存在路径v3-v2-v1,长度为4,将A[3][1]改为4。存在路径v1-v2-v0,长度为7,将A[1][0]改为7。将path[3][0]、path[3][1]和path[1][0]均改为2。因此,有：

考虑顶点v3,A3[i][j]表示由vi到vj,经由顶点v3的最短路径。存在路径v0-v3-v2,长度为8比原长度短,将A[0][2]改为8；存在路径v1-v3-v2-v0,长度为6(A[1][3]+A[3][0]=2+4=6)比原长度短,将A[1][0]改为6；存在路径v1-v3-v2,长度为3,比原长度短,将A[1][2]改为3；将path[0][2]、path[1][0]后path[1][2]均改为3。因此,有：

因此,最后求得的各顶点最短路径长度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从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弗洛伊德算法如下：voidFloyd(intcost[][MAXV],intn){intA[MAXV][MAXV],path[MAXV][MAXV];inti,j,k;for(i=0;i<n;i++) for(j=0;j<n;j++){A[i][j]=cost[i][j]; path[i][j]=-1;}for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) if(A[i][j]>(A[i][k]+A[k][j])){A[i][j]=A[i][k]+A[k][j];path[i][j]=k;}Dispath(A,path,n);/*输出最短路径*/}树的定义和基本术语

1、树的定义

树是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n>0，则：

（1）有且仅有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；

（2）除根结点以外的其它结点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm-1，每个集合Ti（i=0,1,…,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。

由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。

树的结构参见图6-1。

3.建模过程与方法-最小生成树问题

一、最小生成树（MST）概念1.设无向连通图G=（V，{E}），其子图G’=（V，{T}）满足：①V(G’)=V(G)n个顶点②G’是连通的③G’中无回路则G’是G的生成树2.最小生成树：一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图联通的最少的边。3.建模过程与方法-最小生成树问题

具有n个顶点的无向连通图G

其任一生成树恰好含n-1条边

生成树不一定唯一，如深度优先搜索生成树和广度优先搜索生成树。4.生成树代价:对图中每条边赋于一个权值（代价），则构成一个网，网的生成树G’=(V，{T})的代价是T中各边的权值之和，最小生成树就是网上所有可能的生成树中，代价最小的一类生成树。最小生成树也不一定唯一。5.求MST的一般算法可描述为：针对图G，从空树T开始，往集合T中逐条选择并加入n-1条安全边(u，v)，最终生成一棵含n-1条边的MST。当一条边(u，v)加入T时，必须保证T∪{(u，v)}仍是MST的子集，我们将这样的边称为T的安全边。

3.最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中一条“一个端点在U中(例如：u∈U)，另一个端点不在U中的边(例如：v∈V-U)，且(u，v)具有最小权值，则一定存在G的一棵最小生成树包括此边(u，v)。许多应用问题都是求无向连通图的最小生成树问题。例1：要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

例2：N台计算机之间建立通讯网顶点表示computer边表示通讯线权值表示通讯线的代价（通讯线长度，computer间距离等）要求：①n台计算机中的任何两台能通过网进行通讯；②使总的代价最小。-------求最小生成树[T]

最小生成树的实用例子例3：邮递员送信线路[T]顶点表示投递点边表示街道权值表示街道的长度要求：①完成n个投递点的投递；②使总路径长度最短,即求最小生成树[T]设N=（V，{E}）是一个连通网，V=[1，2，…，n}是N的顶点集合，辅助集合U，初值为{Uo}，用来存放当前所得到的最小生成树的顶点；辅助集合TE，初值为Ф，用来存放当前所得到的最小生成树的边。1）普里姆（Prim）算法Prim算法步骤1.TE=Ф,U={u0}2.当U≠V，重复下列步骤：(1)选取（u0,v0)=min{cost(u,v)|u∈U,v∈V-U}，保证不形成回路(2)TE=TE+（u0,v0),边（u0,v0)并入TE(3)U=U+{V0}，顶点V0并入U初始化：①②①④⑤

521③3466556⑥

①1③第1步：6①1③4第2步：④6①1③42第3步：5②④6①1③42第4步：23⑤

②5④6①1③4第5步：特点:以连通为主选代价最小的邻接边Prim算法的实现voidgraph::mintree(charu){ for(intk=0;k<vexnum;k++) if(vexs[k]==u) break; for(intj=0;j<vexnum;j++) if(j!=k) { closedge[j].index=k; closedge[j].lowcost=arcs[k][j]; }//给结构体数组赋值 closedge[k].lowcost=0;//初始化 for(inti=1;i<vexnum;i++) {//找到与顶点u相邻的权值最小的 intk=closedge[0].lowcost; for(intx=0;x<vexnum;x++)

（邻接矩阵存储）if(closedge[x].lowcost<k) k=closedge[x].lowcost; cout<<"("<<vexs[closedge[k].index]<<","<<vexs[k]<<")"; closedge[k].lowcost=0;//第k顶点并入U集合 for(j=0;j<vexnum;j++) if(arcs[k][j]<closedge[j].lowcost) { closedge[j].index=vexs[k]; closedge[j].lowcost=arcs[k][j]; }}//新的顶点并入U后，从新调整辅助数组}2）克鲁斯卡尔（Kruskal）算法Kruskal算法是逐步给生成树T中添加不和T中的边构成回路的当前最小代价边。特点:以最小代价边主。设N=（V，{E}）是个连通网,算法步骤为：1.置生成树T的初始状态为T=（V，{Ф}）2.当T中边数<n-1时,重复下列步骤:

从E中选取代价最小的边（v,u）,并删除之;

若（v,u）依附的顶点v和u落在T中不同的连同分量上，则将边（v,u）并入到T的边集中；否则，舍去该边，选择下一条代价最小的边.步骤(v,u)ET②①④⑤

③⑥

②①④⑤

③⑥

1(1,3)0②①④⑤

52③3466556⑥

②①④⑤

5③3466556⑥

21步骤(v,u)ET5(1,4)4(3,6)②①④⑤

5③66556⑥

②①④⑤

③66556⑥

②①④⑤

③⑥

②①④⑤

③⑥

步骤(v,u)ET6(2,3)②①④⑤

③6656⑥

边数=n-1=5代价=(1+2+3+4+5)=15②①④⑤

③⑥

123453.建模过程与方法

----图的匹配问题实例一：握手的次数史密斯先生和他太太邀请四对夫妻参加晚会。每个人到的时候，房间里的一些人都要与别的一些人握手。当然，每个人都不会与自己的配偶握手，也不会跟同一个人握手两次。之后，史密斯先生问每个人和别人握了几次手，他们的答案都不一样。那么，史密斯太太和别人握了几次手呢?这个问题具有挑战性的原因是因为它没有一个明显的起始点，但如果对此建立一个图模型，问题就变得很简单了。

分析：从题目我们得到了哪些信息?史密斯和太太邀请四对夫妻参加晚会--房间里共有10人。每个人都不会与自己的配偶握手--握手的两个人不是配偶。每个人都不会跟同一人握手两次--两个人间的握手最多是一次。史密斯先生问每个人和别人握了几次手，他们的答案都不一样--除史密斯先生外，每个人和别人握手的次数都不一样。除史密斯先生外，每人握手的次数最多是8次，最少为0次。房间里除了史密斯先生外的9个人，他们与别人握手的次数分别为0，1，2，3，4，5，6，7，8次。要知道史密斯太太和别人握手的次数，只需确定除史密斯先生外的9人中哪一个是史密斯太太即可。根据以上信息，建立图模型

0-8号分别代表握手次数为0-8次的9个人（史密斯先生除外）。

8号握手8次，则其配偶肯定是0号；以此类推，7号的配偶是1号，6号的配偶是2号，5号的配偶是3号。所以，史密斯夫人是4号，即史密斯夫人握手次数为4次。由图可知：8号的配偶是0号；7号的配偶是1号；6号的配偶是2号；5号的配偶是3号；史密斯太太是4号，所以史密斯太太和别人握了4次手。实例二：商人安全过河问题

三名商人各带一个随从乘船渡河，现有一只小船只能容纳两个人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但如何乘船渡河由商人决定，试给出一个商人安全渡河的方案。问题分析多步决策过程决策：每一步(此岸到彼岸或彼岸到此岸)船上的人员。要求：在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。商人仆人k为奇数k为偶数此岸彼岸建模商人仆人设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,2}k为奇数k为偶数此岸彼岸状态转移规律：模型构成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,2}S~允许状态集合uk~第k次渡船上的商人数vk~第k次渡船上的随从数dk=(uk,vk)~决策uk,vk=0,1,2;k=1,2,sk+1=sk

dk+(-1)k~状态转移律求dkD(k=1,2,n),使skS,并按转移律由s1=(3,3)到达sn+1=(0,0).多步决策问题模型求解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}用图的邻接矩阵求解：首先介绍图论中的一个定理G是一个图，V（G）为G的顶点集，E(G)为G的边集。设G中有n个顶点

;为G的邻接距阵，其中

定理1：设A（G）为图G的邻接距阵，则G中从顶点到顶点

，长度为k

的道路的条数为

中的i行j列元素.下面分析及求解假设渡河是从南岸到北岸，（m，n）表示南岸有m个商人，n个随从，全部的允许状态共有10个

以

为顶点集，考虑到奇数次渡河及偶数次渡河的不同，我们建立两个邻接距阵

其中其中A表示从南岸到北岸渡河的图的邻接距阵，

表示从北岸到南岸渡河的图的邻接距阵。

由定理1、我们应考虑最小的k，

中1行10列的元素不为0，此时

即为最少的渡河次数，而矩阵

中1行10列的元素为最佳的路径数目。经过计算K=5时,

的第1行10列元素为2，所以需11次渡河，有两条最佳路径.实例三渡河问题某人带狗、羊、以及蔬菜渡河，一小船除需人划外，每次只能载一物过河。而人不在场时，狗要吃羊，羊要吃菜，问此人应如何过河？模型构成：此问题可化为状态转移问题，用四维向量（人，狗，羊，菜）来表示状态，当一物在此岸时相应分量取1，而在彼岸时则取0。(1)可取状态人在此岸：(1,1,1,1)，(1,1,1,0)，(1,1,0,1)，(1,0,1,1)，(1,0,1,0)人在彼岸：(0,0,0,0)，(0,0,0,1)，(0,0,1,0)，(0,1,0,0)，(0,1,0,1)总共有十个可取状态。(2)现在用状态运算来完成状态转移。由于摆一次游戏即可改变现有状态，为此再引入一个四维转移向量，用它来反映摆渡情况用1表示过河，0表示未过河。例如(1,1,0,0)表示人带狗过河。此状态只有四个允许转移向量：d1=(1,0,0,0)，d2=(1,1,0,0)，d3=(1,0,1,0)，d4=(1,0,0,1)。现在规定状态向量与转移向量（分量）之间的运算为0+0=0，0+1=1，1+0=1，1+1=0(3)模型求解通过上面的定义，问题化为，由初始状态出发(1,1,1,1)，经过奇数次上述运算转移为状态(0,0,0,0)的转移过程。可用图表示为：

练习题1.今有3个油瓶，分别能装10kg、7kg和3kg油。已知10kg瓶中装满了油，其余两瓶为空瓶。现要将油分成两个5kg，没有秤，问能找到几种分油方案，使倒油的次数尽量的少？2.四名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人们手中。商人们怎样才能安全渡河呢?3.三个人和三个机器人要从左岸渡河到右岸。船只有一只，每次可以渡人或机器人共两名，三个人都会划船，机器人中只有一个会划船。为防止意外，每岸有人的时候，人的数目不能比机器人的数目少，问应当怎样渡河？内容1：数学建模及其竞赛2：中国大学生数学建模竞赛历程3：建模过程简介4：建模案例分析5：数学建模论文的撰写2007高教社杯全国大学生数学建模竞赛题目:B题：乘公交，看奥运

我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计