ACM期末论文2010021050008黄智颖.doc

ACM期末论文2010021050008黄智颖试论网络流算法中模型的优化与选择 【内容摘要】 近年来，在国内信息学竞赛（尤其是国家队选拔赛）、国际信息学竞赛中，多次出现应用网络流算法求解的试题，网络流算法已是信息学奥赛选手必须掌握的算法。本文主要探讨不同网络模型的构造对问题解决的效率的影响，以及如何优化网络模型，提高算法的效率。【英文摘要】In recent years, domestic informatics contest (especially in national trials), international informatics competition, been repeated in application of network flow algorithm for the papers, the network flow algorithm is already orsay contestants must master bioinformatics method. This paper mainly discusses the structure of different network model for problem solving, and the influence of efficiency to optimize network model, improve the efficiency of the algorithm.【关键词】 网络流，模型，优化，选择。【正文】一引言网络流算法是一种高效实用的算法，它综合了图论中的一些经典算法（如最短路径、宽度搜索算法），经常能够很好地解决一些搜索与动态规划无法解决的非NP问题。运用网络流解决具体问题没用现成的模式可以套用，需要根据网络流的性质发挥创造性探索建立多种模型，通过分析、选择、优化、确定适当的模型，提高网络流算法的效率。在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”是网络应用的重要组成部分。在现代的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题是很常见的。二网络流的概念网络流(flow，或简称为流)，是指定义在边集E上一个函数f=f(vi，vj)，并称f(vi，vj)为边(vi，vj)上的流量（简记为fij）。二、网络流算法时间效率当我们确定问题可以使用最大流算法求解后，就根据常用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)问题分析由于题目给的棋盘很大，简单的搜索很难在短时间内出解。同时注意到，一个皇后在棋盘最多只能控制两个格子，因此最少需要的皇后数目的下界为N*M/2。要使得皇后数目最少，必定是尽量多的皇后控制两个格子。如果在每两个能相互攻击到的格子之间加上一条有向弧，则问题就转化成类似于二分图的最大匹配问题。模型一1 将每个非障碍的格子按行优先编号(0m*n-1)。2 将上述的每个格子i折成两个格子i和i，作为网络模型中的顶点。3 若格子i可以攻击到格子j且i v(x, y, 1),c1 = MaxInt,w1 = 0。u e2 = v(x, y, 0) - v(x, y, 1)，c2 = 1，w2 = -1（这里要求(x, y)必须是岩石）u e3 = v(x, y, 1) - v(x, y, 0)，c3 = MaxInt,w3 = 0.其中x=x+1 y=y 或x=x y=y+1,1 = x = MaxX，1 = y v(x, y, 1),c1 = 1,w1 = -1。u e2 = v(x, y, 1) - v(x, y, 0)，c2 = 1，w2 = 0（岩石点(x, y)可到达岩石点(x,y)）。u e3 = s - v(x, y, 0)，c3 = 1,w3 = 0。u e4 = v(x, y, 1)-t，c4 = 1,w4 = 0。u e5=S-t,c5=MaxInt,w5=0。由于每个石块被折成两个点，且容量为1，就保证了每个石块只被取走一次，同时取走一块石块就得到-1的费用。因此对以上模型，我们求流量为NumberOfVehicles的最小费用流，就可得到解。两种模型的比较1.模型一以网格为顶点，模型二以岩石为顶点，因此在顶点个数上模型二明显优于模型一，对于一些岩石比较稀疏，而网格又比较大的数据，模型二的效率要比模型一来得高。且只要岩石的个数不超过一定数目，模型二可以处理P，Q很大的数据，而模型一却不行。2模型一中边的数目最多为3*P*Q，而模型二中边的数目最坏情况下大约为p*q*(p+1)*(q+1)/4-p*q。因此在这个问题中，若对于一些岩石比较密集且网格又比较大的数据，模型二的边数将大大超过模型一，从而使得时间效率大大低于模型一。下面是网格中都是岩石的情况比较（PIII700/128M ，BP7.0保护模式）：NumberOfVehicles10模型一模型二P，Q100.05s0.11sP，Q200.11s6.87sP，Q300.49s52.58sP，Q401.37s内存溢出P，Q504.67s内存溢出P，Q608.08s内存溢出P，Q60内存溢出内存溢出通过以上数据，可知对于P，Q不超过60的情况，模型一都能在10秒内出解。而模型二则对于P、Q30的最坏情况下速度就很慢了，且P、Q超过30后就出现内存溢出情况，而无法解决。因此，对于本题，以上两种模型各有利弊，我们可根据测试数据中岩石稀疏程度来决定建立什么样的模型。若岩石比较稀疏，则可以考虑用建立如模型二的网络模型；若岩石比较密集则建立模型一所示网络模型。然后，再应用求最小费用最大流算法求解。对于P，Q60，且岩石比较多情况下，两种模型的网络流算法都无法求解。在实际的应用中问题经常都只要求近似解，此时还可用综合一些其它算法来求解。四、总结综上所述，网络流算法中模型的优化是提高网络流算法效率的根本。我们要根据实际问题，从减少顶点及边的角度综合考虑如何对模型进行优化，选择适当的模型，以提高算法的效率。对于有些题目，解题的各种模型各有优劣时，还可通过程序自动分析测试数据，以决定何种情况下采用何种模型，充分发挥各种模型的优点，以达到优化程序效率的目的。【参考文献】1潘金贵、顾铁成等，现代计算机常用数据结构和算法，南京大学出版社，1994。 2吴文虎王建德编著，实用算法的分析与程序设计，电子工业出版社，1998。另：关于皇后控制问题的解题报告1.问题描述 ：在一个nn个方格组成的棋盘上的任一方格中放置一个皇后，该皇后可以控制他所在的行，列以及对角线上的所有方格。对于给定的自然数n，在nn个方格组成的棋盘上最少要放置多少个皇后才能控制棋盘上的所有方格，且放置的皇后互不攻击？2.程序源代码#include #include #include #include #include ifstream infile(input.txt);ofstream outfile(output.txt);const unsigned long maxshort=65536L;const unsigned long multiplier=1194211693L;const unsigned long adder=12345L;/随机数类class RandomNumberpublic:/构造函数，缺省值0表示由系统自动产生种子RandomNumber(unsigned long s=0);/产生0:n-1之间的随机整数unsigned short Random(unsigned long n);/产生0,1)之间的随机实数double fRandom(void);private:/当前种子unsigned long randSeed;/产生种子RandomNumber:RandomNumber(unsigned long s)if(s=0)randSeed=time(0); /用系统时间产生种子elserandSeed=s; /由用户提供种子/产生0:n-1之间的随机整数unsigned short RandomNumber:Random(unsigned long n)randSeed=multiplier*randSeed+adder;return (unsigned short)(randSeed16)%n);/产生0,1)之间的随机实数double RandomNumber:fRandom(void)return Random(maxshort)/double(maxshort);/2维数组类template void Make2DArray(T* &x, int rows, int cols) /创建行指针 x = new T* rows; /为每行分配空间 for(int j = 0; j rows; j+) xj = new Tcols; template void Delete2DArray(T* &x, int rows) /释放为每行所分配的空间 for(int j = 0; j 0)for(int j=1;j0)&(abs(k-j)=abs(xj-xk)|xj=xk)return false;return true;bool Queen:ctrl(int m)/测试皇后是否已控制棋盘m*mint i,j,u,v,count=0;for(i=1;i=m;i+)for(j=1;j=m;j+) zij=0;/初始置0for(i=1;i0) /i行有皇后时for(j=1;j=1&v=1;u-,v-) zuv=1;/(i,xi)左上对角线所有元素都控制for(u=i,v=xi;u=1;u+,v-) zuv=1;/(i,xi)左下对角线所有元素都控制for(u=i,v=xi;u=1&v=m;u-,v+) zuv=1;/(i,xi)右上对角线所有元素都控制for(u=i,v=xi;u=m&v=m;u+,v+) zuv=1;/(i,xi)右下对角线所有元素都控制for(i=1;i=m;i+)for(j=1;jn)/输出一个解/for(int i=1;i=n;i+)/ai=xi;/return true;if(ctrl(n)&(c=cmin)a0=c;for(int i=1;i=n;i+)ai=xi;return true;else return false;elsefor(int i=0;i0) c+;if(c0) c-;return false;bool Queen:ddBacktrack(int t)/迭代法解n后问题的回溯法,改为布尔型,有一个解输出truext=-1;int k=t;bool *jc =new bool n+1;for(int i=1;it-1)xk+=1;/可以取0while(ccmin)&(xk=n)&!(Place(k) xk+=1;if(xk0)&jck) c+;jck=false;if(k=n)/输出一个解/for(int i=1;i=n;i+)/ai=xi;/return true;if(ctrl(n)&(c=cmin)a0=c;for(int i=1;i0&!jck) c-;jck=true;k-;/回溯return false;int Queen:QueensLV(int stopVegas)/随机放置n个皇后的拉斯维加斯算法/RandomNumber rnd;/随机数产生器定义在类里,随机效果更好int k=1;int count;c=0;while(k=stopVegas)count=0;ycount+=0