论文部分内容阅读
SAT问题的研究具有重要的理论意义和应用价值,目前求解SAT问题的方法大致分为完全算法和不完全算法两大类。由于SAT问题是NP完全问题,其计算复杂度随着问题规模的增大呈指数增长,因此完全算法在求解效率上通常难以满足需求；不完全算法尽管不一定能找到问题的解,但是其求解效率高并且通常能够满足需要,逐步成为求解SAT问题的研究热点。本文主要针对求解SAT问题的不完全算法进行研究。首先对求解SAT问题的免疫克隆算法、量子进化算法以及正交法的基本思想作了较详尽的分析。综合分析上述算法的优势,基于正交法的化简与属性判定,为SAT问题的求解提供了新的思路。基于对量子免疫克隆算法以及SAT问题正交性的研究分析,本文在第三章提出新的求解SAT问题的算法,即结合量子免疫克隆算法和正交性的正交量子免疫算法(OQICA)。该算法首先对SAT问题进行等价的正交化处理,消除子句之间重叠信息的同时有效的判定问题的属性,当问题可满足时,在正交子句组的基础上利用量子运算的高效性快速获得可满足的解。最后本文理论分析了OQICA是以概率1收敛的,并通过实验验证,正交量子免疫克隆算法比遗传算法和量子免疫克隆算法具有更高的求解成功率。