图论模型在实际中的应用

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学建模,雷涛 罗睿辞 王尧 汪瑜婧,数学建模的定义,目前还没有统一的定义,数学模型是为一种特殊目的而建立的一个抽象的、简化的结构。,描述现实世界的一部分特征,表现事物之间的一部分客观联系,数学模型的分类,微分方程模型,差分方程模型,层次分析模型,线性规划模型,动态规划模型,图论模型,其它模型,主要内容,建模的方法和步骤,汪瑜婧,图论模型的建立,罗睿辞,图论模型的选择和关系的简化,雷涛,其它数学模型举例,王尧,建模的方法和步骤,模型准备,模型假设,模型的建立,模型求解与分析,模型检验,模型应用,问题的提出,2007CUMCM B,题 乘公交，看奥运,给定若干条公交线路，以及在每条公交线路中任意相邻的两站之间所花费的时间。,并且给定乘客在任意站点换乘的耗时,要求给出任意两公汽站点之间线路选择问题的一般数学模型与算法，求出最佳的公交线路,.,模型的假设,对”最优”的理解有三个具有代表性的指标：,时间最短,花费最少,最方便（换乘次数最少）,不同的人群对最优的理解不同,需要根据实际定义,.,可以根据需要定义代价函数,三个指标的权重不同,代价值也不同。,以时间最短为例,模型的建立,G=(V,E),每个车站：,G,的顶点,每条公交线路相邻两点的连线：,G,的边,边的权重：耗费时间 点的权重：换乘时间,并不是一个简单图，两点间可能有多条边,5,9,3,7,a,c,b(8),考虑,a,经过,b,到,c,的最短路径,由于有换乘的情况，只记录任意两点间的最短路径是不够的。,并非一个标准的图论模型,与经典最短路径问题比较,5,6,7,a,c,b(8),Min(a,b,)=5,Min(b,c,)=3,Min(a,c,)=5+6=11,3,转化成标准的图论模型,每条公交线路抽象为一层,层与层之间相连的顶点均代表同一个车站,它们之间的边,(,虚线,),的权值为换乘花费的时间,调用,M*M,次,Dijkstra,算法才能得到最优解,M,为公交线路的总数,回顾上图,导致无法使用标准算法原因,:,Min(a,b,),和,Min(b,c,),之间需要计算附加耗时,不用换车的线路成为最佳路径,改进的想法,:,一次性地处理不用换车的情况,5,6,7,a,c,Min(a,b,)=5,Min(b,c,)=3,Min(a,c,)=5+6=11,3,b(8),模型的求解,标准算法,:,每次选择一个新顶点进行扩展,所有顶点扩展完毕即为最优解,修改后的算法,每次对一个顶点所能选择的所有公交线路扩展,所有不用换乘就能到达的顶点均在一次中处理,所有顶点扩展完毕即为最优解,.,算法描述,一次将扩展出多个顶点,用最小值堆保存,初始,:,起点对应的节点,S,入堆；并赋予标志信息,Time(S,)=0,取堆顶,对此定点,逐一枚举所有不用换乘就能到达的顶点,更新堆中对应点的标志信息,.,不断重复取堆顶的过程,直到取出的顶点为最终目标,T,Time(T,),即为所求,举例说明算法步骤,3,2,4,5,1,3,2,a,b,c,d,e,f,g,12,9,8,15,9,20,6,11,9,22,5,考虑顶点,b,到顶点,g,的路径,问题重述,加入步行的因素,即任意两个车站之间人都可能通过步行到达,并给出步行的时间代价,.,由于每两点之间均有步行路径,每次扩展都将涉及到所有顶点,复杂度增加不少,改进的办法,预处理 找到两个相邻顶点之间路径的最小值,如果它加上两个顶点的权值之后后,仍然小于一些其它的路径,就可以将其它路径删除,.,这样至少可以删除不少步行路径,考虑实际情况,可设定步行时间的上限,.,5,6,7,a,c,加入步行的路径,并给定权值,20,算法的总结,关键在于如何解决换乘的耗时,扩展节点的策略与经典算法不同,算法实际用到了分支界限法的思想,类似于回溯法，但是求解的目标不同。,目标：找到使目标函数取极值的解。,分支界限法思想,以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树,从一个点开始，每次以一定的策略扩展一些结点。每一个活结点一旦成为扩展结点，就一次性产生其所有子结点，并从活节点中移除。在产生 的子结点中，导致不可行解或导致非最优解的子结点被舍弃，其余的加入活结点表中。,选择扩展的节点,从活结点表中选择下一扩展结点可能有不同的方式,队列式分支限界法：先入先出的原则,优先队列式分支限界法：选择优先级最高的节点进行扩展,最大效益问题：最大值堆,最小耗费问题：最小值堆,一个简单的例子,印刷电路板将布线区域划分为,nm,个方格阵列,精确的电路板布线问题要求确定连接方格,a,的中点到方格,b,的中点的最短布线方案。,布线时电路只能沿直线或直角布线。,为避免线路相交，已布线方格做上封闭标记，其他线路布线不允许穿过封闭区域。,a,b,1,1,a,1,1,b,2,2,1,1,a,1,2,2,1,2,b,2,3,2,2,1,1,a,1,2,2,1,2,b,2,3,3,2,2,1,1,a,1,2,2,1,2,b,2,3,4,3,2,2,1,1,a,1,2,2,1,2,b,2,3,4,5,3,2,2,1,1,a,1,2,2,1,2,b,2,3,4,5,6,6,3,2,2,1,1,a,1,2,2,1,2,b,2,3,4,5,6,7,6,7,3,2,2,1,1,a,1,2,2,1,2,b,2,3,4,8,5,6,7,8,6,7,8,建模步骤的总结,模型的准备,提出问题，搜集数据。,模型的假设,根据实际情况，提出合理的假设简化问题。,模型的建立,根据所作的假设分析对象的因果关系，利用对象的内在规律和适当的数学工具，构造各个量间的等式关系或其它数学结构。,建模步骤的总结,模型的分析与求解,已建立的模型是否有标准解法,转化成标准模型,对已有的标准解法修改，以适应模型的求解,模型的检验,灵敏性，鲁棒性,模型的应用,图论模型的引入,引例,现有,6,个人，任意两人之间或者相互认识，或者相互不认识，证明这,6,个人中，或者有,3,个人彼此都认识，或者有,3,个人彼此不认识,思路一,只有,6,个人，人数非常少，可以枚举任意两人之间的关系，然后判断每一种情况是否符合题意。如果所有情况都满足，则命题成立。,虽然只有,6,个人，但是这样做的时间复杂度可不低，枚举次数为,2,15,只能借助计算机了。,有没有人可以直接证明的办法呢？,思路二,有了图论这个强大的工具,我们还是像往常一样，以人为顶点，关系为边，建图,但是为了以后的直观，这里图的建立有一点小小的不同：,如果两个人之间相互认识，则在这两个人,(,顶点,),间连一条红色边，如果两个人不认识，则在这两个人,(,顶点,),间连一条蓝色边,(,下面会看到这样做的好处,),那么这样我们就得到了一个由红边和蓝边组成的,6,阶完全图,我们实际上要证明的就是这个图中或者存在一个红三角形,(,认识,),，或者存在一个蓝三角形,(,不认识,),任取一个顶点,v,0,，由它连出,5,条边到其它的顶点，这五条边只有红色和蓝色两种,根据抽屉原理，肯定有一种颜色的边有,3,条或,3,条以上,不妨设为红色,v,i,v,0,v,j,v,k,如果,vi,vj,vk,之间的边都是蓝边，则图中存在一个蓝三角形,如果至少有,1,条为红边，那么它总会与,v0,发出的两条红边组成一个红三角形。,这样就证明了这个命题,现有,n,根长度不同的小木棍，每根木棍数量无限，取出一些小木棍可以拼出一根长度为这些小木棍长度之和的木棍。现在要求最小的整数,k,，使得长度大于等于,k,的木棍都能够被给出的,n,根小木棍拼出。,例如，现在有,3,根小木棍，长度分别,3,5,7,它们可以拼出长度为,3,5,6,7,8,9,10,11,12,13,的木棍，看上去,5,就是答案，怎么证明呢？,可以考虑把能够拼出来的木棍长度,x,根据模,3,的结果分成,3,类,(0,1,2),对于,x mod 3=0,3,能够拼出来，那么,6,9,12,等等模,3,为,0,的数都可以被拼出来,对于,x mod 3=1,，,7,能被拼出来，那么,7,10,13,等等都能被拼出来,对于,x mod 3=2,，,5,能被拼出来，那么,8,11,14,等等都能被拼出来,也就是说，,5,确实是我们要求的答案,这个题看上去似乎毫无头绪，那就先看看简单的情况吧！,根据上面的证明，可以发现一种思路，不妨把上述结果推广一下：,设,n,根木棍的长度为,L1,L2,Ln,不妨设,L1,为所有木棍中最短的,现在把能够拼出的木棍长度根据模,L1,的结果分为,L1,类,(0,1L1-1),若某一类中的数模,L1,的结果为,i,则它们组成的集合为,Si,显然，如果存在一个集合,Si,为空，则问题无解,现在考虑所有集合都不为空的情况：,设每个集合的最小元为,b0,b1bl1-1 (,集合不为空，肯定存在最小元,),那么如何去求题目要求的,k,呢？,考虑这样一个值：,k=max ,b,n, - L1,，,1=n0.,k,不属于任何,Si,集合,否则与,k,是某个,S,中最小元。即,k,不能被小木棍拼出。,对任意,Lk,设,L S,p,，,L+L1,maxb,n,=,b,p,故,Lb,p,-L1,而,L,b,p,(mod p),所以,L=,b,p,，所以,L,一定能够被拼出,由以上两点可知，,k,一定是不能被拼出的木棍长度中的最大值,那么,k+1,就是我们要求的答案！,还剩下最后一步：求,b,0,b,1,b,2,b,l1-1,也就是每个集合中的最小元,事实上，每一个能被拼出来的木棍长度,x,，都是从,0,开始，用已有的小木棍拼出来的。那么就可以把集合的编号看做顶点，小木棍的长度看边的长度，建立一个图。对于每个点,i(,集合,i),，都连出,n,条边，长度为,L1,L2,Ln,。对于长度为,Lk,的边，连向编号为,(,i+Lk,) mod L1,的顶点。,对于从顶点,i,到,j,的一条长度为,L,的路径，表示集合,i,中的一个数加上,L,后得到的数属于集合,j,。,对于任意一个能拼出来的数,x(,设,x mod L1=p),根据上面的建图规则，,x,一定是点,0,到,p,的一条路径的长度。,反过来，,0,到,p,的所有路径长度都属于,S,p,。,所以，可以得出结论：,Sp,中的最小元其实就是顶点,0,到顶点,p,的最短路径长度。,有了这个结论，我们就可以很容易的求出序列,bn,了,至此，这个问题也就被完美的解决,数学建模,模型的选择、关系的简化,很多问题都是通过建立图论模型解决的,图论中常见的模型有序列、树、各种图,如何有效选择数学模型，简化原问题中元素之间的关系是数学建模的关键,题目,坐船问题（改编自湖南省信息学省队选拔赛试题）,北大有,n,个学生去公园划船：,一只船最多坐,2,个人；,出于娱乐目的，大家决定同船的,2,个人要么同姓要么同名；,每个人都必须上船，且不能有脚踏多只船的情况,问最少需要几只船。,例子,6,个同学：姚金宇，李金宇，姚峰宏，陈峰宏,姚金宇 姚峰宏,陈峰宏,李金宇,姚金宇 李金宇,陈峰宏 姚峰宏,例子,4,个同学：陈峰宏，囧峰宏，罗睿辞，廖叶子,罗睿辞同学想和廖叶子同学坐同一船是不行的，因为他们不同名也不同姓,陈峰宏 囧峰宏,罗睿辞,廖叶子,陈峰宏 囧峰宏,罗睿辞 廖叶子,将每一同学视为一元素，元素之间的关系为同名或者同姓,构图是很自然的思路：,2,名同学同名或者同姓就连一条边,一条边就代表了一种坐船的搭配方式,用最少的边覆盖图中的点,一般图的最小边覆盖问题,一般图最大匹配问题，算法复杂，实现麻烦。,建模,姚金宇,李金宇,姚峰宏,陈峰宏,陈峰宏,囧峰宏,罗睿辞,廖叶子,建模,图是本题信息最充分、最自然的模型，但其中数据关系存在很多冗余，没有充分利用原题的条件,单独看同名、同姓这,2,种关系，它们都是等价关系，具有传递性,那么换一种模型构造如何？,把图转换成树来考虑,建模,对于原图中的每一个连通分量，一定可以转换成一棵二叉树,树中一个结点的左孩子跟其同姓；,一个结点的右孩子跟其同名。,证明用反证法,罗睿辞,罗贯中,罗纳尔多,廖睿辞,罗睿辞,罗贯中,罗纳尔多,廖睿辞,问题的解决,含有,n,个点的连通分量，至少需要,(n+1) div 2,只船,使用贪心法，一定可以构造出一个只需,(n+1) div 2,只船的解,罗睿辞,罗贯中,罗纳尔多,廖睿辞,罗纳尔多是罗贯中的独生子，去掉他们,2,个，树依然连通,罗睿辞,廖睿辞,廖睿辞依然是罗睿辞的独生子，将它们分成一组,罗贯中,罗纳尔多,罗睿辞,廖睿辞,得到了一个最优解,贪心构造,1,、若叶子结点是父亲的独生子，则删去它们,2,个，树依然保持性质,2,、若父亲结点有,2,个孩子,重复以上步骤直至树为空或者只剩一个结点为止,贪心举例,陈峰宏,贾 由,陈 云,王 云,贾宝玉,贾 云,贪心举例,陈峰宏,贾 由,陈 云,王 云,贾宝玉,贾 云,贪心举例,陈峰宏,贾 由,陈 云,王 云,贾宝玉,贾 云,陈峰宏,贾 由,陈 云,王 云,贾宝玉,贾 云,贪心举例,贪心举例,陈峰宏,贾 由,陈 云,王 云,贾宝玉,贾 云,贪心举例,陈峰宏,贾 由,陈 云,王 云,贾宝玉,贾 云,小结,通过无向图到二叉树的转化，将一个复杂的匹配问题用简单贪心解决了,建模是一个去粗取精的过程，要尽可能利用对我们有利的信息，而忽略那些与我们目标无关的信息,LCA,与,RMQ,问题之间相互转化，就是树形模型与序列模型相互辅助的经典例子,希望本例会对同学们今后的解题有所帮助！,数学建模,看起来，总会让人觉得,是一种很抽象的概念,如果把概念简单一点，再通俗一点，大概就是把一些实际中碰到的问题抽象化，化简成类似的数学问题，然后就可以用我们已经知道的方法和工具来求解,但是其实数学建模还有很多更深刻的含义和价值，不过已经超出,我可以讲述的很清楚的范围了,其它数学模型举例,而且，其实计算机实现的问题建模不见得就一定局限于图论或者其他离散数学问题的这些方面,还有很多方面都是可以利用数学建模思想和方法的,而有些时候，其实都是我们不经意间已经在数学建模了，只是自己没有在意而已。,比如说数论中有关于素数筛选和测试，因式分解算法，一些特殊的进位制问题，快速幂,取,模等问题其实都可以用数学建模的方式来求解。,下面我要讨论的是关于组合计数问题的一些讨论。,组合数学的问题随处可见，他的历史渊源扎根于古老的数学娱乐和游戏之中，而在当今社会中同样发挥着重要的作用。简单的说，组合数学研究一个集合的物体进行满足一些规则的排列。具体的说来，组合数学往往研究的是这些排列的存在性，计数和分类。有时候还需要构造出满足条件的一个或者多个最优的排列。排列组合，容斥原理等都是这一方面的理论。,其中很多时候都会广泛的运用到递推和生成函数，这也是建立数学模型并用计算机求解的优势所在之一。,E1,E2,E3,棋,盘,多,项,式,问题简述,一个国际象棋棋盘，,若,两个,主教,互相不攻击,，则,当且仅当他们不处于同一条斜线上。,我们可以讨论,在一个,n,n,的棋盘上放,k,个互相不攻击的,主教,有多少种方法？,例如，,当,n=8,，,k=6,时，,即在,88,的棋盘上放,6,个主教,有,5599888,种方法,布棋方案数,R,k,(C),设,C,是一个棋盘，,R,k,(C),表示把,k,个相同的棋子布到,C,中,，,且任意两个棋子不能处于同一行或者同一列的方案数（把斜线换成行和列），并规定对于任意的棋盘,C,有,R,0,(C)=1,。,棋盘多项式,设,C,是棋盘，则,R(C)=R,k(,C),x,k,叫做他的棋盘多项式,可以证明步棋方案数,R,k,(C),具有下面的性质,:,1),对于任意的棋盘,C,和正整数,k,，如果,k,大于,C,中方格的总数，则,R,k,(C)=0,；,2),R,1,(C),等于,C,中的方格数,3),设,C1,和,C2,是,2,个棋盘，如果,C1,经过旋转或者翻转变成了,C2,则,R,k,(C1)= R,k,(C2),4),设,Ci,是从棋盘,C,中去掉指定的方格所在的行和列以后剩下的棋盘，,C1,是从棋盘,C,中去掉指定的方格以后剩下的棋盘，则有,R,k,(C)= R,k-1,(Ci)+ R,k,(C1),（,k=1,）,5),设棋盘,C,由两个子棋盘,C1,和,C2,组成，如果,C1,和,C2,的步棋方案是互相独立的，则有,Rk(C)=R,i,(C1) *R,k-i,(C2),显然，在上述定义中当,k,大于棋盘的格子数时,R,k,(C)=0,，所以,R(C),一般只有有限项。,例如对于,R(,AT,)=R,0,(,AT,)+R,1,(,AT,),x+R,2,(,AT,),x,2,=1+2x+x,2,At,根据,R,k,(C),的性质不难得到,R(C),的性质,R(C)=xR(Ci)+R(C1),R(C)=R(C1)*R(C2),此后我们就用这两条性质计算棋盘多项式,另外，我们回到刚才的问题,我们可以注意到白格主教和黑格主教是不会互相攻击的,所以问题可以化简为白格放,i(i,=k),个棋子和黑格放,k-i,个棋子分别处理,而且处理方法是一样的。,为了直观，我们把白格从棋盘中抽出,小方格和棋盘都顺时针旋转,45,度，再压缩，黑格同样,最后都可以化建成左图情况,我们希望知道的，就是在这样的一个棋盘上放置,i(or,k-i,),各两两不同行不同列的象有多少种放法,由于行列关系是相对的，所以行列顺序不重要，所以把宽度小的行放在宽度大的行之上，将图转换成这样的情况。,然后，我们就可以继续编写算法来把这种有序的图形递归化简，然后利用棋盘多项式的规则化简,最后我们可以从第,x,的,k,次方项的系数得知放置,k,个互不攻击的象的方法数有多少了,