Video在线视频

那么这一章我们来讲述一下约束满足问题

那么约束满足问题它简称CSP

也就是说它就是Constraint satisfaction problems
的英文简写

那么我们来看一下什么叫约束满足问题

前面我们讲过的那种标准的搜索算法它的问题的
形式化状态是一个黑盒

也就是说状态里面的变量

或者是说里面是怎么定义的你是不知道的

那么你只能通过这个后续函数

也就是说这个产生后续的后续函数（动作函数）

以及启发式函数这个是用来评估这个状态好坏的
这么一个函数

以及这个目标测试来测试这个状态是不是一个目
标状态等等

来访问这个状态 那么状态内部你是不可以去乱改
变的

只能通过这些函数来访问这个状态

那么对于这个约束满足问题来讲

它这个状态的描述就不是定义成一个黑盒

而是将这个状态由多个变量来定义

也就是说我们是通过一组变量来定义这个状态的

那么这个每一个变量它有一个取值范围的

也就是说这个取值范围呢

变量Xi的取值范围就用Di表示

也就是说有一个domain域的意思

然后这个目标测试我们也是就是通过一组约束来
定义的

也就是说如果这个状态它满足这组约束 我就认为
它是一个目标状态

那么这个约束是一种什么类型的约束呢

这个约束是用来指定一组变量比如说一组变量或
者变量的子集

它应该怎么样赋值

也就是说这些变量值之间应该符合怎么样一种关
系

这样子的一个定义来定义变量之间的一种约束

也就是说规定它们之间值应该符合一种什么样的
关系

那么这个就是我们的约束满足问题

它的问题形式化方法和前面那种我们用于标准搜
索问题的形式化是不太一样的

那么我们有一个约束满足问题的例子

就是这个给地图上色

那么地图上色我们知道

为了便于区分不同的区域 相邻的区域肯定是不能
涂相同的颜色的

但是我们的颜色的种类又只有有限种

比如说像这个是一个澳大利亚的地图

那么它总共有1、2.....7，七个区域

那么我们就用七个变量来描述一种状态

那么这个变量它的取值 也就是说我规定它只能涂
红绿蓝三种颜色中的一种

也就是说每一个区域都只能涂红绿蓝中的一种颜
色

那么你要用三种颜色把这个地图上色

使得这个不同的区域具有不同的颜色

那么这就是一个约束满足问题

那么我们这个状态就由这七个变量来表示

那么七个变量它们的取值范围我们也规定好

然后约束呢 我们就是这么一种约束

就是规定相邻的区域（变量）不能上同样的颜色

这就是它的约束

那么只要你找到一种给这七个变量赋值的方案不
违反这个约束

那么就认为找到了这个问题的解

那么这个就是叫做约束满足问题

那么像这个就是一个问题的解

那么它就用三种颜色把这个七个区域都赋了值

那么都涂上了颜色 并且任何相邻的区域都具有不
同的颜色

那么它是符合这个约束的

所以这么一个完整的赋值就是约束满足问题的一
个解

也就是说约束满足问题的解 它要求必须是完整的

所谓完整的意思就是所有的变量都赋了值

并且这些赋值是不违反约束的

也就是说它是符合约束的一种赋值

那么就叫做约束满足问题的一个解

像这个就是，赋值如ppt所示

那么任何相邻的区域都没有相同的颜色

所以这个是一个问题的解

那么对于这个约束满足问题的话

约束的表达方法呢

我们可以用图的数据结构来表示这种约束

便于算法进行约束的检查、目标测试等等

那么我们的约束有

一般来说二元约束比较多

也就是说我们这个二元约束满足问题里面

它这个约束是二元约束的 也就是每个约束都关联
两个变量

也就是说它的约束是一个二元关系

也就是说它只对两个变量的值进行一个限制 每一
个约束 也就是说每一组约束

那么对于这种二元约束满足问题 它的约束就可以
用这种图结构来表达出来

也就是说我用结点来表示变量

然后用这个边或者说叫做弧来表示这个约束

那么这个弧或者说边的话 它都是连接两个结点的

也就是说这条弧它表示的是约束WA和NT这两个变
量

也就是说这个约束呢就是约束WA和NT不能取相同
的值

这个约束图就是我们刚才这个澳大利亚地图上色
的这么一个问题的约束图

那么它总共有七个区域变量

那么相邻的区域之间它才会存在约束

所以它相邻的区域之间就有一条约束弧连起来

所以它总共就是有1、2.....9，总共有9个约束弧

也就是说其实上整个的约束集是有9个约束的

那么你最后的赋值一定要满足这九个约束

那么这个是用约束图的方法来表示约束

那么我们约束满足问题里面我们知道这个状态是
用变量来表示的

那么我们的变量的类型也有很多种

比如说有这种离散型的变量

那么离散型的变量有它的取值范围是有限的

也可能这种变量的取值范围是无限的

那么对于有限的这种离散变量

那么比如说总共有n个变量来描述这个状态

那么比如说每一个变量它取值范围 它的域的大小
最多就是d

也就是说它们每一个变量可能的取值最多就是d

那么整个的这个状态呢 它可以描述的状态有多少
种呢

就是d的n次方种

也就是说整个的状态空间其实上就是这么一个数
量级

也就是说因为每一个变量都可能取d种不同的值

都可能赋d种不同的值

n个d相乘，那么就是d的n次方

那么这个是离散变量 并且这种离散变量的取值是
有限的

那么对于这种问题这个状态空间都是非常非常的
大的

也就是说这种问题都是非常难解的

那么如果这个离散变量是无限的

也就是说它的取值范围是无限种可能

比如说我们现实中的作业调动问题

那么变量就是每一道工序的起始和结束日期

那么这是它的变量

那么我们的约束一般就是 比如说

第三道工序必须是在第一道工序开始五天之后进
行

那么这个是这种约束的表示方法

那么像这种起始和结束日期它可能的取值就是有
无限多种的

但这个日期是离散的 比如说今天、明天、后天

它指的是这种日期

那么这个约束满足问题的变量还有可能是这种连
续的变量

比如说这个哈勃太空望远镜观测的起始和结束时
间

那么这个时间的可以是几秒毫秒微妙这样下去的

因为它要非常精确的时间

那么这个的话就是一种变量它是取这个连续的值

不是取这种离散的值

也就是说这是约束满足问题的变量可以有不同的
类型

那么这个约束的类型也可以有很多种

那么我们前面讲的例子叫二元约束

那么其实这个变量上的约束可以是一元约束

那么一元约束也就是说只涉及到一个变量

只对一个变量进行约束

比如说我规定这个SA就不能涂绿色

那么就是二元约束就是比较常见的涉及到两个变
量

也就是说规定SA和WA不能取相同的值

就是相邻区域不能涂相同的颜色

那么还有就是一些高阶约束

它就会涉及到三个以上的变量

比如说这个密码算术约束

那么像这个例子就是一个密码算术

这个密码算术的意思就是我这个里面有很多未知
的数字符号变量

那么要你通过它们之间的一种关系

也就是说要满足这种约束 要你来猜出这种变量的
取值

那么其实上这种类型就是类似于解方程的意思

其实上它就是一个约束满足问题

那么我们看到也就是说对于这么一个问题呢

我们这个状态就用九个变量来表示

就是这个F、T、U、W、R、O、X1、X2、X3来表
示

那么大家看到这里的约束图它不单单有这个结点

这个结点我们知道小圆圈表示的结点是用来表示
这个描述状态变量的

那么还有一些辅助结点是用这个小正方形表示的

那么这种为什么它要引入这个呢 也就是这里面涉
及到的约束是高阶约束 也就是三阶以上的

那么这个时候它就需要引入这个辅助结点来辅助
它表示这个约束

那么像这个就是一个约束结点

这个约束涉及到1、2....6，这六个变量

F、T、U、W、R、O

也就是说对这六个变量进行约束

那么这个约束结点就是对这两个变量进行约束

这个约束结点就是对四个变量进行约束

那么这个约束节点表示对四个变量进行约束

这个约束节点表示对三个变量进行约束

所以高阶约束满足问题的约束图里面除了有结点
和约束弧

那么还会有约束结点来辅助表示它约束的是哪些
变量 这么一个意思

所以它和前面的约束图是不太一样的

那么这里的话总共有5个约束结点

那么他就意味着它有五个约束

那么每一个约束结点对应着一个约束

比如说像这个约束结点就对应这个约束

它的约束意思就是这六个变量都不能相同

F、T、U、W、R、O都不能相同 不能取相同的值

接下来的每一个 像这个

这个就是对F和X3进行约束

那么它其实上就是对应的这条约束 要求X3=F

这个是它的约束

然后这个约束是对T、O、X3、X2进行约束

那就是对应的这条约束

就是X2+T+T=O+10*X3

那么这个约束是对U、W、X2、X1进行约束

那它对应的就是这个约束

然后这个是对R、O、X1进行约束

所以它是对应的是这个约束式子

那么五个约束结点对应成五个约束

那么它要求你找到一种赋值方案

并且这九个变量的取值范围都只能取0~9的数字

只能填0~9

那么要求你对这九个变量进行赋值 填数字 要满足
这五个约束

那么这个就是一个典型的密码算术问题

那么这么一个约束满足问题就是一个高阶约束问
题