隐蔽集求解的相关问题分析

PDF全文下载：2016050580

杨俊成1， 李淑霞 1， 蔡增玉2

（1.河南工业职业技术学院 计算机工程系，河南 南阳  473000; 2.郑州轻工业学院 计算机与通信工程学院， 河南 郑州 450002）

摘要： SAT命题可满足性问题的隐蔽集作为引导搜索SAT问题的关键决策变量，可以优化SAT问题的求解，成为人工智能方向的研究热点之一。本研究对SAT问题隐蔽集中的若干问题进行研究，分别从隐蔽集的概念、隐蔽集的分类进行全面分析，提出影响求解隐蔽集大小的相关因素，论述隐蔽集的参数复杂性与问题难度的关系。

关键词： SAT问题； 隐蔽集； 问题类； 参数复杂性； 问题难度

中图分类号： TP 18文献标志码： A

Analysis of Some Problems in Solving Backdoors

YANG Juncheng1, LI Shuxia1, CAI Zengyu2

（1.Department of Computer Engineering, Henan Polytechnic Institute, Nanyang 473000, China;

2.School of Computer and Communication, Zhengzhou University of Light Industry, Zhengzhou 450002， China)

Abstract: The variables of backdoors are key decision variables to guide the search for SAT problems, and which optimize SAT problem solving and therefore become the one of the hot spots for artificial intelligence direction. This paper studies some problems of the backdoors of SAT problems, analyzes the concept of backdoors and classification of backdoors, proposes the factor of impact backdoors size solving, discusses the relationship of the parameters complexity of backdoors and problem difficulty comprehensively.

Key word: propositional satisfiability problem； backdoors； problem class； parameters complexity；problem difficulty

 收稿日期： 20150608

作者简介： 杨俊成(1982—),男，讲师.

文章编号： 16726987（2016）05058004； DOI： 10.16351/j.16726987.2016.05.020