期刊导航
期刊开放获取
河南省图书馆
退出
期刊文献
+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
检索
高级检索
期刊导航
共找到
1
篇文章
<
1
>
每页显示
20
50
100
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
显示方式：
文摘
详细
列表
相关度排序
被引量排序
时效性排序
基于分支回溯的NAE-3SAT问题求解算法
1
作者
谷文祥
傅琳璐
+1 位作者
周俊萍
姜蕴晖
《智能系统学报》
北大核心
2012年第6期506-511,共6页
NAESAT问题是可满足性问题的一个重要扩展,在集合分裂、最大割集等NP完全问题中有着重要的应用.针对NAESAT问题的泛化NAE-3SAT问题,提出了一个基于分支回溯的精确算法NAE.算法给出了多种化简规则,这些化简规则很好地提高了算法的时间效...
NAESAT问题是可满足性问题的一个重要扩展,在集合分裂、最大割集等NP完全问题中有着重要的应用.针对NAESAT问题的泛化NAE-3SAT问题,提出了一个基于分支回溯的精确算法NAE.算法给出了多种化简规则,这些化简规则很好地提高了算法的时间效率.最后证明了算法在最坏情况下的时间复杂度上界为O(1.618n),其中n为公式中的变量数目.
展开更多
关键词
NAE
sat
nae-3sat
时间复杂性
nae-3sat
问题上界
变量数目
分支回溯
下载PDF
职称材料
题名
基于分支回溯的NAE-3SAT问题求解算法
1
作者
谷文祥
傅琳璐
周俊萍
姜蕴晖
机构
东北师范大学计算机科学与信息技术学院
长春建筑学院基础教学部
出处
《智能系统学报》
北大核心
2012年第6期506-511,共6页
基金
国家自然科学基金资助项目(61070084
60803102)
+1 种基金
中央高校基本科研业务费专项资金资助项目(11QNJJ006)
浙江师范大学计算机软件与理论省级重中之重学科开放基金资助项目(ZSDZZZZXK37)
文摘
NAESAT问题是可满足性问题的一个重要扩展,在集合分裂、最大割集等NP完全问题中有着重要的应用.针对NAESAT问题的泛化NAE-3SAT问题,提出了一个基于分支回溯的精确算法NAE.算法给出了多种化简规则,这些化简规则很好地提高了算法的时间效率.最后证明了算法在最坏情况下的时间复杂度上界为O(1.618n),其中n为公式中的变量数目.
关键词
NAE
sat
nae-3sat
时间复杂性
nae-3sat
问题上界
变量数目
分支回溯
Keywords
not-all-equal
sat
isfiability
not-all-equal
3
-
sat
isfiability
time complexity
upper bounds for Not-All-Equal
3
-
sat
isfiability
number of variables
DPLL
分类号
TP301.6 [自动化与计算机技术—计算机系统结构]
下载PDF
职称材料
题名
作者
出处
发文年
被引量
操作
1
基于分支回溯的NAE-3SAT问题求解算法
谷文祥
傅琳璐
周俊萍
姜蕴晖
《智能系统学报》
北大核心
2012
0
下载PDF
职称材料
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
上一页
1
下一页
到第
页
确定
用户登录
登录
IP登录
使用帮助
返回顶部
