试论网络流算法中模型的优化与选择.docx

试论网络流算法中模型的优化与选择

试论网络流算法中模型的优化与选择福建师大附中周成[内容摘要]近年来，在国内信息学竞赛（尤其是国家队选拔赛）、国际信息学竞赛中，多次出现应用网络流算法求解的试题，网络流算法已是信息学奥赛选手必须掌握的算法。本文主要探讨不同网络模型的构造对问题解决的效率的影响，以及如何优化网络模型，提高算法的效率。[关键词]网络流，模型，优化，选择。一、引言网络流算法是一种高效实用的算法，相对于其它图论算法来说，它的模型更加复杂，编程复杂度也更高。但是它综合了图论中的其它一些算法（如最短路径、宽度搜索算法），因而适用范围也更广，经常能够很好地解决一些搜索与动态规划无法解决的非NP问题。 网络流在具体问题中的应用，最具挑战性的部分是模型的构造，它没用现成的模式可以套用，需要我们对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），根据具体的问题发挥我们的创造性。一道问题经常可以建立多种模型，不同的模型对问题的解决效率的影响也是不同的，本文通过实例探讨如何确定适当的模型，提高网络流算法的效率。二、网络流算法时间效率当我们确定问题可以使用最大流算法求解后，就根据常用的Ford-Fulkerson标号法求解；而最小（大）费用最大流问题也可用类似标号法的对偶算法解题。Ford-Fulkerson标号法的运行时间为O（VE2），对偶法求最小费用流的运行时间大约为O（V3E2）。显然，影响网络流算法的时间效率的因素主要是网络中顶点的数目与边的数目。这二个因素之间不是相互独立的，而是相互联系，矛盾而统一的。在构造网络模型中，有时，实现了某个因素的优化，另外一个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，我们在具体问题的解决中，要坚持"全局观"，实现二者的平衡。三、模型的优化与选择(一)减少模型的顶点数与边数，优化模型如果能根据问题的一些特殊性质，减少网络模型中的顶点的数目和边的数目，则可以大大提高算法的效率。例1：最少皇后控制在国际象棋中，皇后能向八个方向攻击（如图1(a)所示，图中黑点格子为皇后的位置，标有K的格子为皇后可攻击到的格子）。现在给定一个M*N（N、M均不大于于50）的棋盘，棋盘上某些格子有障碍。每个皇后被放置在无障碍的格子中，它就控制了这个格子，除此，它可以从它能攻击到的最多8个格子中选一个格子来控制，如图1(b)所示，标号为1的格子被一个皇后所控制。请你编一程序，计算出至少有多少个皇后才能完全控制整个棋盘。  图1(a)图1(b) 输入格式： 输入文件的第一行有两个整数M和N，表示棋盘的行数与列数。接下来M行N列为一个字符矩阵，用'.'号表示空白的格子，'x'表示有障碍的格子。输出格式： 输出文件的第一行仅有一个数S，表示需要皇后的数目。 SampleInput 34 x... x.x. .x.. SampleOuput 5问题分析]如果本问题用简单的搜索来做，由于题目给的棋盘很大，搜索算法很难在短时间内出解。由于一个皇后在棋盘最多只能控制两个格子，因此最少需要的皇后数目的下界为[N*M/2]。要使得皇后数目最少，必定是尽量多的皇后控制两个格子。如果我们在每两个能相互攻击到的格子之间加上一条有向弧，则问题很类似于二分图的最大匹配问题。[模型一]1．将每个非障碍的格子按行优先编号(0~m*n-1)。 2．将上述的每个格子i折成两个格子i'和i''，作为网络模型中的顶点。 3．若格子i可以攻击到格子j且i<j，则在模型中顶点i'到j''之间加上一条有向弧，容量为1。 4．增加一个源点s，从s点向所有顶点i'添上一条弧；增加一个汇点t，从所有顶点j''到t添上一条弧，容量均为1。图1(b)所示的棋盘，对应的模型为：  图2显然，任一解对应于以上模型的一个最大匹配。且最大匹配中，匹配数必定是偶数。因此至少需要的马匹数为M＊N－障碍数－最大匹配数/2。[模型二]如果我们将棋盘涂成黑白相间的格子，则某皇后控制的两个格子一定是一个是黑格，另一个是白格（如图3），不妨设这两个格子中皇后在白格子上。于是，我们将N*M个格子分成两部分白格与黑格。因此我们可以将模型一优化为： 图31．将棋盘中的所有格子分成两个部分，对所有的格子进行编号，每个白格与它能攻击到的黑格之间（障碍除外）添上一条从白格到黑格的弧，构成一个二分图。2．增加一个源点s，从s点向所有非障碍的白格添上一条弧；增加一个汇点t，从所有非障碍的黑格到t添上一条弧。3．设置所有的弧的流量为1。 图1(b)所示的棋盘，对应