两类组合最优化问题的探讨

发布时间：2017-06-26 19:17

  本文关键词：两类组合最优化问题的探讨，由笔耕文化传播整理发布。

【摘要】：中国邮递员问题是一个重要的组合最优化问题,涉及到在网络中如何在特殊的限定下最优地选取路线的问题,该问题由中国数学家管梅谷1960年首次提出。到今天,国内外对中国邮递员问题及其相关问题的研究已有50多年,得到了大量丰富而又深刻的结果。在计算复杂性领域,中国邮递员问题是一个P类问题,即存在多项式时间算法能得到该问题的最优解。本文首先对中国邮递员问题的结构予以了清晰的描述,通过巧oin的概念引入,给出了求解中国邮递员问题的各种算法介绍；其次,我们研究了无向赋权图上的最大权圈装箱问题,并从算法复杂性角度给予了中国邮递员问题与最大权圈装箱问题的等价性的完整证明；最后,基于我们得到的关于中国邮递员问题与最大权圈装箱问题的相关结果,我们引入了所谓的最大类欧拉回路概念,并作了一些探讨,指明了未来研究的方向。 平行机排序是一个经典的组合最优化问题,带拒绝费用的平行机排序问题是经典平行机排序问题的一个推广,该问题是NP-难的,除非P=NP,否则我们不可能找到多项式时间算法求得该问题的最优解。在本文中,我们给出了带拒绝费用的平行机排序问题的一个2-近似强多项式时间算法,并且给出了实例来说明我们给出的算法是紧的,即算法不可能取得比2更好的近似比。同时,我们也给出了该问题的一个多项式时间近似方案,且得到了该方案的时间复杂度为O
【关键词】：中国邮递员 圈装箱 排序 多项式时间算法 近似算法 PTAS
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：F618;O224
【目录】：

• 摘要6-7
• Abstract7-11
• 第一章 绪论11-15
• §1.1 中国邮递员问题与最大权圈装箱问题11-12
• §1.2 带拒绝费用的平行机排序问题12-13
• §1.3 文章内容结构13-15
• 第二章 预备知识15-26
• §2.1 组合最优化简介15-17
• §2.2 图论基础17-20
• §2.3 排序相关术语和记号20-22
• §2.4 算法和计算复杂性22-26
• 第三章 中国邮递员问题与最大权圈装箱问题26-39
• §3.1 无向赋权图上的中国邮递员问题算法27-29
• §3.1.1：奇偶点图上作业算法27-28
• §3.1.2：最小权完美匹配算法28
• §3.1.3：T-join定义与中国邮递员问题28-29
• §3.2 无向图上中国邮递员问题与最大权圈装箱问题29-37
• §3.3 最大类欧拉回路问题37-38
• §3.4 小结及其未来的研究方向38-39
• 第四章 带拒绝费用的平行机排序问题39-61
• §4.1 带拒绝费用的平行机排序问题的2-近似强多项式时间算法40-47
• §4.2 带拒绝费用平行机排序问题的近似排序方案47-60
• §4.2.1：带拒绝费用的平行机排序问题的辅助实例47-52
• §4.2.2：辅助实例和原始实例52-58
• §4.2.3：近似排序方案：问题P|∑_(Jj∈R)e_j≤B|C_(max)的一个PTAS58-60
• §4.3 小结及未来研究的方向60-61
• 第五章 结论61-62
• 致谢62-63
• 参考文献63-66
• 附录A 攻读硕士期间发表论文目录66

【参考文献】

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

1 越民义,韩继业;n个零件在m台机床上的加工顺序问题(Ⅰ)[J];中国科学;1975年05期

2 管梅谷;奇偶点图上作业法[J];数学学报;1960年03期

3 管梅谷;中国投递员问题综述[J];数学研究与评论;1984年01期

4 张峰;唐国春;;工件可拒绝排序问题的研究[J];同济大学学报(自然科学版);2006年01期

  本文关键词：两类组合最优化问题的探讨，，由笔耕文化传播整理发布。

本文编号：487332