计算机科学与探索
計算機科學與探索
계산궤과학여탐색
JOURNAL OF FRONTIERS OF COMPUTER SCIENCE & TECHNOLOGY
2012年
7期
664-671
,共8页
海明距离%可满足性(SAT)%X3SAT%DPLL%最坏情况%复杂性分析%上界
海明距離%可滿足性(SAT)%X3SAT%DPLL%最壞情況%複雜性分析%上界
해명거리%가만족성(SAT)%X3SAT%DPLL%최배정황%복잡성분석%상계
X3SAT最大海明距离问题是指对于一个X3SAT问题实例,寻找该问题的任意两组可满足赋值之间的最大海明距离.提出了一个基于DPLL的精确算法HMX来求解X3SAT最大海明距离问题,根据公式中某个变量在两组真值赋值中的不同取值进行分支.给出了多种化简规则,这些规则很好地提高了算法的时间效率.证明了该算法可以将X3SAT最大海明距离问题的最小上界由目前最好的O(1.710 7n)缩小到O(1.676 0n),其中n为公式中变量的数目.
X3SAT最大海明距離問題是指對于一箇X3SAT問題實例,尋找該問題的任意兩組可滿足賦值之間的最大海明距離.提齣瞭一箇基于DPLL的精確算法HMX來求解X3SAT最大海明距離問題,根據公式中某箇變量在兩組真值賦值中的不同取值進行分支.給齣瞭多種化簡規則,這些規則很好地提高瞭算法的時間效率.證明瞭該算法可以將X3SAT最大海明距離問題的最小上界由目前最好的O(1.710 7n)縮小到O(1.676 0n),其中n為公式中變量的數目.
X3SAT최대해명거리문제시지대우일개X3SAT문제실례,심조해문제적임의량조가만족부치지간적최대해명거리.제출료일개기우DPLL적정학산법HMX래구해X3SAT최대해명거리문제,근거공식중모개변량재량조진치부치중적불동취치진행분지.급출료다충화간규칙,저사규칙흔호지제고료산법적시간효솔.증명료해산법가이장X3SAT최대해명거리문제적최소상계유목전최호적O(1.710 7n)축소도O(1.676 0n),기중n위공식중변량적수목.
