计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2014年
3期
598-605
,共8页
最坏情况%上界%X2SAT%复杂性分析%分支树
最壞情況%上界%X2SAT%複雜性分析%分支樹
최배정황%상계%X2SAT%복잡성분석%분지수
worst case%upper bounds%X2SAT%complexity analysis%branching tree
最坏情况下XSAT问题上界的研究已成为一个热门的研究领域.针对XSAT的泛化问题X2 SAT提出了算法X2SAT-N,该算法首先利用简化算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.证明了该算法可以将X2SAT问题的时间复杂度由目前最好的O(1.451 1n)提高到O(1.420 3n),其中n为X2 SAT公式中变量的数目.X2SAT问题实例的大小不仅依赖于变量的数目还依赖于公式的长度,时间复杂性是根据问题实例的大小所组成的函数计算所得.因此又提出了算法X2SAT-L,并从公式长度的角度证明了X2SAT问题在O(1.364 3l)时间上界内可解.
最壞情況下XSAT問題上界的研究已成為一箇熱門的研究領域.針對XSAT的汎化問題X2 SAT提齣瞭算法X2SAT-N,該算法首先利用簡化算法Simplify對公式進行化簡,然後通過分支樹的方法對不同情況的子句進行分支.證明瞭該算法可以將X2SAT問題的時間複雜度由目前最好的O(1.451 1n)提高到O(1.420 3n),其中n為X2 SAT公式中變量的數目.X2SAT問題實例的大小不僅依賴于變量的數目還依賴于公式的長度,時間複雜性是根據問題實例的大小所組成的函數計算所得.因此又提齣瞭算法X2SAT-L,併從公式長度的角度證明瞭X2SAT問題在O(1.364 3l)時間上界內可解.
최배정황하XSAT문제상계적연구이성위일개열문적연구영역.침대XSAT적범화문제X2 SAT제출료산법X2SAT-N,해산법수선이용간화산법Simplify대공식진행화간,연후통과분지수적방법대불동정황적자구진행분지.증명료해산법가이장X2SAT문제적시간복잡도유목전최호적O(1.451 1n)제고도O(1.420 3n),기중n위X2 SAT공식중변량적수목.X2SAT문제실례적대소불부의뢰우변량적수목환의뢰우공식적장도,시간복잡성시근거문제실례적대소소조성적함수계산소득.인차우제출료산법X2SAT-L,병종공식장도적각도증명료X2SAT문제재O(1.364 3l)시간상계내가해.
