资源描述:
《容差修正网络最大流算法研究》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、AbstractNetworkoptimizationisanimportantbranchofoptimization,whichisalsothecross-disciplineofcombinationofgraphtheorywithoptimizationtheory.Itmainlystudiesthenetworkalgorithmwithmathematicalmodelssearchedwithgraphtheoryalgorithm.Theissueofnetworkmaximumflowistostudythemaximumtransport
2、capacityofaflowbetweenthesourceandthesinkinacapacity-limitednetwork.Maximumflowproblemisacloseconnectionbetweengraphtheoryandoperationsresearch,inparticularwiththelinearprogramming,whichhasopenedupnewwaysingraphtheoryapplication.Thethesisstartswiththenetworkmaximumflowalgorithm,whichi
3、ncludesfivechapters・Inthefirstchapter,weintroducethebasicissuesofnetworkoptimizationatfirst,togetherwiththehistoryanddevelopmentofnetworkmaximumflowalgorithm.Laterwelearnthedevelopmentofthealgorithmsclassification,andwefinallyanalyzethewiderangeofapplicationsanddevelopmentprospectsfor
4、networkmaximumflowalgorithm.Thesecondchapterisanintroductionoftheinvolvedcommonconceptofnetworkoptimizationandthemainstreamalgorithmsofthenetworkmaximumflow.Inthethirdchapter,wefirstgivetherelateddefinitionsandtheoremsofminimumcut,latergivethesolutiontodeterminethemaximumflowandminimu
5、mcutofthenetwork,wherethetoleranceofthenetworkisnon-positiveornon-toleranceaswellasstructurebalanced,andwealsogivethetheoremofit.Intheforthchapter,wefirstbriefontheprocessoftheimprovementofnetworkmaximumflow2Falgorithmbyaddingtolerancedeterminationintoit,laterwegivethemethodsofdatapre
6、processing,stepsaswellastheflowchartalgorithmofthenewalgorithm・Inthefifthchapter,wegiveafewexamplesoftheimproved2Fmaximumflowalgorithm,alsomakeacomparisonofefficiencywiththeoriginal2Falgorithm,whichconfirmsthattheimprovedalgorithmhasachievedgoodeffect.Also,wewidelydiscusstheapplicatio
7、noftheimprovedalgorithm.KeywordsMaximumflowalgorithm;Feasibleflow;Cut;2Falgorithm;Augmentingchain;Tolerancehi摘要IAbstractII第1章绪论11.1网络最优化算法11.2最大流算法的研究历史和现状21.2.1分类算法研究进展31.2.1.1组合算法31.2.1.2线性规划算法4121.3其他算法41.2.2算法时间复杂度的进展51.2.3广泛的应用领域61.3网络最大流算法的发展前景81.4选题的意义91.5所做的工作和论文结构9第2章网络基础知识和最
8、大流典型算