智能系统学报
智能繫統學報
지능계통학보
CAAI TRANSACTIONS ON INTELLIGENT SYSTEMS
2012年
3期
241-245
,共5页
谷文祥%姜蕴晖%周俊萍%殷明浩
穀文祥%薑蘊暉%週俊萍%慇明浩
곡문상%강온휘%주준평%은명호
MaxSAT%MinSAT%Min-2SAT%MaxSAT问题的上界%Min-2SAT问题的上界%子句数目%分支树
MaxSAT%MinSAT%Min-2SAT%MaxSAT問題的上界%Min-2SAT問題的上界%子句數目%分支樹
MaxSAT%MinSAT%Min-2SAT%MaxSAT문제적상계%Min-2SAT문제적상계%자구수목%분지수
最坏情况下MaxSAT问题上界的研究已成为一个热门的研究领域.与MaxSAT问题相对的是MinSAT问题,在求解某些组合优化问题时,将其转化为MinSAT问题比转化为MaxSAT问题有着更快的速度,因此对MinSAT问题进行研究.针对Min-2SAT问题提出算法MinSATAlg,该算法首先利用化简算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.从子句数目的角度分析算法的时间复杂度并证明Min-2SAT问题可在O(1.134 3m)时间内求解,对于每个变量至多出现在3个2-子句中的情况,得到最坏情况下的上界为O(1.122 5n),其中n为变量的数目.
最壞情況下MaxSAT問題上界的研究已成為一箇熱門的研究領域.與MaxSAT問題相對的是MinSAT問題,在求解某些組閤優化問題時,將其轉化為MinSAT問題比轉化為MaxSAT問題有著更快的速度,因此對MinSAT問題進行研究.針對Min-2SAT問題提齣算法MinSATAlg,該算法首先利用化簡算法Simplify對公式進行化簡,然後通過分支樹的方法對不同情況的子句進行分支.從子句數目的角度分析算法的時間複雜度併證明Min-2SAT問題可在O(1.134 3m)時間內求解,對于每箇變量至多齣現在3箇2-子句中的情況,得到最壞情況下的上界為O(1.122 5n),其中n為變量的數目.
최배정황하MaxSAT문제상계적연구이성위일개열문적연구영역.여MaxSAT문제상대적시MinSAT문제,재구해모사조합우화문제시,장기전화위MinSAT문제비전화위MaxSAT문제유착경쾌적속도,인차대MinSAT문제진행연구.침대Min-2SAT문제제출산법MinSATAlg,해산법수선이용화간산법Simplify대공식진행화간,연후통과분지수적방법대불동정황적자구진행분지.종자구수목적각도분석산법적시간복잡도병증명Min-2SAT문제가재O(1.134 3m)시간내구해,대우매개변량지다출현재3개2-자구중적정황,득도최배정황하적상계위O(1.122 5n),기중n위변량적수목.
