检索结果-内蒙古大学图书馆

自Steve Cook证明了第一个NP完全问题以来,众多的NP完全问题被陆续发现。目前,以SAT问题为根节点,四千多个NP完全问题已经形成了一棵巨大的归结树。NP完全问题遍布人工智能、数据库、程序语言、计算机网络等计算机科学领域,其研究具有重要的研究意义和应用价值。本文针对一个NP完全问题,即MSP问题,研究其结构性质,猜想特殊的结构可以使其算法证明得到简化。以简化证明为导引,从定义、算法、证明、归结等角度多方面深入理解MSP问题的特性,提出一种特殊形式和结构的MSP问题。类比对SAT问题开展研究时,同样开展特殊结构的2-SAT问题、3-SAT问题、k-SAT、max-SAT问题研究,特殊形式和结构的MSP问题同样具有重要意义,并能进一步推动原问题的研究。提出的课题依托了“NP完全问题求解复杂性研究”这一国家自然科学基金项目。本文的主要工作如下:1.首先介绍了MSP问题的定义和相关概念。详细说明了ZH算法的步骤和各个算子的功能。将SAT问题归结到MSP问题。2.从特殊形式的角度侧面研究MSP问题,提出一种特殊形式和结构的MSP问题。并在此基础上说明特殊结构的特殊意义。还证明了特殊结构和形式的MSP问题的NP完全性。3.将ZH算法应用于本文提出的特殊结构MSP问题求解,给出了新的证明。针对特殊结构MSP问题求解算法的新的证明中,简化图的输入条件,使得部分结论的证明更加简单。4.对ZH算法求解特殊结构MSP问题的正确性证明进行了实验验证。具体做法是,对产生的特殊结构的MSP问题的问题实例进行求解,同时与回溯法进行比较,验证算法的正确性。

关键词： MSP问题多项式归结 NP完全问题

来源：评论

学校读者我要写书评

暂无评论

特殊形式和结构的MSP问题NP完全性研究

引用

计算技术与自动化 2021年第3期40卷 78-83页

作者：马兰刘新朱哲湘潭大学计算机学院网络空间安全学院湖南湘潭411105

针对一个NP完全问题,即MSP问题,研究其问题的结构性质,猜想特殊的结构可以使其算法证明得到简化。以简化证明为导引,提出一种特殊形式和结构的MSP问题。而约束了形状的特殊形式和结构的MSP问题如果不具备NP完全性,会极大影响进一步简化... 详细信息

针对一个NP完全问题,即MSP问题,研究其问题的结构性质,猜想特殊的结构可以使其算法证明得到简化。以简化证明为导引,提出一种特殊形式和结构的MSP问题。而约束了形状的特殊形式和结构的MSP问题如果不具备NP完全性,会极大影响进一步简化算法证明的研究意义。因此,提出的特殊形式和结构的MSP问题进行了NP完全性质证明。类比对SAT问题开展研究时,同样开展特殊结构的2-SAT问题、3-SAT问题、k-SAT、max-SAT问题研究,特殊形式和结构的MSP问题同样具有重要意义,并进一步推动原问题的研究。

关键词： MSP问题多项式归结 NP完全性

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：