《E约束满足》-课件.pptVIP

约束满足问题 (CSP) Constraint Satisfaction Problems (CSP)(对于困难的决策，我们将推迟到它变得容易的时候再做决定)  RN: Chap. 5 我们想做些什么？ 有哪些信誉好的足球投注网站技术通常按照一个任意的次序对可能进行选择，一般很少有效的信息能够帮助如何进行选择 在许多问题中，状态的到达与进行选择的次序无关（“可交换”） ，即采取不同的次序进行选择也一样可以到达同一个状态 那能否通过选定某种适合的选择次序能够更有效的解决这些问题呢？甚至可以避免进行选择？ 约束传播Constraint Propagation 将一个皇后放入到一个方格里 移去所有可能攻击到的方格 Constraint Propagation Constraint Propagation Constraint Propagation Constraint Propagation Constraint Propagation Constraint Propagation Constraint Propagation Constraint Propagation 我们需要些什么？ 后继函数与目标测试 还需要: 通过约束传播（ propagate the constraints ）信息，比如通过对一个皇后位置的约束来影响其他皇后的位置 提前的失败测试（failure test） 约束的清晰表示 约束传播算法 约束满足问题 (CSP) Constraint Satisfaction Problem (CSP) 变量的集合 variables {X1, X2, …, Xn} 每一个变量Xi所有可能的取值，构成该变量的值域Di；通常Di是有限的 约束的集合 constraints {C1, C2, …, Cp} 每个约束描述了一个变量子集与特定的某些值合法的结合对应关系 目标: 每一个变量都得到了一个赋值，且所有的约束得到满足 地图着色问题 8-皇后问题 8 个变量 Xi, i = 1 to 8 每个变量的值域均为: {1,2,…,8} 约束表示为如下形式: Xi = k ? Xj ? k for all j = 1 to 8, j?i 对角线也是相同的约束 Street Puzzle（课本习题5.13） Street Puzzle Street Puzzle Street Puzzle Street Puzzle Street Puzzle 有限CSP vs. 无限CSPFinite vs. Infinite CSP 有限CSP : 每个变量的值域有有限个值 无限CSP : 一些或所有的变量的值域是无限的E.g., 实数线性规划: 本课程只讨论有限CSP CSP 描述为有哪些信誉好的足球投注网站问题 n个变量 X1, ..., Xn 合法赋值 : {Xi1 ? vi1, ..., Xik ? vik}, 0? k ? n, 即取值vi1, ..., vik满足所有与变量Xi1, ..., Xik有关的约束 完全赋值: k由0到n，每个变量都得到了赋值 [变量值域大小为d, 则有O(dn) 种完全赋值] 状态: 合法赋值 初始状态: 空赋值 {}, 即 k = 0，也就是还没有变量得到赋值 状态的后继: {Xi1?vi1, ..., Xik?vik} ? {Xi1?vi1, ..., Xik?vik, Xik+1?vik+1} 目标测试: k = n，即n个变量都得到了赋值 4 变量 X1, ..., X4 令节点N的合法赋值为:  A = {X1 ? v1, X3 ? v3} 以为变量X4取值为例 令X4 的值域为 {v4,1, v4,2, v4,3} A的后继为以下赋值中的合法赋值: {X1 ? v1, X3 ? v3 , X4 ? v4,1 } {X1 ? v1, X3 ? v3 , X4 ? v4,2 } {X1 ? v1, X3 ? v3 , X4 ? v4,3 } 回溯有哪些信誉好的足球投注网站Backtracking Search 本质即使用递归的简化深度优先算法 回溯有哪些信誉好的足球投注网站(3 变量) 回溯有哪些信誉好的足球投注网站(3 变量) 回溯有哪些信誉好的足球投注网站(3 变量) 回溯有哪些信誉好的足球投注网站(3 变量) 回溯有哪些信誉好的足球投注网站(3 变量) 回溯有哪些信誉好的足球投注网站(3 变量) 回溯有哪些信誉好的足球投注网站(3 变量) 回溯有哪些信誉好的足球投注网站(3 变量) 回溯有哪些信誉好的足球投注网站(3 变量) 回溯有哪些信誉好的足球投注网站(3 变量) 回溯有哪些信誉好的足球投注网站(3 变量) 回溯有哪些信誉好的足球投注网站(3 变量) 回溯算法Backtracking Algorithm CSP-BACKTRACKING(A) If assignment A is complete then return A X ? select a variable