acm期末论文2010021050008黄智颖

《acm期末论文2010021050008黄智颖》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ACM期末论文2010021050008黄智颖试论网络流算法中模型的优化与选择【内容摘要】近年来，在国内信息学竞赛（尤其是国家队选拔赛）、国际信息学竞赛中，多次出现应用网络流算法求解的试题，网络流算法已是信息学奥赛选手必须掌握的算法。本文主要探讨不同网络模型的构造对问题解决的效率的影响，以及如何优化网络模型，提高算法的效率。【英文摘要】Inrecentyears,domesticinformaticscontest(especiallyinnationaltrials),internationalinformaticscompetition

2、,beenrepeatedinapplicationofnetworkflowalgorithmforthepapers,thenetworkflowalgorithmisalreadyorsaycontestantsmustmasterbioinformaticsmethod.Thispapermainlydiscussesthestructureofdifferentnetworkmodelforproblemsolving,andtheinfluenceofefficiencytooptimizenetworkmodel,improv

3、etheefficiencyofthealgorithm.【关键词】网络流，模型，优化，选择。【正文】一﹑引言网络流算法是一种高效实用的算法，它综合了图论中的一些经典算法（如最短路径、宽度搜索算法），经常能够很好地解决一些搜索与动态规划无法解决的非NP问题。运用网络流解决具体问题没用现成的模式可以套用，需要根据网络流的性质发挥创造性探索建立多种模型，通过分析、选择、优化、确定适当的模型，提高网络流算法的效率。在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流等等。5

4、0年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”是网络应用的重要组成部分。在现代的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题是很常见的。二﹑网络流的概念网络流(flow，或简称为流)，是指定义在边集E上一个函数f={f(vi，vj)}，并称f(vi，vj)为边(vi，vj)上的流量（简记为fij）。二、网络流算法时间效率　　当我们确定问题可以使用最大流算法求解后，就根据常用ford-fulkerson标号法求解；而最小（大）费用最大流问题也可用类似标号法的对偶算法解题。ford-fulkerson标号

5、法的运行时间为o（ve2），对偶法求最小费用流的运行时间大约为o（v3e2）。　　显然，影响网络流算法的时间效率的因素主要是网络中顶点的数目与边的数目。这二个因素之间不是相互独立的，而是相互联系，矛盾而统一的。在构造网络模型中，有时，实现了某个因素的优化，另外一个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，我们在具体问题的解决中，要坚持“全局观”，实现二者的平衡。三、模型的优化与选择(一)减少模型的顶点数与边数，优化模型如果能根据问题的一些特殊性质，减少网络模型中的顶点的数目和边的数目，则可以大大提高算法的

6、效率。例1：最少皇后控制　　在国际象棋中，皇后能向八个方向攻击（如图1(a)所示，图中黑点格子为皇后的位置，标有K的格子为皇后可攻击到的格子）。现在给定一个M*N（N、M均不大于于50）的棋盘，棋盘上某些格子有障碍。每个皇后被放置在无障碍的格子中，它就控制了这个格子，除此，它可以从它能攻击到的最多8个格子中选一个格子来控制，如图1(b)所示，标号为1的格子被一个皇后所控制。请你编一程序，计算出至少有多少个皇后才能完全控制整个棋盘。图1(a)图1(b)　　　[问题分析]　　由于题目给的棋盘很大，简单的搜索很难在短时间内出解。同时注意到，一个皇

7、后在棋盘最多只能控制两个格子，因此最少需要的皇后数目的下界为[N*M/2]。要使得皇后数目最少，必定是尽量多的皇后控制两个格子。如果在每两个能相互攻击到的格子之间加上一条有向弧，则问题就转化成类似于二分图的最大匹配问题。[模型一]　1．将每个非障碍的格子按行优先编号(0~m*n-1)。　2．将上述的每个格子i折成两个格子i'和i''，作为网络模型中的顶点。　3．若格子i可以攻击到格子j且i

8、上一条弧，容量均为1。图1(b)所示的棋盘，对应的模型为图2。　　　　图2　　显然，任一解对应于以上模型的一个最大匹配。且最大匹配中，匹配数必定是偶数。因此至少需要的马匹数为M＊