0871-5031301 * 1 / 信 息 学 院人工智能 一种现代方法第五章 约束满足问题5.1 约束满足问题 5.2 CSP问题的回溯搜索5.3 约束满足问题的局部搜索5.4 问题的结构 0871-5031301 * 2 / 信 息 学 院人工智能 一种现代方法约束满足问题 Constraint Satisfaction Problem, CSP约束满足问题:包含一组变量和一组变量间的约束。变量集合:X1, X2,Xn (变量Xi 的值域Di )约束集合:C1, C2,Cn 找到所有变量的一个(或多个)赋值,使所有约束都得到满足。0871-5031301 * 3 / 信 息 学 院人工智能 一种现代方法约束:用于描述对象的性质、相互关系、任务要求、目标一元谓词序关系语言形如x-yc 的方程线性方程和不等式布尔组合代数和三角方程约束表示易于理解、编码和实现0871-5031301 * 4 / 信 息 学 院人工智能 一种现代方法问题的一个状态由对一些或全部变量的赋值定义例如:Xi=vi, Xj=vj,相容的( 合法的) 赋值:不违反约束条件完全赋值:每个变量都参与CSP 的解是满足