随机k-SAT问题的回溯算法分析 被引量：2

1

作者 许可 李未 《计算机学报》 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模型的上界研究

2

作者 高宗升 许学琳 《江西师范大学学报（自然科学版）》 CAS 北大核心 2011年第2期111-115,共5页

对于包含n个变量和m=αn个长度为k的子句的CNF公式,人们比较关注公式中最大可满足子句的个数max Fk(MAX k-SAT).当子句密度α比较大时,随机MAX k-SAT模型中的变量f k(n,αn)E(max Fk)的上界可以用一阶矩方法给出.通过对一阶矩方法放缩... 对于包含n个变量和m=αn个长度为k的子句的CNF公式,人们比较关注公式中最大可满足子句的个数max Fk(MAX k-SAT).当子句密度α比较大时,随机MAX k-SAT模型中的变量f k(n,αn)E(max Fk)的上界可以用一阶矩方法给出.通过对一阶矩方法放缩精度的改进,得到了它的一个更紧的上界(1-1/2 k)αn+h(α,t)·αn.同时,可以证明这个新的上界随着t的增大而变得更紧. 展开更多

关键词 MAX k-sat 上界 一阶矩方法

在线阅读 下载PDF 职称材料

随机k-SAT公式不可满足性VS最小k-击中集

3

作者 杨智应 《计算机应用与软件》 CSCD 2009年第2期100-102,113,共4页

给定一个k-SAT实例F,将作用于公式F得到随机k-SAT实例F′。在随机扰动模型M(m;n;k)下,随机k-SAT实例F′的若干性质。并证实当子句密度足够大时,随机k-SAT实例F′的不可满足性判定可以归结为最小k-击中集问题的求解。

关键词 随机k-sat实例 随机扰动模型M(m N k) 最小 k-击中集

在线阅读 下载PDF 职称材料

随机k-SAT的相变上下界

4

作者 李倩倩 王以松 +1 位作者 冯仁艳 张振鹏 《贵州大学学报（自然科学版）》 2016年第5期86-90,共5页

在随机k-SAT模型的基础上,针对合取范式的满足性问题进行研究。对于固定的变量数n,随着子句数m增加,当m/n接近某一值时公式的可满足性发生剧烈的变化,可满足的概率从1变为0,也就是经常提到的相变问题。证明k-SAT相变的阈值上界为2kln2;... 在随机k-SAT模型的基础上,针对合取范式的满足性问题进行研究。对于固定的变量数n,随着子句数m增加,当m/n接近某一值时公式的可满足性发生剧烈的变化,可满足的概率从1变为0,也就是经常提到的相变问题。证明k-SAT相变的阈值上界为2kln2;当k(k<53)比较小时阈值下界为2^(k-1)ln2;当k(k≥53)比较大的时候,对任何ε=ε(k)>0(ε是关于k的函数)且εn→!(趋近无穷大),存在α0=2~k ln2,使得下界为αl=(1-ε)α0。通过实验对k为2,3,4时的阈值进行验证。 展开更多

关键词 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 职称材料

随机正则3-(d,k)-SAT问题的可满足性相变

6

作者 王晓峰 唐傲 +4 位作者 彭庆媛 颜冬 华盈盈 何飞 王军霞 《华中科技大学学报(自然科学版)》 北大核心 2025年第10期42-48,83,共8页

受随机正则恰当(d,k)-SAT(可满足性)问题的特征启发,提出了随机正则3-(d,k)-SAT问题.首先,引入了随机正则3-(d,k)-SAT问题实例生成模型,用于产生随机正则(d,k)-CNF(合取范式)公式.该模型采用完美匹配机制,每个随机完美匹配都对应一个随... 受随机正则恰当(d,k)-SAT(可满足性)问题的特征启发,提出了随机正则3-(d,k)-SAT问题.首先,引入了随机正则3-(d,k)-SAT问题实例生成模型,用于产生随机正则(d,k)-CNF(合取范式)公式.该模型采用完美匹配机制,每个随机完美匹配都对应一个随机正则3-(d,k)-SAT实例.然后,结合一阶矩方法、二阶矩方法和正则(d,k)-CNF公式的解空间结构,给出了当k>3时,随机正则3-(d,k)-SAT问题的可满足性相变点dk.当d>dk时,随机正则(d,k)-CNF实例公式高概率3-恰当不可满足;当d<dk时,随机正则(d,k)-CNF实例公式高概率3-恰当可满足.最后,分别取变元规模n=10,k=6和n=15,k=10的两组数据集进行实验.实验结果表明:随机正则3-(d,k)-SAT问题存在相变现象,分别发生在d_(6)=1.407 4和d_(10)=1.962 4附近,验证了理论证明所得相变点的正确性. 展开更多

关键词 相变现象 随机正则3-(d k)-SAT问题 矩方法 正则(d k)-CNF公式 生成模型

原文传递

基于和声搜索算法求解组合优化问题 被引量：7

7

作者 李宁 刘建芹 贺毅朝 《计算机应用》 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 职称材料

随机均衡正则恰当(2s,k)-SAT问题的可满足相变 被引量：6

8

作者 王晓峰 于卓 +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问题 相变分析 可满足性问题 一阶矩 二阶矩

原文传递

随机正则(k,r)-SAT问题的可满足临界 被引量：8

9

作者 周锦程 许道云 卢友军 《软件学报》 EI CSCD 北大核心 2016年第12期2985-2993,共9页

研究k-SAT问题实例中每个变元恰好出现r=2s次,且每个变元对应的正、负文字都出现s次的严格随机正则(k,r)-SAT问题.通过构造一个特殊的独立随机实验,结合一阶矩方法,给出了严格随机正则(k,r)-SAT问题可满足临界值的上界.由于严格正则情... 研究k-SAT问题实例中每个变元恰好出现r=2s次,且每个变元对应的正、负文字都出现s次的严格随机正则(k,r)-SAT问题.通过构造一个特殊的独立随机实验,结合一阶矩方法,给出了严格随机正则(k,r)-SAT问题可满足临界值的上界.由于严格正则情形与正则情形的可满足临界值近似相等,因此得到了随机正则(k,r)-SAT问题可满足临界值的新上界.该上界不仅小于当前已有的随机正则(k,r)-SAT问题的可满足临界值上界,而且还小于一般的随机k-SAT问题的可满足临界值.因此,这也从理论上解释了在相变点处的随机正则(k,r)-SAT问题实例通常比在相应相变点处同规模的随机k-SAT问题实例更难满足的原因.最后,数值分析结果验证了所给上界的正确性. 展开更多

关键词 随机正则(k r)-SAT问题 可满足临界值 相变现象 计算复杂性

在线阅读 下载PDF 职称材料

d-正则(k,s)-SAT问题的NP完全性 被引量：3

10

作者 符祖峰 许道云 《软件学报》 EI CSCD 北大核心 2020年第4期1113-1123,共11页

研究具有正则结构的SAT问题是否是NP完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函数f(k),使得当s≤f(k)时,所有实例都可满足;当s≥f(k)+1时,对应的SAT问题是NP完全问题.研究具有更强正则... 研究具有正则结构的SAT问题是否是NP完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函数f(k),使得当s≤f(k)时,所有实例都可满足;当s≥f(k)+1时,对应的SAT问题是NP完全问题.研究具有更强正则约束的d-正则(k,s)-SAT问题,其要求实例中每个变元的正负出现次数之差不超过给定的自然数d.通过设计一种多项式时间的归约方法,证明d-正则(k,s)-SAT问题存在一个临界函数f(k,d),使得当s≤f(k,d)时,所有实例都可满足;当s≥f(k,d)+1时,d-正则(k,s)-SAT问题是NP完全问题.这种多项式时间的归约变换方法通过添加新的变元和新的子句,可以更改公式的子句约束密度,并约束每个变元正负出现次数的差值.这进一步说明,只用子句约束密度不足以刻画CNF公式结构的特点,对临界函数f(k,d)的研究有助于在更强正则约束条件下构造难解实例. 展开更多

关键词 d-正则(k s)-CNF公式 SAT问题 NP完全性

在线阅读 下载PDF 职称材料

局部引理及其在(r，s)-SAT问题中的应用

11

作者 邓天炎 张庆顺 许道云 《计算机工程与科学》 CSCD 2008年第11期68-71,共4页

一般说来,寻找满足一定结构性质的对象结构是困难的。概率方法提供了解决此类问题的途径:证明满足一定结构性质的对象的概率大于零。在概率方法中,局部引理是一个关键技术。本文介绍了局部引理的基本原理和使用方法,并将其应用到估计(k,... 一般说来,寻找满足一定结构性质的对象结构是困难的。概率方法提供了解决此类问题的途径:证明满足一定结构性质的对象的概率大于零。在概率方法中,局部引理是一个关键技术。本文介绍了局部引理的基本原理和使用方法,并将其应用到估计(k,s)-SAT问题中临界函数的下界。 展开更多

关键词 概率方法 局部引理(r s)-SAT问题 临界函数

在线阅读 下载PDF 职称材料

随机正则恰当(d,k)-SAT问题的可满足相变分析

12

作者 王晓峰 王军霞 《华中科技大学学报（自然科学版）》 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问题 一阶矩 二阶矩 可满足性问题 相变分析

原文传递

基于1RSB的正则(k,r)-SAT问题可满足临界 被引量：6

13

作者 周锦程 许道云 卢友军 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2017年第12期7-13,共7页

针对每个变元恰好出现r次且其正、负出现各为r/2次的随机正则(k,r)-SAT问题,结合一阶复本对称破缺理论和随机正则(k,r)-CNF公式解空间的几何结构,分析了通常以解的总数作为一阶矩方法的随机变量时,所得到的随机正则(k,r)-SAT问题可满足... 针对每个变元恰好出现r次且其正、负出现各为r/2次的随机正则(k,r)-SAT问题,结合一阶复本对称破缺理论和随机正则(k,r)-CNF公式解空间的几何结构,分析了通常以解的总数作为一阶矩方法的随机变量时,所得到的随机正则(k,r)-SAT问题可满足临界值上界偏大的本质原因.在此基础上,通过计算可满足相变点附近区域中随机正则(k,r)-CNF公式的解的聚类总数,从而把计算其解的规模转换为计算其解的聚类规模.进一步,通过引入覆盖的定义来表示聚类,并以覆盖总数作为一阶矩方法中的随机变量,结合相关的概率分析,得到了当前该问题可满足临界值点的一个新上界,使得上、下界之间仅有常数1的间隙. 展开更多

关键词 随机正则(k r)-SAT问题 相变性质 1RSB腔域方法 可满足临界 变元

原文传递

改进的模拟退火算法求解规则可满足性问题 被引量：10

14

作者 张九龙 王晓峰 +2 位作者 芦磊 牛鹏飞 程亚南 《现代电子技术》 2022年第5期122-128,共7页

对于随机k-SAT问题,限定每个变元出现的次数恰好出现d次,形成随机规则(k,d)-SAT问题,目前国内外对该问题的相关研究较少,且研究随机规则(k,d)-SAT问题比研究k-SAT问题更为具体。文中给出一种随机规则(k,d)-SAT问题的生成实例模型——RRI... 对于随机k-SAT问题,限定每个变元出现的次数恰好出现d次,形成随机规则(k,d)-SAT问题,目前国内外对该问题的相关研究较少,且研究随机规则(k,d)-SAT问题比研究k-SAT问题更为具体。文中给出一种随机规则(k,d)-SAT问题的生成实例模型——RRIG(N,k,d)模型,并用改进的模拟退火算法SARSAT求解规则随机规则(k,d)-SAT问题。将变元出现次数d加入到扰动策略中,利用变元出现次数和子句间约束关系中的启发信息对候选解中的赋值选择性改动,加快算法收敛至较优解的速度;同时,模拟退火算法中的Metropolis接受准则和改进后的退火策略保证了算法能够有效跳出局部最优解,最后使用RRIG(N,k,d)模型生成不同参数的测试实例,并与其他相关算法进行比较,结果表明SARSAT算法能有效解决规则可满足问题。 展开更多

关键词 模拟退火算法 规则可满足问题 随机正则(k d)-SAT 启发式策略 随机3-SAT问题 Metropolis接受准则 规则可满足性实例生成模型

在线阅读 下载PDF 职称材料

长程阻错的统计物理理论

15

作者 周海军 《物理》 CAS 北大核心 2006年第3期193-196,共4页

一个无序自旋玻璃系统可能有许许多多能量最小态或基态构型.有些格点的自旋可能在所有这些基态中都只取同一个值(这种情况称为自旋凝固).也有另外一种情况出现,即某些格点在一部分基态中自旋取向上而在其余的基态中自旋向下;这样的格点... 一个无序自旋玻璃系统可能有许许多多能量最小态或基态构型.有些格点的自旋可能在所有这些基态中都只取同一个值(这种情况称为自旋凝固).也有另外一种情况出现,即某些格点在一部分基态中自旋取向上而在其余的基态中自旋向下;这样的格点称为未凝固的格点.本文的工作表明,2个或多个未凝固的格点,虽然每个格点的自旋都随着基态的不同而改变,但是有可能某一些特定的自旋取向组合不会出现于任何一基态构型中.这种现象称为长程阻错.本文提出一个新的长程阻错序参量R来定量刻划这种现象,并将这一统计物理理论用于图的最小覆盖和K-SAT等组合优化问题. 展开更多

关键词 自旋玻璃 长程阻错 组合优化 图的覆盖 K—SAT

在线阅读 下载PDF 职称材料