约束满足问题人工智能课程.ppt

文档介绍：第五章、约束满足问题
Ch3&4：通过搜索状态空间求解问题
把状态看作一个黑盒子，只能由问题特定的例行程序来访问—后继函数、启发函数和目标测试。
约束满足问题：利用状态的结构以及通用的、而不是问题特定的启发式来定义搜索算法。
精选ppt
1
第五章、约束满足问题
约束满足问题（CSP）
CSP问题的回溯搜索
约束满足问题的局部搜索
问题的结构
精选ppt
2
约束满足问题
CSP由一个变量集合和一个约束集合组成
问题的一个状态是由对一些或全部变量的一个赋值定义的
完全赋值：每个变量都参与的赋值
问题的解是满足所有约束的完全赋值，或更进一步，使目标函数最大化。
精选ppt
3
例子：澳大利亚地图的染色
对每个区域染上红、绿或蓝色，使得没有相邻的区域颜色相同。
精选ppt
4
将问题形式化为CSP
精选ppt
5
CSP问题的增量形式化
初始状态
后继函数：给任何未赋值的变量赋值（满足约束）
目标测试
路径耗散
精选ppt
6
CSP（续）
经常用深度优先搜索算法求解
变量
离散或连续
值域：有限或无限
约束
线性或非线性
一元或多元：通过引入辅助变量，转为二元约束。
绝对vs偏好
精选ppt
7
第五章、约束满足问题
约束满足问题（CSP）
CSP问题的回溯搜索
约束满足问题的局部搜索
问题的结构
精选ppt
8
CSP问题的回溯搜索
一次为一个变量选择值，当没合法值可以再赋给该变量时就回溯。
精选ppt
9
一个简单的回溯算法
以递归深度优先算法为模型
精选ppt
10