几类网络优化和改进问题的算法研究

《几类网络优化和改进问题的算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、致谢转眼已临近毕业，回首三年研究生学习生涯，我有许多感触。在这三年里，我作为一名研究生，聆听老师的教诲，不断学习和努力。是老师和同学赋予了我这段时间在学习和生活上的成长。值此论文完成之际，特向你们表达我最诚挚的感谢和祝福。在这里我要特别感谢我的导师王勤教授，是您将我带入一个更高的层次，让我明白学无止境的道理。在本科阶段，您教授我运筹学的知识，让我感受到了运筹学和优化思想的广泛应用。而在研究生阶段，是您指引我学习图论与最优化理论的相关知识，带我进入算法理论的更深领域。您是我学习上的良师和生活中的益友，感谢您对我这么多年的关心和帮助，您的教诲学生永远牢记于心,

2、并将使我终身受益。我要衷心感谢中国计量学院理学院及研究生部对我的培养。感谢我的所有授课老师们，正是你们的悉心教授，学生们才能学到更多的知识，老师们不仅传授知识给我们，你们的言传身教，更让我学到了为人做事的道理，你们的师者风范始终是我学习的榜样。我还要感谢和我一起同窗的那些同学们，你们陪我一起度过这美好的岁月，有欢歌，笑语，是友情，亦是亲情。感谢一路有你们，感谢你们学习和生活上对我的帮助。最后，我要深深地感谢我的父母，感谢我的家人，感谢你们对我的付出，对我研究生期间物质和精神上的支持，是你们给了我人世间最无私的爱和最可贵的亲情。丁哲衡2013年6月几类网络优

3、化和改进问题的算法研究摘要：网络优化问题以及网络改进问题是图论和组合最优化领域的一个重要的研究方向。这些问题在现实生活中有广泛的应用，研究其具有重要的意义。网络优化问题主要研究如何在一定的约束条件下寻求问题的最优解，而网络改进问题又称为网络优化问题的反问题，它研究如何通过修改问题模型的参数，使得在修改后的参数下，网络能满足问题的某些特定的约束或要求，并且总的修改费用最少。本文对k-supplier问题、l¥模下一类通信网络的改进问题以及圈秩数固定的最小连通生成子图的部分改进问题进行了研究，并分别得到了近似算法及多项式时间算法：第一，研究了k-supplie

4、r问题，得到了性能比为3的贪婪近似算法。k-supplier问题是一个NP-困难问题,且其最优近似性能比为3。本文对k-supplier问题通过使用贪婪技术，从客户的角度出发，不断寻找最近的供应商，通过迭代调整，得到了该问题的3-近似的多项式时间贪婪近似算法，并通过实例验证了该算法的有效性。该算法相对于其他方法具有实现简单，计算速度快，结果精度较高等优点。第二，研究了l¥模下一类通信网络的改进问题，该问题具有一定的应用背景。本文对一类特定的通信网络优化问题，运用弱控制集的定义，首先基于最小生成树算法，得到了求解该通信网络优化问题的复杂性为2O(V)的多项式

5、时间算法，并在此基础上得到了其改进问题的模型。通过一类Newton型算法进O(V(logE+V))的多项式时间算法。2行求解，得到了其改进问题的复杂性为第三，研究了圈秩数固定的最小连通生成子图的部分改进问题。对于给定子图是圈秩数为k的连通子图的情况，首先收缩该子图，得到收缩之后图的最小生成树。在此生成树的基础上进行扩展，最后得到部分改进问题的多项式时间算法；对于给定子图为生成树的情况，通过逐步减少给定子图边的权重，构造出一个包含给定子图的圈秩数为k的连通子图，并证明了该连通子图为最小连通生成子图，从而得到了该类情形下部分改进问题的多项式时间算法。关键词：k

6、-supplier问题；网络优化；圈秩数；生成子图；多项式时间算法分类号：O221.7IResearchontheAlgorithmsofSeveralNetwork OptimizationandImprovementProblemsAbstract:Networkoptimizationandimprovementproblemisanimportantresearchdirectioninthefieldofgraphtheoryandcombinatorialoptimization.Manyapplicationsoftheseproblemsh

7、avebeenfoundintherealworld.Networkoptimizationproblemistofindanoptimalsolutionoftheproblemundersomeconstraints,whilenetworkimprovementproblemisalsocalledthereverseproblemofnetworkoptimizationproblem,itistomodifytheparametersofanoptimizationproblem,suchthatunderthenewparameters,the

8、networkcansatisfysomecertaindesir