最坏情况下X3SAT最大海明距离问题最小上界
X3SAT最大海明距离问题是指对于一个X3SAT问题实例，寻找该问题的任意两组可满足赋值之间最大的海明距离d.提出了一个新的基于DPLL的精确算法HMX来求解X3SAT最大海明距离问题.根据公式中的某个变量在两组真值赋值中的不同取值进行分支.另外，给出了多种化简规则，这些规则很好地提高了算法的时间效率.最后证明了该算法可以将X3SAT最大海明距离问题的最小上界由目前最好的(1.7107n)缩小到O(1.6760n)，其中n为公式中变量的数目.
海明距离 X3SAT DPLL 最坏情况 复杂性分析 上界
傅琳璐 周俊萍 殷明浩
东北师范大学 计算机科学与信息技术学院,吉林 长春 130117
国内会议
长春
中文
1-8
2012-08-04（万方平台首次上网日期，不代表论文的发表时间）