期刊导航
期刊开放获取
河南省图书馆
退出
期刊文献
+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
检索
高级检索
期刊导航
共找到
1
篇文章
<
1
>
每页显示
20
50
100
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
显示方式:
文摘
详细
列表
相关度排序
被引量排序
时效性排序
最坏情况下X3SAT最大海明距离问题最小上界
1
作者
傅琳璐
周俊萍
殷明浩
《计算机科学与探索》
CSCD
2012年第7期664-671,共8页
X3SAT最大海明距离问题是指对于一个X3SAT问题实例,寻找该问题的任意两组可满足赋值之间的最大海明距离。提出了一个基于DPLL的精确算法HMX来求解X3SAT最大海明距离问题,根据公式中某个变量在两组真值赋值中的不同取值进行分支。给出了...
X3SAT最大海明距离问题是指对于一个X3SAT问题实例,寻找该问题的任意两组可满足赋值之间的最大海明距离。提出了一个基于DPLL的精确算法HMX来求解X3SAT最大海明距离问题,根据公式中某个变量在两组真值赋值中的不同取值进行分支。给出了多种化简规则,这些规则很好地提高了算法的时间效率。证明了该算法可以将X3SAT最大海明距离问题的最小上界由目前最好的O(1.7107n)缩小到O(1.6760n),其中n为公式中变量的数目。
展开更多
关键词
海明距离
可满足性(SAT)
x3sat
DPLL
最坏情况
复杂性分析
上界
下载PDF
职称材料
题名
最坏情况下X3SAT最大海明距离问题最小上界
1
作者
傅琳璐
周俊萍
殷明浩
机构
东北师范大学计算机科学与信息技术学院
出处
《计算机科学与探索》
CSCD
2012年第7期664-671,共8页
基金
国家自然科学基金Nos.61070084
60803102
+1 种基金
中央高校基本科研业务费专项资金No.11QNJJ006
浙江师范大学计算机软件与理论省级重中之重学科开放基金No.ZSDZZZZXK37~~
文摘
X3SAT最大海明距离问题是指对于一个X3SAT问题实例,寻找该问题的任意两组可满足赋值之间的最大海明距离。提出了一个基于DPLL的精确算法HMX来求解X3SAT最大海明距离问题,根据公式中某个变量在两组真值赋值中的不同取值进行分支。给出了多种化简规则,这些规则很好地提高了算法的时间效率。证明了该算法可以将X3SAT最大海明距离问题的最小上界由目前最好的O(1.7107n)缩小到O(1.6760n),其中n为公式中变量的数目。
关键词
海明距离
可满足性(SAT)
x3sat
DPLL
最坏情况
复杂性分析
上界
Keywords
Hamming distance
satisfiability(SAT)
x3sat
DPLL
worst case
complexity analysis
upper bound
分类号
TP301.5 [自动化与计算机技术—计算机系统结构]
下载PDF
职称材料
题名
作者
出处
发文年
被引量
操作
1
最坏情况下X3SAT最大海明距离问题最小上界
傅琳璐
周俊萍
殷明浩
《计算机科学与探索》
CSCD
2012
0
下载PDF
职称材料
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
上一页
1
下一页
到第
页
确定
用户登录
登录
IP登录
使用帮助
返回顶部