人工智能复习总结.docx

文档介绍：约束推理

约束满足问题(Constraint Satisfaction Problem, 简称CSP) 包含一组变量与一组变量间的约束。变量表示领域参数,每个变量都有一个固定的值域。约束满足问题的目标就是找到所有变量的一个(或多个)赋值,使所有约束都得到满足。
目前约束推理的研究主要集中在两个方面:约束搜索,约束语言

Backtracking-Top(P)
1 f := the null assignment
2 return Backtracking(f,P)
Backtracking(f,P)
1 if f is a total assignment of the variables in P
2 answer := f
3 else
4 v := some variable in P that is not yet assigned a value
by f
5 answer := Unsat
6 for each value x while answer = Unsat
7 f(v) := x
8 if f satisfies the constraints in P
9 answer := Backtracking(f,P)
10 return answer
提高回溯算法的效率
受约束最多的变量:选择合法值最少的变量
选择产生约束最多的变量:约束产生最多的变量—选择使其他变量受到约束最多的变量
给定一个变量, 选择产生约束最少的值:选择使剩余的变量不合法值最少的值
前置检测:
追踪没有赋值变量的剩余合法值
当有变量没有任何合法值的时候则停止搜索
约束传播 Constraint propagation
提前检测可以将信息从已经赋值变量传递到没有赋值的变量,但是不能提前检测所有的失败
约束传播可以反复地强制局部约束
简单的约束传播方式,可以保证每条弧具有一致性
弧viàvj 是一致的当且仅当, 对于vi 当前域中的每个值x存在vj的当前域中的某值y使得弧viàvj满足约束
如果 vi失去了一个值,那么 vi 的邻居需要重新检测
弧一致性可以在提前检测之前发现失败
可以作为赋值的前处理或者后处理

REVISE(vi,vj)
1 DELETE ¬ false;
2 for each x Î Di do
3 if there is no such y Î Dj
4 such that(x, y) is consistent,
5 then
6 delete x from Di;
7 DELETE ¬ true;
8 endif
9 endfor
10 return DELETE;
11 end REVISE
AC-1
1
2 repeat
3 CHANGE ¬ false;
4 for each (vi, vj) Î Q do
CHANGE ¬ REVISE(vi, vj) È CHANGE;
6 endfor;
7 until not(CHANGE);
8 end AC-1
AC-3
1 ;
2 While Q not empty
3 Select and delete any arc(vi, vj) from Q;
4 If (REVISE(vi,vj))
Then Q ¬ {(vs, vi) such that (vs,vi)Îarcs(G),
s¹i, s¹j};
6 endfor;
7 endwhile;
8 end AC-3
4..局部搜索求解CSPs
爬山算法 Hill-climbing
模拟退火 Simulated Annealing

Backjumping-Top(P)
1 f := the null assignment
2 <answer, conflict-set> := Backjumping(f,P)
3 return answer
Backjumping(f,P)
1 if f is a total assignment of the variables in P
2 answer := <f,Æ>
3 else
4 v := some variable in P that is not yet assigned a value
by f
5 answer := Unsat
6 conflict-set := Æ
7 for each value
8 f(v) := x
9 if f satisfies the constraints