网络流算法的研究与应用分析

《网络流算法的研究与应用分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、单位代码：10293密级：公开硕士学位论文论文题目：网络流算法的研究与应用分析学号1011081806姓名董方导师赵礼峰学科专业应用数学研究方向数值方法与应用申请学位类别理学硕士论文提交日期二零一四年四月万方数据ResearchandAppliedanalysisonNetworkFlowAlgorithmThesisSubmittedtoNanjingUniversityofPostsandTelecommunicationsfortheDegreeofMasterofScienceByDongFangS

2、upervisor:Prof.ZhaoLifengFebruary2014万方数据南京邮电大学学位论文原创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本人学位论文及涉及相关资料若有不实，愿意承担一切相关的法律责任。研究生签名：____

3、_________日期：____________南京邮电大学学位论文使用授权声明本人授权南京邮电大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档；允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索；可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质论文的内容相一致。论文的公布（包括刊登）授权南京邮电大学研究生院办理。涉密学位论文在解密后适用本授权书。研究生签名：____________导师签名：____________日期：_________

4、____万方数据摘要网络流问题是网络最优化问题中至关重要的部分，它在生活和各个科学领域的应用也愈加广泛。随着计算机科学技术的进步和人们对其深入的研究，形成了较完善的理论体系，从而建立了一系列有效算法。本文针对增广链的选取具有不稳定性而得不到理想的最大流问题进行改进，并对最大流问题的应用进行研究。主要创新工作是：（1）介绍了几种求最大流问题的经典算法，并通过实例对这些经典算法进行优缺点和局限性的分析，广泛吸取标号算法的最新成果并引进断链的基本概念，提出了一种基于断链求解网络最大流的新标号算法。同时通过实例和仿

5、真实验进行了验证，验证了该算法具有可行性与高效性。（2）针对现有算法没有给出明确的选择增广链路径的方法，造成计算复杂等问题，于是对原有算法的一些缺点进行改进，又应用分层、度差、容差等概念，提出了一种基于度差求解网络图最大流的新算法。通过实例和仿真实验验证该算法具有明显的稳定性与有效性。（3）由于上述提出的改进的新标号算法，它不但可以解决最大流问题同时也为求解最短路问题提供了一种方法，于是提出了一种基于新标号算法求解小规模网络最短路问题的算法。通过实例验证该算法的简单可行性。（4）给出最大流算法在通信网络中的

6、应用以及它的推广应用。关键词:最大流，增广链，最短路，标号算法，剩余容量，顶点度，网络编码I万方数据AbstractThemaximumflowproblemplaysanimportantroleinthenetworkoptimizationproblem.Itiswidelyappliedinlifeandeachfieldofscience.Withtheboomingdevelopmentofcomputertechnology,peopleresearchinmaximumflowproblem

7、deeply,scholarssetupmuchperfecttheoreticalsystemandseriesofeffectivealgorithms.Duetotheimproperselectionorderofaugmentedchaincouldnotobtaintheidealmaximumflowanddosomeresearchonthemaximumflowproblem,thepaperdoesthefollowingsomemaininnovationworks：Firstly,t

8、hepaperintroducessomeclassicalgorithm,thenitanalyzestheiradvantagesanddisadvantages,verifiestheirslimitationsbyexamples.Inaddition,usingtheconceptofdisconnectedchainsandabsorbingthelatestachievements,thepaper