求解MAX-CNF问题的一种随机近似算法

• 作者: 曾文华 李伟
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: MAX-CNF 可满足问题 近似算法 相变现象
• 年，卷（期）: 2006,（34）
• 所属期刊栏目: 学术探讨
• 页码范围: 39-41,69
• 页数: 4页
• 分类号: TP301.6
• 字数: 3822字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2006.34.012

摘要

已有的Johnson算法是求解组合问题的一种随机近似算法,可以用于求解MAX-CNF问题.基于该算法,提出新的随机近似算法RCNF求解MAX-CNF问题.概率推导和实验数值均表明,RCNF具有良好的近似比和稳定的性能.在构成难可满足问题的CNF实例上,将新算法与演化算法结合,进-步提出扩展算法E-RCNF.扩展算法利用演化算法的并行性,可以在较短时间内,简单有效地求出最多可满足子句数的近似值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李伟		1	0	0.0	0.0
2	曾文华		5	22	3.0	4.0