带相关系数的SAT问题的局部搜索算法
本文提出了一个基于动态子句定权的SAT问题的局部搜索算法RCSAT.通过引入子句相关系数的概念,将算法中子句权重分为两个部分,静态部分为该子句的相关系数,在求解过程中保持不变;而动态部分为通常意义上的子句权重,反映着求解时该子句可满足的难易程度.随着求解的进行,动态权重需要不断更新以引导系统脱离局部最优.本文也给出了动态权重的更新算法.对一些SAT基准问题的求解实验表明,与现有算法相比,这个算法能够有效地减少求解某些问题的翻转次数,获得较好的求解性能.
局部搜索算法 SAT 相关系数 翻转次数 可满足性问题 权重
唐屹
广州大学理学院数学系(广州)
国内会议
北京
中文
63-67
2003-11-01（万方平台首次上网日期，不代表论文的发表时间）