北大公开课-人工智能基础 35 约束满足问题 CSPs

约束满足问题是一类问题的统称

标准搜索的状态是一个节点，节点对应某一个特定的状态，节点是不可分割的。

约束满足问题CSP的状态，是一系列因子及其状态结构的组合。

约束满足问题，常常需要启发式（历史经验）与组合搜索方法

一个CSP通常包括三元组

变量x，变量的集合

范畴D，（x对应v的集合）

约束C，约束的集合

地图着色问题：

变量x，相当于每个州的名称和位置

范畴D，相当于x的赋值v的集合，红、绿、蓝

约束C，相邻两个州的颜色不能一致。

四色定理的计算机解决方法

作业车间调度，约束满足问题

任务互相之间的约束

CSP的不同类型

有限空间/无限空间

离散/连续

n元约束

勇于解决算式迷问题

算式迷的举例

x变量，每一个字母的赋值

D范畴，每一个字母可能的值，（0~9）

D约束，几个字母之间满足的等式

约束满足问题，也常常用来处理决策的问题