求解拟阵约束下下模函数最小集合覆盖的贪婪算法及其性能保证

发布时间：2017-11-07 16:28

  本文关键词：求解拟阵约束下下模函数最小集合覆盖的贪婪算法及其性能保证

  更多相关文章： 下模函数 拟阵约束 背包约束 贪婪算法 性能保证

【摘要】：组合优化问题是在一些约束条件下给定的有限集合中,根据某一目标找出一个最符合要求的最优解的这么一类数学规划问题,也称为组合规划。组合优化都是在由有限个方案构成的集合中,选择能够使目标函数达到最优解的最优子集。组合优化问题的发展在生产生活等各个领域有着广泛的应用,例如在商品生产,交通运输航线问题,装箱问题,工作指派问题等。等到拟阵理论进入到组合优化问题的研究领域中,得到了很多理论成果,比如推销问题,最短路问题和最大支撑树问题。下模函数作为一类特殊的实值函数,并且是被定义在幂集上。下模函数的变量是离散的不是连续的。由于这种特殊的性质使得下模函数在求解最优化问题中起到了重要作用。在组合优化中,下模函数最大值问题的求解被当做一个中心问题,我们可以把很多组合优化问题最优值的求解转化成求解下模函数的最大值问题,这使得组合优化问题都可以认为是求解下模函数的最大值问题,归纳出很多重要问题比如最大割、最大熵采样、最大设施选址和集合覆盖的问题。因此我们研究下模函数的最值问题就有非常特殊的理论价值和实践应用价值。然而,求解下模函数是一个NP-难问题,人们不断地寻找有效的多项式算法。本文主要介绍了如何求解下模函数的最优值理论和如何在求解下模函数最大值问题当中应用贪婪算法。我们主要给出一个近似贪婪算法,并将这个贪婪算法运用在被多重拟阵约束下任意非负的下模函数最大值问题。最后介绍了下模函数的最值被k维背包约束下的求解问题。并把各种算法进行了比较全面的理论分析进而得出其性能保证。本文一共分为五章,第一章首先介绍了最优化理论问题的起源与发展和贪婪算法,以及针对不同的算法如何分析它们的性能保证,接着给出了这篇文章研究的背景,最后介绍了这篇文章的任务以及要解决什么样的问题。第二章综述了下模函数的概念及相关定理,以及贪婪算法解决最小集合的覆盖问题,并给出了此贪婪算法的性能保证。第三章主要详细介绍如何用近似贪婪算法和局部搜索程序对于下模函数最大值被k个拟阵约束下的求解问题,并证明了贪婪算法的近似度为()111 k2ke??+++?÷è?第四章主要介绍了近似算法对于下模函数最大值被k维背包约束下的求解问题,并且证明此算法可以得到一个12 n?e?-?÷è?的近似解。第五章全面的对论文进行了总结、展望。
【学位授予单位】：兰州交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O224

【相似文献】

中国期刊全文数据库 前10条

1 陈洪;蔡佳;张玉成;;多分类贪婪算法的一致性[J];湖北大学学报(自然科学版);2005年04期

2 杨洁;;基于贪婪算法的卫星区域观测摆角方案选择方法[J];广西科学院学报;2006年02期

3 高静宇;马文丽;孙汉顺;孙立哲;郑文岭;;一种新的蛋白质结构字母序列优化算法[J];生物信息学;2010年03期

4 冯光毅;;就背包和部件加工问题浅论贪婪算法的运用及优化方案[J];计算机光盘软件与应用;2013年24期

5 徐立新,张玉忠;集合核约束分划的贪婪算法分析[J];系统工程理论与实践;1999年04期

6 张岩;;单调多边形三角剖分贪婪算法的分析与实现[J];牡丹江师范学院学报(自然科学版);2002年04期

7 田仲;李加祥;;基于贪婪算法的影响网络行动方案优选[J];指挥控制与仿真;2013年03期

8 肖华勇,田铮,师义民;资源公平分配的一种贪婪算法[J];运筹与管理;2000年02期

9 贾欣鑫;罗亮;郭丽峰;何尚录;;求解组合拍卖问题的一种贪婪算法[J];温州大学学报(自然科学版);2009年03期

10 周斌;程慧;杨立志;裴国庆;;基于贪婪算法的符号网络中社团结构快速发现算法[J];大众科技;2009年12期

中国重要会议论文全文数据库 前2条

1 陈华;管乐乐;宗鹏安;黄星星;;TSP问题的一个新算法[A];全国第20届计算机技术与应用学术会议（CACIS·2009）暨全国第1届安全关键技术与应用学术会议论文集（上册）[C];2009年

2 张兴辉;冯明静;;谈智能灭火救援辅助指挥系统的设计与思考[A];2003年湖北省灭火救援学术研讨会论文集[C];2003年

中国博士学位论文全文数据库 前1条

1 李海锋;压缩感知恢复算法及应用研究[D];华南理工大学;2014年

中国硕士学位论文全文数据库 前10条

1 曹金;基于压缩感知的信道估计关键技术研究[D];电子科技大学;2014年

2 张立群;求解拟阵约束下下模函数最小集合覆盖的贪婪算法及其性能保证[D];兰州交通大学;2015年

3 任文轩;运用贪婪算法构建物流网络的方法与应用研究[D];中国科学技术大学;2011年

4 王海洋;基于SVM的分段贪婪算法研究[D];西安科技大学;2009年

5 孙魁伟;基于贪婪算法的自动排课系统设计与实现[D];大连理工大学;2013年

6 孟庆敏;关于几种光滑函数类的最佳逼近[D];华北电力大学;2014年

7 孙剑阳;复方药物筛选前期的模型及算法[D];山东大学;2014年

8 袁毅;侧围焊接工位焊点分配及路径规划的研究[D];湖南大学;2013年

9 冯小军;社会网络环境下一种基于潜力的影响最大化算法[D];复旦大学;2010年

10 叶环球;限秩最大子集问题[D];浙江大学;2001年

，

本文编号：1153209