值域增长约束满足问题的无回溯与随机行走策略的算法复杂性分析

• 作者: 巩馥洲 徐伟
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 无回溯 随机行走 算法复杂性 RB模型 约束满足问题
• 年，卷（期）: 2014,（4）
• 所属期刊栏目: 人工智能
• 页码范围: 205-210
• 页数: 6页
• 分类号: TP30
• 字数: 6158字
• 语种: 中文

摘要

值域增长的约束满足问题模型是计算复杂性理论中一类重要的实际问题模型,针对解决这类问题的算法研究仍然很少.通过研究RB模型这一典型的值域增长约束满足问题,发现当问题规模很大时,无回溯策略比随机行走策略更加有效.这与典型的值域确定的约束满足问题如SAT问题不同,是值域增长的约束满足问题所特有的性质.通过实验研究了两种策略的表现,并进一步对两种策略的表现进行了分析.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	巩馥洲	中国科学院数学与系统科学研究院应用数学研究所	9	38	4.0	6.0
2	徐伟	北京科技大学自动化学院	8	7	2.0	2.0