基于变元加权的一种求解SAT问题的新方法

摘要：

研究合取范式可满足性的SAT问题作为一个NP完全问题,在计算机科学及组合优化问题领域中有着中心课题的重要地位.由于其NP问题的性质决定了它尚无通用快速的完全算法,因此基于"实验算法学"的思想,按照平均性态而不是最坏情况性态的原则,对具有启发式策略的不完全算法的研究成为近年来大家关注与努力的焦点.该文正是立足于此,提出了"加权消元"这一种全新而且高效的算法.

关键词：SAT问题、不完全算法、变元权重

所属期刊栏目：40

分类号：O221.2;F224.5(运筹学)

资助基金：华南农业大学校科研和教改项目

在线出版日期：2004-03-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：74-77