期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到5篇文章
< 1 >
每页显示 20 50 100
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
随机正则恰当(d,k)-SAT问题的可满足相变分析
1
作者 王晓峰 王军霞 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2024年第11期85-92,共8页
为深入理解随机正则恰当(d,k)-SAT问题难解的内在本质,理清相变与难解之间的变化规律,进一步设计高效的求解算法,引入随机正则恰当可满足性实例产生模型,采用一阶矩和二阶矩方法分析了该问题的相变情况,给出了正则恰当(d,k)-SAT问题的... 为深入理解随机正则恰当(d,k)-SAT问题难解的内在本质,理清相变与难解之间的变化规律,进一步设计高效的求解算法,引入随机正则恰当可满足性实例产生模型,采用一阶矩和二阶矩方法分析了该问题的相变情况,给出了正则恰当(d,k)-SAT问题的可满足相变点d^(*).当相变控制参数d^(*)时,正则恰当(d,k)-SAT问题实例高概率可满足;当d>d^(*)时,正则恰当(d,k)-SAT问题实例高概率不可满足.最后,选取子句长度k分别为3和4进行实验,结果表明:在d^(*)的取值分别为2.3798和3.0668附近发生了相变现象,进一步证明了理论结果与实验结果的一致性. 展开更多
关键词 随机正则恰当(d k)-sat问题 一阶矩 二阶矩 可满足性问题 相变分析
原文传递
随机均衡正则恰当(2s,k)-SAT问题的可满足相变 被引量：1
2
作者 王晓峰 于卓 +1 位作者 周锦程 许道云 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2022年第2期105-111,共7页
为深入理解均衡正则恰当(2s,k)-SAT问题的判定难度和可满足性解的分布情况,引入随机实例产生模型,利用一阶矩和二阶矩方法分析可满足性相变现象,给出随机均衡正则恰当(2s,k)-SAT问题可满足的相变点s∗.当s<s∗时,随机均衡正则恰当(2s,k... 为深入理解均衡正则恰当(2s,k)-SAT问题的判定难度和可满足性解的分布情况,引入随机实例产生模型,利用一阶矩和二阶矩方法分析可满足性相变现象,给出随机均衡正则恰当(2s,k)-SAT问题可满足的相变点s∗.当s<s∗时,随机均衡正则恰当(2s,k)-SAT实例高概率可满足;当s>s∗时,随机均衡正则恰当(2s,k)-SAT实例高概率不可满足.最后,选取了k=4和k=6的两组数据集进行实验验证,结果表明理论结果与实验结果符合. 展开更多
关键词 均衡正则恰当(2s k)-sat问题 相变分析 可满足性问题 一阶矩 二阶矩
原文传递
基于和声搜索算法求解组合优化问题 被引量：7
3
作者 李宁 刘建芹 贺毅朝 《计算机应用》 CSCD 北大核心 2012年第4期1041-1044,共4页
为了能够应用和声搜索算法(HSA)求解组合优化问题,基于HAS的三种操作的离散化实现提出了一种二进制和声搜索算法(BHSA),并将BHSA用于求解著名的k-可满足性(k-SAT)问题和0-1背包问题,通过与粒子群优化(BPSO)和遗传算法(GA)的实例计算对... 为了能够应用和声搜索算法(HSA)求解组合优化问题,基于HAS的三种操作的离散化实现提出了一种二进制和声搜索算法(BHSA),并将BHSA用于求解著名的k-可满足性(k-SAT)问题和0-1背包问题,通过与粒子群优化(BPSO)和遗传算法(GA)的实例计算对比验证了新算法的可行性与有效性。 展开更多
关键词 进化算法 二进制和声搜索 组合优化 k-sat问题 0-1背包问题
下载PDF
随机k-SAT问题的回溯算法分析 被引量：2
4
作者 许可 李未 《计算机学报》 EI CSCD 北大核心 2000年第5期454-458,共5页
通过研究搜索树的平均节点数 ,分析了回溯算法求解随机 k- SAT问题的平均复杂性 ,结果表明 :找到实例所有的解或证明其无解所需的平均节点数随变量数 n的增加而指数增长 ;随着 r(子句数 /变量数 )的增大 ,求解将变得越来越容易 ,而且当 ... 通过研究搜索树的平均节点数 ,分析了回溯算法求解随机 k- SAT问题的平均复杂性 ,结果表明 :找到实例所有的解或证明其无解所需的平均节点数随变量数 n的增加而指数增长 ;随着 r(子句数 /变量数 )的增大 ,求解将变得越来越容易 ,而且当 r趋近于无穷大时 ,以 n为指数 ,平均节点数的底数将无限地趋近于 1.因此 ,尽管回溯算法求解随机 k- SAT问题具有指数的平均复杂性 ,但当 r充分大以后 ,许多实例的求解将变得非常容易 . 展开更多
关键词 算法分析 平均复杂性 回溯算法 随机k-sat问题
下载PDF
MAX-k-SAT的PTAS归约等价性
5
作者 许道云 秦永彬 《计算机科学与探索》 CSCD 2009年第6期641-648,共8页
通过构造适当的极小不可满足公式,利用子句拼接技术,引入了一个一般化的从k-CNF公式(k≥3)到3-CNF公式之间的归约转换。基于该转换,给出了一个真值指派的转换算法,并证明了MAX-k-SAT与MAX-3-SAT是PTAS归约等价的。因此,对于k,t≥3,MAX-k... 通过构造适当的极小不可满足公式,利用子句拼接技术,引入了一个一般化的从k-CNF公式(k≥3)到3-CNF公式之间的归约转换。基于该转换,给出了一个真值指派的转换算法,并证明了MAX-k-SAT与MAX-3-SAT是PTAS归约等价的。因此,对于k,t≥3,MAX-k-SAT与MAX-t-SAT是PTAS归约等价的。 展开更多
关键词 极小不可满足公式 归约 MAX—k—sat问题 PTAS等价
下载PDF
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 下一页 到第 页
使用帮助 返回顶部