本文共 3900 字，大约阅读时间需要 13 分钟。

人智导（四）：约束满足问题

约束满足问题(Constraint Satisfaction Problem)

• 一种结构化的、简单而标准模式的问题表示
• 状态被描述为一系列变量$X_i$（对应的值域为$D_i$）
• 目标测试：一个约束集，描述这些变量或子集允许的取值

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$对应的值域为$D_i$；$C_i$为一些变量间的约束关系。
• 一个状态：部分或全部变量的一个赋值
• 完全赋值：每个变量都进行赋值（完全状态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}
• 约束：相邻区域必须用不同颜色标识
  • 隐式描述：$WA\ne 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_{ij}$
• 值域： { 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 连续变量（现实世界中许多问题涉及实数型变量）
• 约束种类：
  • 一元约束：如$SA\ne green$
  • 二元约束：如$SA\ne WA$
  • 多元约束：涉及三个以上变量的高阶约束
• 目标测试：检查是否满足所有约束条件

CSP问题的解决

标准搜索方法解决CSP问题

• CSP问题表示：状态(state)通过变量赋值来定义
  • 初始状态：没有任何赋值{}
  • 后继函数：对一个未有值的变量赋值，不违反约束条件
  • 目标测试：当前状态赋值已完备，并且满足所有约束
  • 路径代价可把每一步代价作为常数（例如取值为1）
• CSP问题的解：必须是一个满足约束的完全赋值，若有n个变量，n也就是解的路径深度

回溯搜索算法

思路：

• 无信息搜索算法解决CSP
• 一次只给一个变量赋值
• 过程中每步都检测是否满足约束（不与之前赋值相冲突）
  算法：

Function BACKTRACKING-SEARCH (csp) returns solution or failure	return RECURSIVE-BACKTRACKING({},csp)Function RECURSIVE-BACKTRACKING(assignment, csp) returns solution or failure	if assignment is complete then return assignment	var <--- SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment, csp)	for each value in ORDER-DOMAIN-VALUES(var assignment, csp) do		if value is consistent with assignment given CONSTRAINTS[csp] then			add{var = value} to assignment			result <--- RECURSIVE-BACKTRACKING(assignment, csp)			if result != failure then return result			remove {var = value} from assignment	return failure

深度优先搜索+有序变量赋值+违反约束即失败

启发式：优先选择合法取值最少变量（最受约束变量） 标准问题求解与完全状态问题对比

• CSP标准的问题求解：如何发现动作序列，一步一步地达到目标
  • 看作是规划(plan)问题
  • 达到目标的途径是重要的
• CSP解决完全状态问题：如何发现满足约束的完全赋值
  • 看作是识别(Identification)问题
  • 目标本身是重要的，而途径不是

完全状态问题

局部搜索：问题的完整状态(complete-state)形式表示

• 初始状态：每个变量均被赋值
• 后继状态：每次改变一个变量的值
• 直到发现满足约束的解

如下图：

初始状态违反了约束，采用局部搜索来消除违反的约束 算法：最小冲突算法Min-Conflict

Function MIN-CONFLICTS(csp, max_steps) returns a solution or failure	inputs:csp	       max_steps //最大尝试次数	current <--- an initial complete assignment for csp	for i=1 to max_steps do		if current is a solution for csp then return current		var <--- a randomly chosen conflicted variable from csp.VARIABLES		value <--- the value v for var that minimizes CONFLICTS(var, v, current, csp)		set var = value in current	return failure

最小冲突算法：每一步搜索为一个变量赋予新值，启发式是新值必须与其他变量相冲突的数目最小化。

爬山或模拟退火等局部搜素可以被应用于目标优化。

总结

局部搜索问题

• 局部搜索：只关心目标状态本身，而非达到目标的途径
• 仅需少量存储空间，适于处理大规模的、甚至是连续状态空间的目标搜索状态
• 完全状态(complete state)的形式化描述问题，诸如布局、调度、最优化问题等方面应用
• 爬山搜索算法、模拟退火算法、局部集束算法
  约束满足问题
• 从数学意义上定义一种简单而标准模式的问题形式化表示
• 完全状态(complete state)的形式化，状态由一组变量表示
• 约束满足问题求解：回溯搜索（标准搜索），最小冲突搜索（局部搜索）

转载地址：http://fdzai.baihongyu.com/