图的极大邻集搜索算法序列及序列终点的性质研究

发布时间：2017-03-22 08:19

  本文关键词：图的极大邻集搜索算法序列及序列终点的性质研究，，由笔耕文化传播整理发布。

【摘要】：本文主要研究极大邻集搜索算法(Maximal Neighborhood Search,简记为MNS),重点考虑由这种算法在图上生成的序列和序列终点所满足的性质.论文首先分析了MNS算法与字典序广度优先搜索(LexBFS)算法、最大势能搜索(MCS)算法以及字典序深度优先搜索(LexDFS)算法的相似性.我们用与LexBFS、MCS和LexDFS类似的方法,从弦图入手,发现MNS序列不一定是moplex删除序列,区别于已知的LexBFS、MCS和LexDFS序列都可以定义moplex删除序列.之后为了寻找图的极小分割集和极大团,考虑到MNS算法的特性,我们从指标搜索(label search)的角度入手,探索出当MNS序列中标号相邻的点的指标集满足一定条件后,我们便可以通过相邻两点中标号较晚的点的指标求得图的极小分割集,并通过相邻两点中标号较早的点和它的指标集导出图的极大团.文章中我们利用数学归纳法从不同角度证明了这种方法的正确性.同时,给出反例说明这种方法在非弦图上并不适用.最后,我们研究了MNS序列终点的性质,并证实了弦图中MNS序列终点一定属于某个molpex.然而在将结论推广到一般图上时发现非弦图上的MNS序列终点不满足这个性质.
【关键词】：极大邻集搜索算法 序列 极小分割集 极大团 moplex
【学位授予单位】：兰州大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 中文摘要3-4
• Abstract4-6
• 第一章 引言6-8
• 1.1 极大邻集搜索算法的背景及研究现状6-7
• 1.2 本文研究内容7
• 1.3 本文结构7-8
• 第二章 基本概念及符号说明8-11
• 第三章 极大邻集搜索序列及序列终点的性质11-27
• 3.1 极大邻集搜索序列与moplex删除序列的关系11-13
• 3.2 在弦图上利用极大邻集搜索算法寻找极小分割集13-23
• 3.3 在弦图上利用极大邻集搜索算法寻找极大团23-25
• 3.4 极大邻集搜索算法在弦图上终点的性质研究25-27
• 第四章 总结27-28
• 附录28-29
• 参考文献29-30
• 致谢30

【相似文献】

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

1 黄帅;马良;;多目标0-1规划的和声搜索算法[J];数学的实践与认识;2012年17期

2 雍龙泉;刘三阳;拓守恒;熊文涛;陈涛;;改进的和声搜索算法求绝对值方程[J];黑龙江大学自然科学学报;2013年03期

3 王慧敏;贺兴时;盛孟龙;;一种改进的和声搜索算法[J];纺织高校基础科学学报;2013年03期

4 冯远静;俞立;冯祖仁;;蚁群协同模式搜索算法及其收敛性分析[J];控制理论与应用;2007年06期

5 刘勇;马良;;非线性极大极小问题的混沌万有引力搜索算法求解[J];计算机应用研究;2012年01期

6 金文梁;;量子搜索算法的多相位关系研究[J];计算机学报;2012年07期

7 张伟;李华天;刘积仁;;线性可采纳搜索算法的充要条件[J];控制与决策;1992年02期

8 李树荣;陈国霞;雷阳;张强;;一种多策略协同的加速和声搜索算法[J];系统科学与数学;2013年10期

9 余鹏;隽志才;;两层应急抢修系统选址问题的核搜索算法[J];计算机应用研究;2013年11期

10 欧阳海滨;高立群;邹德旋;孔祥勇;;和声搜索算法探索能力研究及其修正[J];控制理论与应用;2014年01期

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

1 张玲;姜立志;;能量抵消测量相位中的相位搜索算法[A];2009年全国水声学学术交流暨水声学分会换届改选会议论文集[C];2009年

2 李金;蒋国平;;一种改进的复杂网络搜索算法[A];2007中国控制与决策学术年会论文集[C];2007年

3 罗家祥;唐立新;李小林;刘建荣;邬成新;;分散搜索算法在板坯匹配优化问题中的应用研究[A];全国冶金自动化信息网2009年会论文集[C];2009年

4 李潇磊;伍瑞卿;朱维乐;;运动搜索算法的比较与改进[A];2007北京地区高校研究生学术交流会通信与信息技术会议论文集（上册）[C];2008年

5 程振波;邓志东;;优化策略模型下的匹配律算法[A];2009年中国智能自动化会议论文集（第五分册）[东南大学学报（增刊）][C];2009年

6 彭明侨;罗先觉;邹晓松;;基于改进概率搜索算法的模拟电路故障诊断[A];第四届中国测试学术会议论文集[C];2006年

7 常新杰;李言俊;;搜索算法的研究进展[A];1998年中国智能自动化学术会议论文集（上册）[C];1998年

8 糜玉林;左斌;;基于协同控制的极值搜索算法与控制器一体化设计[A];2007年中国智能自动化会议论文集[C];2007年

9 钟普查;鲍皖苏;;基于相位变换的量子搜索算法研究[A];第十三届全国量子光学学术报告会论文摘要集[C];2008年

10 罗春华;张继勇;郑方;徐明星;;一种基于HTK的词图搜索算法[A];第六届全国人机语音通讯学术会议论文集[C];2001年

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

1 孙杰;基于绝热演化的量子搜索算法研究[D];华中科技大学;2013年

2 张映玉;绝热量子搜索算法研究[D];华中科技大学;2011年

3 阎兴

本文编号：261194