《ACM算法浅谈图论模型的建立与应用.》由会员分享，可在线阅读，更多相关《ACM算法浅谈图论模型的建立与应用.（16页珍藏版）》请在金锄头文库上搜索。
1、浅谈型的建立与应用引言图论是数学的一个有趣的分支。图论的建模，就是要抓住问题的本质，把问题 抽象为点、边、权的关系。许多看似无从入手的问题，通过图论建模，往 往能转化为我们熟悉的经典问题。例题 1 Place the Robots (ZOJ)例题 1 Place the Robots（zoj）在问题的原型中，草地，墙这些信 息不是我们所关心的，我们关心的 只是空地和空地之间的联系。因此, 我们很自然想到了下面这种简单的 模型：以空地为顶点，有冲突的空地间连 边，我们可以得到右边的这个图：于是，间题转化为求图的最大独立 集问题。45撲型一在问题的原型中，草地，墙这些信 息不是我们所关心的，我们关
2、心的 只是空地和空地之间的联系。因此, 我们很自然想到了下面这种简单的 模型：以空地为顶点，有冲突的空地间连 边，我们可以得到右边的这个图：这足存冏駆/例题 1 Place the Robots (ZOJ)我们将每一行，每一列被墙隔开, 且包含空地的连续区域称作“块” O显然，在一个块之中， 最多只能放一个机器人。我们把 这些块编上号。同样，把竖直方向的块也编上号。例题 1 Place the Robots（zoj）例题 1 Place the Robots（zoj）把每个横向块看作x部的点，竖向 块看作Y部的点，若两个块有公共 的空地，则在它们之间连边。于是，问题转化成这样的一个二 部图：例
3、题 1 Place the Robots（zoj）由于每条边表示一个空地，有冲 突的空地之间必有公共顶点，所 以间题转化为二部图的最大匹配 间题。比较前面的两个模型：模型一过于简单，没有给问 题的求解带来任何便利；模型二则充分抓住了问题的内 在联系，巧妙地建立了二部图模型。为什么会产生这种 截然不同的结果呢？其一是由于对问题分析的角度不同: 模型一以空地为点，模型二以空地为边；其二是由于对 原型中要素的选取有差异：模型一对要素的选取不充分, 模型二则保留了原型中“棋盘”这个重要的性质。由此 可见，对要素的选取，是图论建模中至关重要的一步。例题2出纳员的雇佣(ACM Tehran 2000)问軀
4、描述有一家24小时营业的超市，需要雇佣一批岀纳员。一天 中每个小时需要出纳员的最少数量为R0,Rl,R2,.,R23。有N 个人申请这项工作，每个申请者，从一个特定时刻开始连 续工作恰好8个小时，设Wi (i=0.23)表示从时刻i开始工 作的申请者的人数(ZWi=N=1000)。你的任务是计算出需要雇佣出纳员的最少数目，满足在 每一时刻i,至少有Ri名出纳员在工作。例题2出纳员的雇佣(ACM Tehran 2000)今新初看本题，很容易使人往贪心、动态规划或网络流这 些方面思考。然而，对于本题，这些算法都无能为力。由于本题的约束条件很多，为了理清思路，我们先把 题目中的约束条件用数学语言表达
5、出來。设Si表示0i 时刻雇佣出纳员的总数，那么我们可以将题目中的约束条 件转化为下面的不等式组：0Si-Si-lWi(0iRi(8iRi(0i7)例题2出纳员的雇佣(ACM Tehran 2000)0Si-Si-lWi(0iRi(8iRi(0i7)这样的不等式组，不禁使我们想到了差分约束系统。对于每个不等式Si-SjK,从顶点j向顶点i引一条权 值为K的有向边。我们要求S23的最小值，就是要求顶点 0到顶点23的最短路。注意上面第三条不等式：它包含三个未知数，无法在图中 表示为边的关系。例题2出纳员的雇佣(ACM Tehran 2000)今新(0i23)(8i23)(0i7)0RiS23+S
6、i-Si+16Ri退一步考虑：如果S23已经确定了，那么上面的不等式组 可以完全转化为一个有向图，顶点0到顶点i的最短路，就 是Si的解。而当图中存在负权回路时，不等式组无解。至于S23,我们可以用二分法枚举，逐步缩小范围，用迭 代法判断是否存在负权回路(判定可行性)，最终求得S23的最小值。时间复杂度为O(241og2N)o例题2出纳员的雇佣(ACM Tehran 2000)小辖本题用到了差分约束系统的理论，在竞赛中，这样 的系统并不多见，但是却可以巧妙的解决一些难题。这 类题目的模型都不明显，需要一定的思考和转化。做这 类题目，关键是要把题目中的约束条件表示为不等式， 再把不等式转化为图的
7、最短路或最长路模型。例题3贪婪之岛 (ZOJ)问题描述有N (NMOOOOO)张卡片，每张卡片有三种能力，每种 能力的能力值分别为Ai, Bi, Ci.每张卡片可以使用其中 一种能力，且每张卡片只能使用一次。现在需要A张卡片 使用第一种能力，B张卡片使用第二种能力，C张卡片使用 第三种能力(A+B+CS100) o请计算使用哪些卡片，以及 使用卡片的哪项能力，可以使相应的能力值之和最大。例题3贪婪之岛 (ZOJ)今新最优化问题的解法有很多种，比如动态规划，网络流 等，而本题就是一个比较明显的网络流模型。网络流模型中，权的类型众多，有流量，容量，还可 以有费用。在本题中，容量可以作为选取的约束，
8、确保解 的合法性；费用则表示选取的价值，确保解的最优性。因 此，更确切地说，本题是一个最大费用最大流模型。例题3贪婪之岛 (ZOJ)每张卡片i用顶点i表示，另外加三个顶点Pl, P2, P3,表 示三种能力，还有源点S,汇点T。例题3贪婪之岛 (ZOJ)从源点分别向Pl, P2, P3引一条弧，容量分别为A, B, C, 费用为0。例题3贪婪之岛 (ZOJ)2B,034从Pl, P2, P3向顶点i (liN )分别引一条弧，容量为I,费 用分别为Ai, Bi, Cio例题3贪婪之岛 (ZOJ)从顶点i (liN)向汇点引一条弧，容量为I,费用为0。例题3贪婪之岛 (ZOJ)2B.034Lo构
9、图之后，求出从s到T的最大费用最大流，再检查流出Pl, P2, P3的弧，并输岀最优方案。时间复杂度:(X)N太大了，需要进一步优化!例题3贪婪之岛 (ZOJ)优祀同理，对于第二种和第三种能力的选取，也只需保留 其能力值最大的前A+B+C张卡片。这一步可以在线性时间 内解决。这是一个既简单又有效的方法，经过这一步处理，保 留下来的卡片数不会超过3(A+B+C)张，顶点数大大减少， 求解最大费用最大流的时间复杂度降为O(A+B+C)3)。至此，算法已经优化到了一个可以接受的地步，时间 复杂度仅为O (N+(A+B+C)3)。例题3贪婪之岛 (ZOJ)优祀如果还要进一步提高效率，可以用更有效的算法
10、删掉 多余的顶点。不过这样做意义不大，而且也不是本文讨论 的要点。另外，本题还可以转化为二部图模型，用最佳匹配算 法求解。这一步留给读者自己思考。例题3贪婪之岛 (ZOJ)小毎本题建立的是网络流模型。这类模型的算法系数大， 编程复杂度也大，在竞赛中往往作为走投无路时的“候补 算法” O但是，网络流模型的适用性广，一些较复杂，或 者约束较多的问题，网络流模型可以很好地解决，而基于 网络流模型的问题又比较明显，这使得网络流模型有着广 泛的应用。结语问题是千变万化的，如何建立问题的图论模型并没有 通用的准则。前面的几个例子都比较简单，在更复杂的问 题中，有时我们会感到难以建立适当的模型，这时，我们 需要在不改变问题原型本身的性质的前提下，对原型进行 抽象，简化，在此基础上建立合适，有效的模型。有时， 我们建立了问题的一个模型之后，可能会感到难以求解， 这时，我们可能需要对模型进行修改，转化，或者对原型 进行更深入的分析，抽取其中较关键的要素，建立一个易 于求解的模型。这些都需要我们有丰富的经验，灵活的思 维以及良好的创造力。
