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

《试论网络流算法中模型的优化与选择 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、试论网络流算法中模型的优化与选择[试论网络流算法中模型的优化与选择]试论网络流算法中模型的优化与选择福建师大附中周成[内容摘要]近年来，在国内信息学竞赛（尤其是国家队选拔赛）、国际信息学竞赛中，多次出现应用网络流算法求解的试题，网络流算法已是信息学奥赛选手必须掌握的算法，试论网络流算法中模型的优化与选择。本文主要探讨不同网络模型的构造对问题解决的效率的影响，以及如何优化网络模型，提高算法的效率。[关键词]网络流，模型，优化，选择。一、引言网络流算法是一种高效实用的算法，相对于其它图论算法来说，它的模型更加复杂，编程复杂度也更高。但是它综合了图论中

2、的其它一些算法（如最短路径、宽度搜索算法），因而适用范围也更广，经常能够很好地解决一些搜索与动态规划无法解决的非NP问题。网络流在具体问题中的应用，最具挑战性的部分是模型的构造，它没用现成的模式可以套用，需要我们对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），根据具体的问题发挥我们的创造性。一道问题经常可以建立多种模型，不同的模型对问题的解决效率的影响也是不同的，本文通过实例探讨如何确定适当的模型，提高网络流算法的效率。二、网络流算法时间效率当我们确定问题可以使用最大流算法求解后，就根据常用的Ford-Fulkerson标号

3、法求解；而最小（大）费用最大流问题也可用类似标号法的对偶算法解题，教育论文《试论网络流算法中模型的优化与选择》(..)。Ford-Fulkerson标号法的运行时间为O（VE2），对偶法求最小费用流的运行时间大约为O（V3E2）。显然，影响网络流算法的时间效率的因素主要是网络中顶点的数目与边的数目。这二个因素之间不是相互独立的，而是相互联系，矛盾而统一的。在构造网络模型中，有时，实现了某个因素的优化，另外一个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，我们在具体问题的解决中，要坚持"全局观"，实现二者的平衡。三、

4、模型的优化与选择(一)减少模型的顶点数与边数，优化模型如果能根据问题的一些特殊性质，减少网络模型中的顶点的数目和边的数目，则可以大大提高算法的效率。例1：最少皇后控制在国际象棋中，皇后能向八个方向攻击（如图1(a)所示，图中黑点格子为皇后的位置，标有K的格子为皇后可攻击到的格子）。现在给定一个M*N（N、M均不大于于50）的棋盘，棋盘上某些格子有障碍。每个皇后被放置在无障碍的格子中，它就控制了这个格子，除此，它可以从它能攻击到的最多8个格子中选一个格子来控制，如图1(b)所示，标号为1的格子被一个皇后所控制。请你编一程序，计算出至少有多少个皇后才

5、能完全控制整个棋盘。图1(a)图1(b)输入格式：输入文件的第一行有两个整数M和N，表示棋盘的行数与列数。接下来M行N列为一个字符矩阵，用'.'号表示空白的格子，'x'表示有障碍的格子。输出格式：输出文件的第一行仅有一个数S，表示需要皇后的数目。SampleInput34x...x.x..x..SampleOuput5问题分析]如果本问题用简单的搜索来做，由于题目给的棋盘很大，搜索算法很难在短时间内出解。由于一个皇后在棋盘最多只能控制两个格子，因此最少需要的皇后数目的下界为[N*[1][2][3][4]试论网络流算法中模型的优化与选择2　　第2篇

6、WTO与企业财务管理　　〖预览〗一、入世后财务管理环境的变迁对财务管理的影响　　任何企业的财务活动和财务管理都是在一定环境和条件下展开的，人世后企业财务管理环境的变迁必定会对企业财务管理产生极大的影响，主要表现在以下几个方面：　　（一）金融市场变化的影响。加入WTO之后，根据《服务贸易总协定》的基本要求及与有关WTO成员国达成的双边协议，我国将逐步放松外资金融机构准人的范围和区域限制。越来越多的外资金融机构进入我国，必将使我国金融市场发生全面而深远的变化，呈现出一些新的特征，从而对企业筹资投资产生极大的影响。第一，金融市场规模的扩大、资金供给的增

7、加和金融工具的不断创新，为我国企业筹资、投资和规避风险提供了多种可供选择的组合方式。第二，金融创新丰富了金融工具品种，拓展了金融服务范围，但同时也派生出利率风险、汇率风险、表外风险等新的风险，使金融风险进一步加大，规避风险将成为人世后企业财务管理面临的最重要课题之一。第三，国内外金融市场竞争的加剧，促使我国金融机构建立现代企业制度的步伐进一步加快，金融机构自律性管理将进一步加强，国家对金融市场的监管也将进一步规范，必将便金融市场配置资源的功能得以更加有效地发挥。这样，无论什么性质的企业在金融市场都将处于公平竞争的地位，只能凭借其良好的经济效益、看

8、好的市场前景与持续高速的增长而获得资金，况且企业筹资有时还要……试论网络流算法中模型的优化与选择3　　第3篇浅谈利润管理的合理性　　〖预