《浅谈论模型的建立与应用ppt课件》由会员分享,可在线阅读,更多相关《浅谈论模型的建立与应用ppt课件(27页珍藏版)》请在金锄头文库上搜索。
1、浅谈图论模型的浅谈图论模型的建立与运用建立与运用 引言v图论是数学的一个有趣的分支。v图论的建模,就是要抓住问题的本质,把问题笼统为点、边、权的关系。v许多看似无从入手的问题,经过图论建模,往往能转化为我们熟习的经典问题。例题1 Place the RobotsZOJ问题描画 有一个N*M(N,M=50)的棋盘,棋盘的每一格是三种类型之一:空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人,假设它们之间没有墙,那么它们可以相互攻击。问给定的棋盘,最多可以放置多少个机器人,使它们不能相互攻击。 Wall Grass Empty例题1 Place the RobotsZOJ模型一5
2、467832112346578于是,问题转化为求图的最大独立集问题。在问题的原型中,草地,墙这些信息不是我们所关怀的,我们关怀的只是空地和空地之间的联络。因此,我们很自然想到了下面这种简单的模型:以空地为顶点,有冲突的空地间连边,我们可以得到右边的这个图:例题1 Place the RobotsZOJ模型一5467832112346578在问题的原型中,草地,墙这些信息不是我们所关怀的,我们关怀的只是空地和空地之间的联络。因此,我们很自然想到了下面这种简单的模型:以空地为顶点,有冲突的空地间连边,我们可以得到右边的这个图:这是NP问题!我们将每一行,每一列被墙隔开,且包含空地的延续区域称作“块
3、。显然,在一个块之中,最多只能放一个机器人。我们把这些块编上号。同样,把竖直方向的块也编上号。例题1 Place the RobotsZOJ模型二123451234例题1 Place the RobotsZOJ模型二123451234把每个横向块看作X部的点,竖向块看作Y部的点,假设两个块有公共的空地,那么在它们之间连边。于是,问题转化成这样的一个二部图:112233445由于每条边表示一个空地,有冲突的空地之间必有公共顶点,所以问题转化为二部图的最大匹配问题。例题1 Place the RobotsZOJ模型二123412354112233445比较前面的两个模型:模型一过于简单,没有给问题
4、的求解带来任何便利;模型二那么充分抓住了问题的内在联络,巧妙地建立了二部图模型。为什么会产生这种截然不同的结果呢?其一是由于对问题分析的角度不同:模型一以空地为点,模型二以空地为边;其二是由于对原型中要素的选取有差别:模型一对要素的选取不充分,模型二那么保管了原型中“棋盘这个重要的性质。由此可见,对要素的选取,是图论建模中至关重要的一步。例题1 Place the RobotsZOJ小结例题2 出纳员的雇佣ACM Tehran 2000问题描画 有一家24小时营业的超市,需求雇佣一批出纳员。一天中每个小时需求出纳员的最少数量为R0,R1,R2,.,R23。有N个人恳求这项任务,每个恳求者,从一
5、个特定时辰开场延续任务恰好8个小时,设Wii=0.23表示从时辰i开场任务的恳求者的人数Wi=N=1000。 他的义务是计算出需求雇佣出纳员的最少数目,满足在每一时辰i,至少有Ri名出纳员在任务。例题2 出纳员的雇佣ACM Tehran 2000分析 初看此题,很容易使人往贪婪、动态规划或网络流这些方面思索。然而,对于此题,这些算法都无能为力。 由于此题的约束条件很多,为了理清思绪,我们先把标题中的约束条件用数学言语表达出来。设Si表示0i时辰雇佣出纳员的总数,那么我们可以将标题中的约束条件转化为下面的不等式组:0Si-Si-1Wi (0i23)Si-Si-8Ri (8i23)S23+Si-S
6、i+16Ri (0i7)例题2 出纳员的雇佣ACM Tehran 2000分析这样的不等式组,不由使我们想到了差分约束系统。对于每个不等式 Si-SjK,从顶点向顶点引一条权值为K的有向边。我们要求S23的最小值,就是要求顶点0到顶点23的最短路。留意上面第三条不等式:它包含三个未知数,无法在图中表示为边的关系。0Si-Si-1Wi (0i23)Si-Si-8Ri (8i23)S23+Si-Si+16Ri (0i7)怎怎样办例题2 出纳员的雇佣ACM Tehran 2000分析退一步思索:假设S23曾经确定了,那么上面的不等式组可以完全转化为一个有向图,顶点0到顶点的最短路,就是Si的解。而当
7、图中存在负权回路时,不等式组无解。至于S23,我们可以用二分法枚举,逐渐减少范围,用迭代法判别能否存在负权回路断定可行性,最终求得S23的最小值。时间复杂度为O(243*log2N)。0Si-Si-1Wi (0i23)Si-Si-8Ri (8i23)S23+Si-Si+16Ri (0i7)例题2 出纳员的雇佣ACM Tehran 2000小结此题用到了差分约束系统的实际,在竞赛中,这样的系统并不多见,但是却可以巧妙的处理一些难题。这类标题的模型都不明显,需求一定的思索和转化。做这类标题,关键是要把标题中的约束条件表示为不等式,再把不等式转化为图的最短路或最长路模型。例题3 贪婪之岛ZOJ问题描
8、画 有NN100000张卡片,每张卡片有三种才干,每种才干的才干值分别为Ai,Bi,Ci。每张卡片可以运用其中一种才干,且每张卡片只能运用一次。如今需求A张卡片运用第一种才干,B张卡片运用第二种才干,C张卡片运用第三种才干A+B+C100。请计算运用哪些卡片,以及运用卡片的哪项才干,可以使相应的才干值之和最大。例题3 贪婪之岛ZOJ分析 最优化问题的解法有很多种,比如动态规划,网络流等,而此题就是一个比较明显的网络流模型。 网络流模型中,权的类型众多,有流量,容量,还可以有费用。在此题中,容量可以作为选取的约束,确保解的合法性;费用那么表示选取的价值,确保解的最优性。因此,更确切地说,此题是一
9、个最大费用最大流模型。构图SP2P1P312345T每张卡片用顶点表示,另外加三个顶点P1,P2,P3,表示三种才干,还有源点S,汇点T。例题3 贪婪之岛ZOJ构图SP2P1P312345TA,0B,0C,0从源点分别向P1,P2,P3引一条弧,容量分别为A,B,C,费用为0。例题3 贪婪之岛ZOJ构图SP2P1P312345TA,0B,0C,0从P1,P2,P3向顶点(1iN) 分别引一条弧,容量为1,费用分别为Ai,Bi,Ci。例题3 贪婪之岛ZOJ构图SP2P1P312345TA,0B,0C,01,01,01,01,01,0从顶点(1iN) 向汇点引一条弧,容量为1,费用为0。例题3 贪
10、婪之岛ZOJ构图SP2P1P312345TA,0B,0C,01,01,01,01,01,0构图之后,求出从S到T的最大费用最大流,再检查流出P1,P2,P3的弧,并输出最优方案。时间复杂度:O(N3)例题3 贪婪之岛ZOJN N太大了,需求太大了,需求进一步一步优化!化!优化例题3 贪婪之岛ZOJ此题的卡片总数有十万之多,而最终要选取的卡片数不超越100张。假设在构图之前,把没有用的卡片先删掉,必将大大提高效率。什么样的卡片是没有用的呢?先思索第一种才干的选取:假设把全部卡片按第一种才干值从大到小排序,显然我们应该尽量从前面选A张出来,由于每张卡片只能运用一次,所以有能够会和其他的两种才干发生
11、冲突,而冲突的卡片数最多是B+C张,所以实践上对我们有用的卡片只是前面的A+B+C张。优化例题3 贪婪之岛ZOJ同理,对于第二种和第三种才干的选取,也只需保管其才干值最大的前A+B+C张卡片。这一步可以在线性时间内处理。这是一个既简单又有效的方法,经过这一步处置,保管下来的卡片数不会超越3(A+B+C)张,顶点数大大减少,求解最大费用最大流的时间复杂度降为O(A+B+C)3)。至此,算法曾经优化到了一个可以接受的地步,时间复杂度仅为O(N+(A+B+C)3)。优化例题3 贪婪之岛ZOJ假设还要进一步提高效率,可以用更有效的算法删掉多余的顶点。不过这样做意义不大,而且也不是本文讨论的要点。另外,
12、此题还可以转化为二部图模型,用最正确匹配算法求解。这一步留给读者本人思索。小结例题3 贪婪之岛ZOJ此题建立的是网络流模型。这类模型的算法系数大,编程复杂度也大,在竞赛中往往作为走投无路时的“候补算法。但是,网络流模型的适用性广,一些较复杂,或者约束较多的问题,网络流模型可以很好地处理,而基于网络流模型的问题又比较明显,这使得网络流模型有着广泛的运用。结语问题是千变万化的,如何建立问题的图论模型并没有通用的准那么。前面的几个例子都比较简单,在更复杂的问题中,有时我们会感到难以建立适当的模型,这时,我们需求在不改动问题原型本身的性质的前提下,对原型进展笼统,简化,在此根底上建立适宜,有效的模型。有时,我们建立了问题的一个模型之后,能够会感到难以求解,这时,我们能够需求对模型进展修正,转化,或者对原型进展更深化的分析,抽取其中较关键的要素,建立一个易于求解的模型。这些都需求我们有丰富的阅历,灵敏的思想以及良好的发明力。