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

摘要

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