人智导（四）：约束满足问题
人智导（四）：约束满足问题
约束满足问题(Constraint Satisfaction Problem)
- 一种结构化的、简单而标准模式的问题表示
- 状态被描述为一系列变量 X i X_i Xi（对应的值域为 D i D_i Di）
- 目标测试：一个约束集，描述这些变量或子集允许的取值
CSP问题的定义
约束满足问题的定义：
- 变量集合： { X 1 , X 2 , … , X n } {X_1,X_2,dots ,X_n} {X1,X2,…,Xn}；约束集合： { C 1 , C 2 , … , C n } {C_1,C_2,dots ,C_n} {C1,C2,…,Cn}。 X i X_i Xi对应的值域为 D i D_i Di； C i C_i Ci为一些变量间的约束关系。
- 一个状态：部分或全部变量的一个赋值
- 完全赋值：每个变量都进行赋值（完全状态complete state）
- 问题的解：满足所有约束的完全赋值
约束满足问题：地图着色(map coloring)
如图
- 状态变量：WT, NT, Q, NSW, V, SA, T
- 值域： D = { r e d , g r e e n , b l u e } D={red,~green,~blue} D={red, green, blue}
- 约束：相邻区域必须用不同颜色标识
- 隐式描述： W A ≠ N T WAne NT WA=NT
- 显式描述： ( W A , N T ) ∈ { ( r e d , g r e e n ) , ( r e d , b l u e ) , … } (WA,NT)in {(red,~green),~(red,~blue),dots} (WA,NT)∈{(red, green), (red, blue),…}
- 问题的解是满足约束的变量赋值，如：
{ W A = r e d , N T = g r e e n , Q = − r e d , N S W = g r e e n , V = r e d , S A = b l u e , T = g r e e n } {WA=red,~NT=green,~Q=-red,~NSW=green,~V=red,~SA=blue,~T=green} {WA=red, NT=green, Q=−red, NSW=green, V=red, SA=blue, T=green}
约束满足问题：八皇后问题
约束规则：同一行或同一列、或统一斜线上不能有两个或以上的Queens
形式化描述：
- 变量： X i j X_{ij} Xij
- 值域： { 0 , 1 } {0,1} {0,1}
- 约束：
- ∀ i , j , k ( X i j , X i k ) ∈ { ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 0 ) } forall i,j,k (X_{ij},X_{ik})in {(0,0),(0,1),(1,0)} ∀i,j,k(Xij,Xik)∈{(0,0),(0,1),(1,0)}
- ∀ i , j , k ( X i j , X k j ) ∈ { ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 0 ) } forall i,j,k (X_{ij},X_{kj})in {(0,0),(0,1),(1,0)} ∀i,j,k(Xij,Xkj)∈{(0,0),(0,1),(1,0)}
- ∀ i , j , k ( X i j , X i + k , j + k ) ∈ { ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 0 ) } forall i,j,k (X_{ij},X_{i+k,j+k})in {(0,0),(0,1),(1,0)} ∀i,j,k(Xij,Xi+k,j+k)∈{(0,0),(0,1),(1,0)}
- ∀ i , j , k ( X i j , X i + k , j − k ) ∈ { ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 0 ) } forall i,j,k (X_{ij},X_{i+k,j-k})in {(0,0),(0,1),(1,0)} ∀i,j,k(Xij,Xi+k,j−k)∈{(0,0),(0,1),(1,0)}
约束满足中的变量与约束
- 变量种类：离散变量 vs 连续变量（现实世界中许多问题涉及实数型变量）
- 约束种类：
- 一元约束：如 S A ≠ g r e e n SAne green SA=green
- 二元约束：如 S A ≠ W A SAne WA SA=WA
- 多元约束：涉及三个以上变量的高阶约束
- 目标测试：检查是否满足所有约束条件
CSP问题的解决
标准搜索方法解决CSP问题
- CSP问题表示：状态(state)通过变量赋值来定义
- 初始状态：没有任何赋值{}
- 后继函数：对一个未有值的变量赋值，不违反约束条件
- 目标测试：当前状态赋值已完备，并且满足所有约束
- 路径代价可把每一步代价作为常数（例如取值为1）
- CSP问题的解：必须是一个满足约束的完全赋值，若有n个变量，n也就是解的路径深度
回溯搜索算法
思路：
- 无信息搜索算法解决CSP
- 一次只给一个变量赋值
- 过程中每步都检测是否满足约束（不与之前赋值相冲突）
算法：
Function BACKTRACKING-SEARCH (csp) returns solution or failurereturn RECURSIVE-BACKTRACKING({},csp)
Function RECURSIVE-BACKTRACKING(assignment, csp) returns solution or failureif assignment is complete then return assignmentvar <--- SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment, csp)for each value in ORDER-DOMAIN-VALUES(var assignment, csp) doif value is consistent with assignment given CONSTRAINTS[csp] thenadd{var = value} to assignmentresult <--- RECURSIVE-BACKTRACKING(assignment, csp)if result != failure then return resultremove {var = value} from assignmentreturn failure
深度优先搜索+有序变量赋值+违反约束即失败
启发式：优先选择合法取值最少变量（最受约束变量）
标准问题求解与完全状态问题对比
- CSP标准的问题求解：如何发现动作序列，一步一步地达到目标
- CSP解决完全状态问题：如何发现满足约束的完全赋值
- 看作是识别(Identification)问题
- 目标本身是重要的，而途径不是
完全状态问题
局部搜索：问题的完整状态(complete-state)形式表示
- 初始状态：每个变量均被赋值
- 后继状态：每次改变一个变量的值
- 直到发现满足约束的解
如下图：
初始状态违反了约束，采用局部搜索来消除违反的约束
算法：最小冲突算法Min-Conflict
Function MIN-CONFLICTS(csp, max_steps) returns a solution or failureinputs:cspmax_steps //最大尝试次数current <--- an initial complete assignment for cspfor i=1 to max_steps doif current is a solution for csp then return currentvar <--- a randomly chosen conflicted variable from csp.VARIABLESvalue <--- the value v for var that minimizes CONFLICTS(var, v, current, csp)set var = value in currentreturn failure
最小冲突算法：每一步搜索为一个变量赋予新值，启发式是新值必须与其他变量相冲突的数目最小化。
爬山或模拟退火等局部搜素可以被应用于目标优化。
总结
局部搜索问题
- 局部搜索：只关心目标状态本身，而非达到目标的途径
- 仅需少量存储空间，适于处理大规模的、甚至是连续状态空间的目标搜索状态
- 完全状态(complete state)的形式化描述问题，诸如布局、调度、最优化问题等方面应用
- 爬山搜索算法、模拟退火算法、局部集束算法
约束满足问题 - 从数学意义上定义一种简单而标准模式的问题形式化表示
- 完全状态(complete state)的形式化，状态由一组变量表示
- 约束满足问题求解：回溯搜索（标准搜索），最小冲突搜索（局部搜索）
