文件名称：最坏情况下Min-2SAT问题的上界 (2012年)
文件大小：357KB
文件格式：PDF
更新时间：2024-06-06 18:59:53
工程技术 论文
最坏情况下MaxSAT问题上界的研究已成为一个热门的研究领域．与MaxSAT问题相对的是MinSAT问题，在求解某些组合优化问题时，将其转化为MinSAT问题比转化为MaxSAT问题有着更快的速度，因此对MinSAT问题进行研究．针对Min-2SAT问题提出算法MinSATAlg，该算法首先利用化简算法Simplify对公式进行化简，然后通过分支树的方法对不同情况的子句进行分支．从子句数目的角度分析算法的时间复杂度并证明Min-2SAT问题可在 O(1．134 3m)时间内求解，对于每个变量至多出现在3个