文档介绍：(ConstraintSatisfactionProblem,简称CSP)包含一组变量与一组变量间的约束。变量表示领域参数,每个变量都有一个固定的值域。约束满足问题的目标就是找到所有变量的一个(或多个)赋值,使所有约束都得到满足。目前约束推理的研究主要集中在两个方面:约束搜索,-Top(P)1f:=thenullassignment2returnBacktracking(f,P)Backtracking(f,P)1iffisatotalassignmentofthevariablesinP2answer:=f3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6foreachvaluexwhileanswer=Unsat7f(v):=x8iffsatisfiestheconstraintsinP9answer:=Backtracking(f,P)10returnanswer提高回溯算法的效率受约束最多的变量:选择合法值最少的变量选择产生约束最多的变量:约束产生最多的变量—选择使其他变量受到约束最多的变量给定一个变量,选择产生约束最少的值:选择使剩余的变量不合法值最少的值前置检测:追踪没有赋值变量的剩余合法值当有变量没有任何合法值的时候则停止搜索约束传播Constraintpropagation提前检测可以将信息从已经赋值变量传递到没有赋值的变量,但是不能提前检测所有的失败约束传播可以反复地强制局部约束简单的约束传播方式,可以保证每条弧具有一致性弧viàvj是一致的当且仅当,对于vi当前域中的每个值x存在vj的当前域中的某值y使得弧viàvj满足约束如果vi失去了一个值,(vi,vj)1DELETE¬false; 2foreachxÎDido 3ifthereisnosuchyÎDj4suchthat(x,y)isconsistent,5then 6 deletexfromDi; 7 DELETE¬true; 8endif 9endfor 10returnDELETE; 11endREVISEAC-112repeat 3CHANGE¬false;4foreach(vi,vj)ÎQdoCHANGE¬REVISE(vi,vj)ÈCHANGE;6endfor;7untilnot(CHANGE);8endAC-1AC-31;2WhileQnotempty 3Selectanddeleteanyarc(vi,vj)fromQ;4If(REVISE(vi,vj))ThenQ¬{(vs,vi)suchthat(vs,vi)Îarcs(G),s¹i,s¹j};6endfor;7endwhile;8endAC-34..局部搜索求解CSPs爬山算法Hill--Top(P)1f:=thenullassignment2<answer,conflict-set>:=Backjumping(f,P)3returnanswerBackjumping(f,P)1iffisatotalassignmentofthevariablesinP2answer:=<f,Æ>3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6conflict-set:=Æ7foreachvalue8f(v):=x9iffsatisfiestheconstraintsinP10<answer,new-conflicts>:=Backjumping(f,P)11else12new-conflicts:=thesetofvariablesinaviolatedconstraint13ifanswer¹Unsat14return<answer,Æ>15elseifvÏnew-conflicts16return<Unsat,new-conflicts>17else18conflict-set:=conflict-setÈ(new-conflicts{v})19return<Unsat,conflict-set>案例推理概述在基于案例推理(Case-BasedReasoning,简称CBR)中,把当前所面临的问题或情况称为目标案例(targetcase),而把记忆的问题或情况称为源案例(basecase)。粗略地说,基于案例推理就是由目标案例的提示而获得记