0871-50313012025年1月1日1/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法第五章约束满足问题5.1约束满足问题5.2CSP问题的回溯搜索5.3约束满足问题的局部搜索5.4问题的结构0871-50313012025年1月1日2/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法约束满足问题ConstraintSatisfactionProblem,CSP约束满足问题：包含一组变量和一组变量间的约束。变量集合：X1,X2,…,Xn（变量Xi的值域Di）约束集合：C1,C2,…,Cn找到所有变量的一个（或多个）赋值，使所有约束都得到满足。0871-50313012025年1月1日3/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法约束：用于描述对象的性质、相互关系、任务要求、目标…一元谓词序关系语言形如x-y>c的方程线性方程和不等式布尔组合代数和三角方程约束表示易于理解、编码和实现0871-50313012025年1月1日4/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法问题的一个状态由对一些或全部变量的赋值定义例如：{Xi=vi,Xj=vj,…}相容的(合法的)赋值：不违反约束条件完全赋值：每个变量都参与CSP的解是满足所有约束的完全赋值约束满足问题0871-50313012025年1月1日5/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法约束满足问题变量集合：WA,NT,Q,NSW,V,SA,T值域:Di={red,green,blue}约束：相邻区域颜色不同例如,WA≠NT,或(WA,NT)组合{(red,green),(red,blue),(green,red),(green,blue),(blue,red),(blue,green)}0871-50313012025年1月1日6/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法e.g.,WA=red,NT=green,Q=red,NSW=green,V=red,SA=blue,T=green约束满足问题0871-50313012025年1月1日7/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法约束图：节点--变量，弧--约束约束满足问题0871-50313012025年1月1日8/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法CSP问题的特点CSP问题的增量形式化：初始状态：空的赋值{}；后继函数：可以给任何未赋值的变量赋一值，且和先前赋值的变量不冲突目标测试：检验当前赋值是否完全路径耗散：每一步耗散为常数完全状态形式化：每个状态是一个满足或不满足约束条件的完全赋值。0871-50313012025年1月1日9/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法值域：有限值域无限值域：例如工作安排问题使用约束语言描述约束例如：StartJob1+5≤StartJob3约束类型：一元约束：只限制单个变量的取值，例如：SA≠green二元约束：和两个变量有关，例如：SA≠WA可表示为约束图。变量类型：离散型连续型：线性规划问题CSP问题的特点0871-50313012025年1月1日10/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法高阶约束：涉及三个或更多变量例：密码算术可用超约束图表示。变量：FTUWROX1X2X3值域：{0,1,2,3,4,5,6,7,8,9}约束：Alldiff(F,T,U,W,R,O)•O+O=R+10·X1•X1+W+W=U+10·X2•X2+T+T=O+10·X3•X3=F••高阶的、有限值域的约束可简化为一个二元约束集合：F≠T，F≠U…CSP问题的特点0871-50313012025年1月1日11/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法绝对约束:任何违反规则的都排除在解之外偏好约束：指出哪些解是更偏好的CSP问题的特点0871-50313012025年1月1日12/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法CSP问题的回溯搜索CSP问题的每一个解必须有一个完全赋值，如有n个变量，解的深度为n搜索树则扩展到n.回溯搜索：深度有限搜索，一次为一个变量赋值1、为一个新生成的变量选择赋值；2、比较，合理吗？3、不合理，回溯0871-50313012025年1月1日13/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法0871-50313012025年1月1日14/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法0871-50313012025年1月1日15/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法0871-50313012025年1月1日16/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法0871-50313012025年1月1日17/16jhzhang@ynu.edu.cn信息学院人工智能——一种现代方法0871-50313012025年1...
