%0 Journal Article %A 傅琳璐 %A 周俊萍 %A 殷明浩 %T 最坏情况下X3SAT最大海明距离问题最小上界 %D 2012 %R %J 计算机科学与探索 %P 664-671 %V 6 %N 7 %X X3SAT最大海明距离问题是指对于一个X3SAT问题实例,寻找该问题的任意两组可满足赋值之间的最大海明距离。提出了一个基于DPLL的精确算法HMX来求解X3SAT最大海明距离问题,根据公式中某个变量在两组真值赋值中的不同取值进行分支。给出了多种化简规则,这些规则很好地提高了算法的时间效率。证明了该算法可以将X3SAT最大海明距离问题的最小上界由目前最好的O(1.710 7n)缩小到O(1.676 0n),其中n为公式中变量的数目。 %U http://fcst.ceaj.org/CN/abstract/article_516.shtml