一种值域增长约束满足问题上无回溯算法的分析-论文.pdf

《一种值域增长约束满足问题上无回溯算法的分析-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第37卷第3期应用数学学报Vo1．37No．32014年5月ACTAMATHEMATICAEAPPLICATAESINICAM，2014一种值域增长约束满足问题上无回溯算法的分析徐伟臼E京科技大学自动化学院，北京100083)(E—mail：xuwei一225@163．corn)摘要本文研究一种值域增长的约束满足问题模型，称做RA模型．发现无回溯算法在其约束密度较小时(比如对某些参数的模型其密度为满足相变点的25％)解出概率趋于1，能解出时的时间复杂度为多项式时间．关键词约束满足问题；无回溯；算法分析MR(2000)主题分类68Q25；68W40中图分类TP301引言约束满足问题(C

2、SPs)[】通常包含若干变量和若干约束，每个变量有自己的值域，问题的解是能避开所有约束的变量的一组赋值．比如，变量为Xl，X2，每个变量的值域为f0，1，约束为“解不是1=0，X2=0”，“解不是Xl=0，X2=1”，则解为Xl=1，X2=0或z=1，2=1．变量与约束很多时，通常采用计算机解决，用计算机解决约束满足等问题的能力便成为根本的科学问题．约束满足问题也是许多实际问题的模型．常见的约束满足问题有SAT问题[2】j染色问题，自旋玻璃，纠错编码，数独，CSPs标准的A，B，C，D模型【3】_约束满足问题的研究与其他领域有广泛联系．比如与随机图的联系，f41证明了SAT问题的满足

3、性具有突变阈值，其证明过程是先证明随机图上的相关性质，再推广到SAT问题上；在随机图中常见的谱的性质也被应用到CSPs问题上[5]．约束满足问题在统计物理上可看作是一种稀疏自旋玻璃[6]_自旋玻璃中常用的空腔方法[7)8】被用到约束满足问题，取得很好的效果，但其原理与正确性尚未可知，还有待于用数学方法进一步研究．本文2013年7月19日收到．2013年9月25日收到修改稿386应用数学学报37卷算法分析是CSPs一个重要的研究方向．以3一SAT问题为例，『91等分析了完全算法，如证明一些完全算法能在1．618”时间内解决3-SAT，佗为变量个数；f101等分析了规约算法，如证明规约算

4、法在3-SAT约束密度低于，n／时效果很差，为任意小常数；[11]证明一种单元子句算法当约束密度低于2．9时，解出概率大于一个正常数；[12]证明一种纯变量算法在约束密度低于1．63时解出概率趋于1；f131证明随机行走算法在约束密度低于1．63时解出概率趋于1．本文对一种值域增长CSPs上的无回溯算法进行分析，证明其在约束密度小于某值时，解出概率趋于1．许可，李未【l4J于2000年提出了一种值域增长的约束满足问题模型，RB模型，并发现该模型具有良好的理论与应用性质．首先它具有可证明的精确的满足性相变点，其次它是生成难解实例的重要途径[15,16]，该方法生成的难解实例已被广泛应用

5、于竞赛与研究．该模型已被广泛关注和研究，如f17—191等．f201中通过实验发现RB上无回溯算法优于随机行走算法，并对两种算法进行了一些分析．其在分析RB模型上的无回溯算法的表现时，为方便分析，对RB模型进行了微调，微调后称作RA模型．f201已给出k=2时的RA模型无回溯算法解出概率的表达式．本文进一步给出了k值任意时解出概率的表达式，并对表达式进行了放缩，发现约束密度较小时该表达式趋于1．又由于无回溯算法运行时间为多项式时间，从而我们得到了无回溯算法在值域增长的约束满足问题上当约束密度较小时的有效性，它是约束密度较小时的良好算法．2预备知识先给出约束满足问题的RB模型的定义．令

6、k2是整数，r，>0，0

7、约束包含k个变量，共有个可能的约束，令每一个以概率出现．2．对每一个约束，共有Ⅳ个可能的联合赋值，令每一个以概率P属于不协调联合赋值．解是能避免所有约束的赋值，严格表述为在该赋值下中的任意子集的赋值不是不协调联合赋值．解的集合记为，它是DⅣ的一个子集．由于RA模型与RB模型的相似性，RA模型的基本性质可参考RB模型基本的3期徐伟：一种值域增长约束满足问题上无回溯算法的分析387性质．令表示解的个数，X=．容易看到RB模型的均值表示为E(X)=NⅣ(1一p)