文件名称：基于分支回溯的NAE-3SAT问题求解算法 (2012年)
文件大小：337KB
文件格式：PDF
更新时间：2024-06-17 23:02:13
工程技术 论文
NAESAT问题是可满足性问题的一个重要扩展,在集合分裂、最大割集等NP完全问题中有着重要的应用.针对NAESAT问题的泛化NAE-3SAT问题,提出了一个基于分支回溯的精确算法NAE.算法给出了多种化简规则,这些化简规则很好地提高了算法的时间效率.最后证明了算法在最坏情况下的时间复杂度上界为O(1.618n),其中n为公式中的变量数目.