布局问题NP难性质的传递路线研究

发布时间：2017-07-05 17:07

  本文关键词：布局问题NP难性质的传递路线研究

  更多相关文章： 布局问题 复杂性 NP难 NP完全

【摘要】：布局问题作为研究NP难度问题的典型代表,在实践领域中应用较为广泛。实际生产中,其表现出来的NP难性质的求解性,已经成为技术发展的瓶颈环节。当前,计算机科学家和工程技术人员对NP难度问题的探索,还需要面对诸多挑战。就目前的情况而言,对布局问题的研究主要是对其求解方法的研究,对布局问题复杂性研究的相对较少,但判别问题的复杂性是问题求解的基础。本文对布局问题复杂性的传递路线进行研究,旨在厘清不同布局问题之间的复杂性传递关系,主要的研究内容包括：(1)三类NP难性质的布局问题划分研究。首先是对布局问题NP难性质的声称说法进行统计归类;然后选择基于问题难度划界的分类策略,将布局问题分为已知NP难类、猜想NP难类和P类三类布局问题；最后针对三类问题实施不同的分类方案,得到比较合理的分类结果；(2)托盘装载问题归结为NP难问题的证明尝试。采用的证明思路是将顶点覆盖问题多项式转换为该问题,由于过程的复杂性,以失败告终；但是由证明过程所启发的求解方法(用顶点覆盖问题求解托盘问题)具有重要的意义,将该求解思路应用到实际布局问题中,利用顶点覆盖问题的方法求解实际直角边下料问题,并取得较好的结果。(3)不同布局文献对布局问题NP难性质的归纳。1)统计出证明(声称)不同布局问题复杂性的布局文献,即一共有哪些文献说明了其复杂性；2)不同布局问题的上一级布局文献；3)不同布局问题的下一级布局文献。(4)布局问题NP难证明中的归结传递路线的梳理。参考Wascher等人对切割与布局问题的六种基本问题类型,然后对不同布局问题NP难证明中的传递路线进行梳理,厘清不同布局问题之间的复杂性传递关系,建立布局问题复杂性归结传递图。(5)布局问题难度判定系统的建立。布局问题难度判定系统包括布局问题分类查询系统和布局问题复杂性判定两个子系统,用户可以实现布局问题分类类别的查询和复杂性的判定。本题的研究结果可以给研究布局问题的学者们在分类查询和复杂性依据方面提供有价值的支持；同时从侧面给工程技术人员在算法大类的选择和设计上给予辅助。
【关键词】：布局问题 复杂性 NP难 NP完全
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TB115
【目录】：

• 致谢5-6
• 摘要6-7
• ABSTRACT7-12
• 1 引言12-24
• 1.1 研究背景和意义12-14
• 1.1.1 研究背景12
• 1.1.2 研究意义12-14
• 1.2 布局问题概述14-18
• 1.2.1 布局问题的定义14-15
• 1.2.2 布局问题的复杂性15-16
• 1.2.3 布局问题的求解方法16-18
• 1.3 国内外研究现状18-19
• 1.4 研究内容19-21
• 1.4.1 主要研究内容19-20
• 1.4.2 论文章节结构20-21
• 1.5 本章小结21-24
• 2 布局问题NP难性质的划分研究24-36
• 2.1 NP完全理论概述24-26
• 2.1.1 P类和NP类问题24-25
• 2.1.2 NP-omplete类问题25-26
• 2.1.3 NP-Hard类问题26
• 2.2 布局问题NP难性质的声称说法研究26-30
• 2.2.1 声称说法的统计26-29
• 2.2.2 声称说法的分类29-30
• 2.3 布局问题复杂性的划分研究30-31
• 2.3.1 分类策略的选择30
• 2.3.2 分类方案的实施30-31
• 2.4 对布局问题NP难性质统计分类结果的分析31-35
• 2.4.1 统计结果31-34
• 2.4.2 结果分析34-35
• 2.5 本章小结35-36
• 3 布局问题NP难性质的证明尝试36-44
• 3.1 托盘装载问题归结为NP难问题的证明尝试36-38
• 3.1.1 托盘装载问题概述36-37
• 3.1.2 证明思路37-38
• 3.2 由证明过程所启发的问题求解方法38-40
• 3.2.1 求解思路38-39
• 3.2.2 求解实例39-40
• 3.3 求解方法的应用40-42
• 3.4 本章小结42-44
• 4 布局问题NP难性质的传递路线梳理44-56
• 4.1 WASCHER布局问题分类法概述44-46
• 4.2 布局问题复杂性的传递路线梳理46-51
• 4.2.1 六种基本布局问题47
• 4.2.2 复杂性传递关系的建立47-51
• 4.3 布局问题NP难证明中的归结传递图的建立51-53
• 4.4 关于归纳不同布局问题NP难性质的布局文献研究53-54
• 4.5 本章小结54-56
• 5 布局问题难度判定系统的建立56-68
• 5.1 布局问题难度判定系统的设计57-59
• 5.1.1 系统结构设计57-58
• 5.1.2 系统数据库设计58-59
• 5.2 布局问题NP难性质的描述模型59-63
• 5.2.1 描述模型的建立59-60
• 5.2.2 描述模型的内容60-63
• 5.3 布局问题难度判定系统的建立及运行63-66
• 5.4 本章小结66-68
• 6 总结与展望68-70
• 6.1 研究总结68-69
• 6.3 研究展望69-70
• 参考文献70-74
• 作者简历及攻读硕士学位期间取得的研究成果74-78
• 学位论文数据集78

【相似文献】

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

1 汤全林;胡安定;;赴瑞典参加“工业维修的组织与管理”国际研修班学习的主要内容(续)[J];设备维修;1984年02期

2 吴斐,侯云章;基于启发式结果的模拟退火算法在布局问题中的应用[J];物流科技;2005年09期

3 王金敏,查建中,王玉新;布局问题的聚块算法[J];机械设计;1999年02期

4 王金敏,王玉新,查建中;布局问题约束的分类及表达[J];计算机辅助设计与图形学学报;2000年05期

5 刘先畅;县域小城镇布局的几个问题[J];小城镇建设;2000年03期

6 周娜;宓为建;徐子奇;;设备混合布局问题研究[J];上海海事大学学报;2013年04期

7 朱国金;;广珠(澳)铁路选线布局问题的探讨[J];中国铁路;1993年08期

8 王金敏;齐杨;;矩形布局问题吸引子法研究[J];图学学报;2012年06期

9 唐晓君,查建中,陆一平;布局问题的复杂性和建模方法[J];北方交通大学学报;2003年01期

10 王金敏;王保春;朱艳华;;求解矩形布局问题的自适应算法[J];图学学报;2012年03期

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

1 丁梅;朱美琳;;钻井布局问题的模型及解法[A];中国运筹学会第六届学术交流会论文集（上卷）[C];2000年

中国重要报纸全文数据库 前4条

1 驻京记者 金丰杰;24小时供应≠24小时营业[N];医药经济报;2004年

2 本报评论员;配套服务应跟上[N];白银日报;2008年

3 记者 王静;中小学校布局问题亟待破题[N];石家庄日报;2013年

4 许昌县将官池镇党委书记 王建民;抓住三个关键环节 解决好三大问题[N];许昌日报;2012年

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

1 徐义春;卫星舱布局问题的智能求解方法研究[D];华中科技大学;2008年

2 黄振东;卫星舱布局问题的启发式求解与涌现计算[D];华中科技大学;2014年

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

1 宋真真;基于蚁群算法的布局问题研究[D];天津职业技术师范大学;2016年

2 杨萌;布局问题NP难性质的传递路线研究[D];北京交通大学;2016年

3 谢艳芳;求解加权圆集布局问题的启发式演化算法研究[D];湘潭大学;2012年

4 季美;卫星舱布局问题的求解研究[D];华中科技大学;2011年

5 杨林;布局问题的演化算法[D];湖南师范大学;2007年

6 王璐;切割与布局问题的算法分类研究[D];北京交通大学;2009年

7 马国通;两类矩形布局问题的启发式算法研究[D];北京交通大学;2008年

8 杨林;求解带性能约束圆集布局问题的启发式蚁群算法研究[D];湘潭大学;2010年

9 谭思捷;单行布局问题的变邻域算法研究及其应用[D];西南交通大学;2013年

10 刘玉飞;容量限制CVT及其在布局问题中的应用[D];合肥工业大学;2013年

，

本文编号：522826