求解两类图论问题的P系统研究

发布时间：2017-10-17 11:26

  本文关键词：求解两类图论问题的P系统研究

  更多相关文章： 顶点覆盖 度约束生成树 图论 P系统 膜计算

【摘要】：膜计算(也被称为膜系统或P系统)是罗马尼亚Gheorghe.P?un教授于1998年从细胞中抽象出的新的计算模型,自被提出后,发展迅速,并成为自然计算中的一个分支。由于细胞内的化学反应可以并行执行,且反应所消耗的能量非常小,所以,P系统拥有极大并行性,用来解决一些复杂问题得心应手,从而获得远远超过传统电子计算机的计算能力,也为很多难点问题带来新的求解思路。已有研究证明,膜计算可以在多项式时间内解决很多NP-完全问题。顶点覆盖问题和度约束生成树问题是图论中两类经典的NP难问题,在电子计算机计算模型下,对于这两类问题的求解要么只能求出其个别值,要么对于大规模的问题求解根本束手无策。膜计算作为一个新兴的研究领域,虽然其对于求解NP难问题拥有很大的优势,但是仍然鲜有对这两类问题的研究成果发表。不论从扩展膜计算的应用领域上,还是从实际应用中,研究这两类NP难问题都有着一定的理论意义和应用价值。因此,本文通过对顶点覆盖问题和度约束生成树问题的分析,设计出求解这两类问题全部解的P系统,扩展P系统在图论领域的研究,也为P系统计算机的物理实现提供一定的理论基础。本文所完成的研究工作简述如下:(1)根据图论中顶点覆盖问题基础知识及其特点,设计出判定顶点覆盖的具体流程,为求解该问题的具体实现奠定基础。(2)根据图论中度约束生成树问题基础知识及其特点,设计出判定生成树的具体流程,为求解该问题的具体实现奠定基础。(3)通过膜计算模型的研究,设计了一个求解顶点覆盖问题全部解的P系统,并用实例及计算机仿真程序来验证该P系统的可行性。(4)通过膜计算模型的研究,设计了一个求解度约束生成树问题全部解的P系统,并用实例及计算机仿真程序来验证该P系统的可行性。综上所述,本文通过选择顶点覆盖问题和度约束生成树问题进行P系统研究,完善了P系统中对于NP难问题的研究,为其他NP难问题的求解提供参考,也为今后解决其他领域问题的提供解决思路。
【关键词】：顶点覆盖 度约束生成树 图论 P系统 膜计算
【学位授予单位】：重庆大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要3-4
• ABSTRACT4-8
• 1 绪论8-12
• 1.1 引言8-9
• 1.2 国内外研究现状综述9-10
• 1.3 研究的目的及意义10-11
• 1.4 本文结构及安排11-12
• 2 研究基础12-20
• 2.1 膜计算基础12-14
• 2.1.1 膜及其表示12-13
• 2.1.2 类细胞P系统定义13-14
• 2.2 图论问题基础14-15
• 2.3 顶点覆盖问题15-17
• 2.3.1 问题定义15-16
• 2.3.2 判定方法16-17
• 2.4 度约束生成树问题17-18
• 2.4.1 问题定义17
• 2.4.2 判定方法17-18
• 2.5 P系统仿真平台18-19
• 2.6 本章小结19-20
• 3 顶点覆盖问题全部解的求解P系统 ΠAll-VCP20-32
• 3.1 ΠAll-VCP的定义20-21
• 3.2 All-VCP求解流程21-23
• 3.3 规则集合23-25
• 3.4 实例分析25-26
• 3.5 系统仿真26-31
• 3.6 本章小结31-32
• 4 度约束生成树问题全部解求解P系统 ΠAll-DCSTP32-43
• 4.1 ΠAll-DCSTP的定义32-33
• 4.2 All-DCSTP求解流程33-35
• 4.3 规则集合35-38
• 4.4 实例分析38-39
• 4.5 系统仿真39-42
• 4.6 本章小结42-43
• 5 总结与展望43-45
• 5.1 总结43
• 5.2 展望43-45
• 致谢45-46
• 参考文献46-49
• 附录49
• A. 作者在攻读学位期间发表的论文目录49
• B. 作者在攻读学位期间参与的科研项目49

【相似文献】

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

1 曹布阳,林亚雄;最小费用/容量比生成树的一个算法[J];上海机械学院学报;1985年03期

2 杨春德;Fuzzy网络中生成树的优化问题[J];重庆邮电学院学报;1996年02期

3 ;[J];;年期

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

1 冯俊文;;最优生成树的表格求解方法[A];中国运筹学会第六届学术交流会论文集（下卷）[C];2000年

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

1 李幸福;最大内部点生成树问题的算法及复杂性[D];山东大学;2015年

2 王岩;扭立方体和奇偶立方体上独立生成树的嵌入研究[D];苏州大学;2014年

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

1 钟玉文;求解两类图论问题的P系统研究[D];重庆大学;2016年

2 徐忆晨;最小标记生成树问题的研究与拓展[D];复旦大学;2009年

，

本文编号：1048570