QBF问题中隐蔽集的求解过程①.PDF

计 算 机 系 统 应 用 2016 年 第 25 卷 第 8 期 ① QBF 问题中隐蔽集的求解过程 杨俊成, 陶 琳, 李淑霞 (河南工业职业技术学院 电子信息工程系, 南阳 473000) 摘 要: 隐蔽集作为 QBF 问题的重要结构之一, 能使 QBF 这一难求解问题变得更加简单. QBF 问题中隐蔽集的 求解相当复杂且难以理解. 为了使读者更好的理解 QBF 问题中隐蔽集的求解过程, 本文对 QBF 问题中隐蔽集的 求解过程进行深入研究, 结合实例计算变量的深度、选择符合条件的变量 x 并计算其对应的三角依赖变量集 DΔ (x ) , 根据B = B ∪ {x }= {x }和ψ =ψ − DΔ (x ) 的思想求解出问题的隐蔽集, 希望本文能为该领域的相关研 ψ ψ 究人员提供一定的参考. 关键词: QBF 问题; 隐蔽集; 重要结构; 求解过程 Solving Process of Backdoors Set in QBF YANG Jun-Cheng, TAO Lin, LI Shu-Xia (Dept. of Computer Engineering, Henan Polytechnic Institute, Nanyang 473000, China) Abstract: The Backdoors as one of the important structures of problem QBF, it makes QBF problems easier in solving difficulty. In QBF problem, the solving of backdoors is quite complex and difficult to understand. In order to enable the reader to better understand the solving process, this paper researches the solving process of backdoors for QBF problems, calculates the depth of variable x and the triangle dependent set of variable DΔ (x ) that is meet the condition by ψ combining the examples. This paper solves the backdoors of this problem according to the ideas of B = B ∪ {x }= {x } and ψ =ψ − DΔ (x ) . We are hoping that it can provide a reference for researchers in this field. ψ Key words: QBF problem; backdoors; important structure; solving process 1 引言 (fixed-parameter tractable). QBF 问题中隐蔽集的求解 隐 蔽 集 (backdoor set) 作 为 量 化 布 尔 公 式 过程比较复杂且难以理解. 本文针对 QBF 问题中隐蔽 (Quantified Boolean Formulae,简称 QBF) 问题的一个重 集求解过程进行分析. 本文结构如下: 第一部分的引 要结构, 能有效地提高 QBF 问题的求解效率, 近年来 言用来分析本文问题的重要性,