e约束满足人工智能.pptxVIP

我们想做些什么？搜索技术通常按照一个任意的次序对可能进行选择，一般很少有效的信息能够帮助如何进行选择在许多问题中，状态的到达与进行选择的次序无关（“可交换”） ，即采取不同的次序进行选择也一样可以到达同一个状态那能否通过选定某种适合的选择次序能够更有效的解决这些问题呢？甚至可以避免进行选择？约束传播Constraint Propagation将一个皇后放入到一个方格里移去所有可能攻击到的方格Constraint Propagation5 5 5 5 5 6 算每一行、每一列不会受到攻击的方格数将一个皇后放置在有着最小数目的行或列上再次移去可能受到攻击的所有方格Constraint Propagation4 3 3 3 4 5344335重复前述过程Constraint Propagation3 3 3 4 343234Constraint Propagation3 3 3 142213Constraint Propagation2 2 1221Constraint Propagation1 221Constraint Propagation1 1Constraint Propagation我们需要些什么？后继函数与目标测试还需要:通过约束传播（ propagate the constraints ）信息，比如通过对一个皇后位置的约束来影响其他皇后的位置提前的失败测试（failure test）约束的清晰表示 约束传播算法约束满足问题 (CSP) Constraint Satisfaction Problem (CSP)变量的集合 variables {X1, X2, …, Xn}每一个变量Xi所有可能的取值，构成该变量的值域Di；通常Di是有限的约束的集合 constraints {C1, C2, …, Cp}每个约束描述了一个变量子集与特定的某些值合法的结合对应关系目标: 每一个变量都得到了一个赋值，且所有的约束得到满足NTQWASANTNSWQVWASATNSWVT地图着色问题 7 个变量 {WA,NT,SA,Q,NSW,V,T} 每个变量的值域是一样的: {red, green, blue} 两个相邻的变量不能取相同的值: WA?NT, WA?SA, NT?SA, NT?Q, SA?Q, SA?NSW, SA?V,Q?NSW, NSW?V所有的约束都是二进制表示8-皇后问题 8 个变量 Xi, i = 1 to 8 每个变量的值域均为: {1,2,…,8} 约束表示为如下形式:Xi = k ? Xj ? k for all j = 1 to 8, j?i对角线也是相同的约束23415Street Puzzle（课本习题5.13）Ni = {English, Spaniard, Japanese, Italian, Norwegian}Ci = {Red, Green, White, Yellow, Blue}Di = {Tea, Coffee, Milk, Fruit-juice, Water}Ji = {Painter, Sculptor, Diplomat, Violinist, Doctor}Ai = {Dog, Snails, Fox, Horse, Zebra}The Englishman lives in the Red houseThe Spaniard has a DogThe Japanese is a PainterThe Italian drinks TeaThe Norwegian lives in the first house on the leftThe owner of the Green house drinks CoffeeThe Green house is on the right of the White houseThe Sculptor breeds SnailsThe Diplomat lives in the Yellow houseThe owner of the middle house drinks MilkThe Norwegian lives next door to the Blue houseThe Violinist drinks Fruit juiceThe Fox is in the house next to the Doctor’sThe Horse is next to the Diplomat’sWho owns the Zebra?Who drinks Water?23415?i,j?[1,5], i?j, Ni ? Nj?