E约束满足人工智能PPT学习教案

1、会计学1E约束满足人工智能约束满足人工智能第1页/共76页66555565 5 5 5 5 6 7计算每一行、每一列不会受到攻击的方格数将一个皇后放置在有着最小数目的行或列上再次移去可能受到攻击的所有方格第2页/共76页3443354 3 3 3 4 5重复前述过程第3页/共76页432343 3 3 4 3第4页/共76页422133 3 3 1第5页/共76页2212 2 1第6页/共76页211 2第7页/共76页11 第8页/共76页第9页/共76页第10页/共76页目标: 每一个变量都得到了一个赋值，且所有的约束得到满足第11页/共76页 7 个变量 WA,NT,SA,Q,NSW,V

2、,T 每个变量的值域是一样的: red, green, blue 两个相邻的变量不能取相同的值:WA NT, WA SA, NT SA, NT Q, SA Q, SA NSW, SA V,Q NSW, NSW VWANTSAQNSWVTWANTSAQNSWVT第12页/共76页所有的约束都是二进制表示第13页/共76页12345Ni = English, Spaniard, Japanese, Italian, NorwegianCi = Red, Green, White, Yellow, BlueDi = Tea, Coffee, Milk, Fruit-juice, WaterJi =

3、Painter, Sculptor, Diplomat, Violinist, DoctorAi = Dog, Snails, Fox, Horse, ZebraThe 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

4、 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 DoctorsThe Horse is next to the DiplomatsWho owns t

5、he Zebra?Who drinks Water?第14页/共76页12345Ni = English, Spaniard, Japanese, Italian, NorwegianCi = Red, Green, White, Yellow, BlueDi = Tea, Coffee, Milk, Fruit-juice, WaterJi = Painter, Sculptor, Diplomat, Violinist, DoctorAi = Dog, Snails, Fox, Horse, ZebraThe Englishman lives in the Red houseThe Spa

6、niard 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 dr

7、inks MilkThe Norwegian lives next door to the Blue houseThe Violinist drinks Fruit juiceThe Fox is in the house next to the DoctorsThe Horse is next to the Diplomats i,j1,5, ij, Ni Nj i,j1,5, ij, Ci Cj .第15页/共76页12345Ni = English, Spaniard, Japanese, Italian, NorwegianCi = Red, Green, White, Yellow,

8、 BlueDi = Tea, Coffee, Milk, Fruit-juice, WaterJi = Painter, Sculptor, Diplomat, Violinist, DoctorAi = Dog, Snails, Fox, Horse, ZebraThe 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 o

9、f 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

10、 DoctorsThe Horse is next to the Diplomats(Ni = English) (Ci = Red)(Ni = Japanese) (Ji = Painter)(N1 = Norwegian)其余的类似，留给同学们思考(Ci = White) (Ci+1 = Green)(C5 White)(C1 Green)第16页/共76页12345Ni = English, Spaniard, Japanese, Italian, NorwegianCi = Red, Green, White, Yellow, BlueDi = Tea, Coffee, Milk, F

11、ruit-juice, WaterJi = Painter, Sculptor, Diplomat, Violinist, DoctorAi = Dog, Snails, Fox, Horse, ZebraThe 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 Coffe

12、eThe 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 DoctorsThe Horse is next to t

13、he Diplomats(Ni = English) (Ci = Red)(Ni = Japanese) (Ji = Painter)(N1 = Norwegian)(Ci = White) (Ci+1 = Green)(C5 White)(C1 Green)一元（unary）约束第17页/共76页12345Ni = English, Spaniard, Japanese, Italian, NorwegianCi = Red, Green, White, Yellow, BlueDi = Tea, Coffee, Milk, Fruit-juice, WaterJi = Painter, S

14、culptor, Diplomat, Violinist, DoctorAi = Dog, Snails, Fox, Horse, ZebraThe 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 left N1 = NorwegianThe owner of the Green house drinks CoffeeThe Green house

15、is on the right of the White houseThe Sculptor breeds SnailsThe Diplomat lives in the Yellow houseThe owner of the middle house drinks Milk D3 = MilkThe Norwegian lives next door to the Blue houseThe Violinist drinks Fruit juiceThe Fox is in the house next to the DoctorsThe Horse is next to the Dipl

16、omats第18页/共76页12345Ni = English, Spaniard, Japanese, Italian, NorwegianCi = Red, Green, White, Yellow, BlueDi = Tea, Coffee, Milk, Fruit-juice, WaterJi = Painter, Sculptor, Diplomat, Violinist, DoctorAi = Dog, Snails, Fox, Horse, ZebraThe Englishman lives in the Red house C1 RedThe Spaniard has a Do

17、g A1 DogThe Japanese is a PainterThe Italian drinks TeaThe Norwegian lives in the first house on the left N1 = NorwegianThe 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

18、house drinks Milk D3 = MilkThe Norwegian lives next door to the Blue houseThe Violinist drinks Fruit juice J3 ViolinistThe Fox is in the house next to the DoctorsThe Horse is next to the Diplomats第19页/共76页ni,ni,11i,22i,0nj,nj,11j,22j,0for i = 1, 2, ., p : a x +a x +.+a x afor j = 1, 2, ., q : b x +b

19、 x +.+b x b第20页/共76页第21页/共76页第22页/共76页第23页/共76页第24页/共76页第25页/共76页赋值 Assignment = 第26页/共76页赋值 Assignment = (X1,v11)X1v11第27页/共76页赋值 Assignment = (X1,v11), (X3,v31)X1v11v31X3第28页/共76页赋值 Assignment = (X1,v11), (X3,v31)X1v11v31X3X2假设没有一个X2的取值能构成合法赋值于是，搜索算法回溯到前一个变量(X3)并尝试另外的赋值第29页/共76页赋值 Assignment = (X1

20、,v11), (X3,v32)X1v11X3v32v31X2第30页/共76页赋值 Assignment = (X1,v11), (X3,v32)X1v11X3v32X2假设仍然没有一个X2的取值能构成合法赋值搜索算法回溯到前一个变量(X3)并尝试另外的赋值。但假设X3只有两个可能的取值。于是算法回溯到X1v31X2第31页/共76页赋值 Assignment = (X1,v12)X1v11X3v32X2v31X2v12第32页/共76页Assignment = (X1,v12), (X2,v21)X1v11X3v32X2v31X2v12v21X2第33页/共76页Assignment = (

21、X1,v12), (X2,v21)X1v11X3v32X2v31X2v12v21X2算法不需要考虑与其他子树中次序一样的变量第34页/共76页Assignment = (X1,v12), (X2,v21), (X3,v32)X1v11X3v32X2v31X2v12v21X2v32X3第35页/共76页Assignment = (X1,v12), (X2,v21), (X3,v32)X1v11X3v32X2v31X2v12v21X2v32X3算法不需要考虑那些在其它子树中次序一样的X3赋值第36页/共76页Assignment = (X1,v12), (X2,v21), (X3,v32)X1v1

22、1X3v32X2v31X2v12v21X2v32X3由于只有三个变量，因此赋值已完全第37页/共76页该递归算法会保存太多的数据到内存中，用迭代改进将会节省许多内存，感兴趣的同学可以进一步思考。第38页/共76页WA=redWA=greenWA=blueWA=redNT=greenWA=redNT=blueWA=redNT=greenQ=redWA=redNT=greenQ=blueWANTSAQNSWVT第39页/共76页CSP-BACKTRACKING(A)1.If assignment A is complete then return A2.X select a variable no

23、t in A3.D select an ordering on the domain of X4.For each value v in D do a.Add (Xv) to Ab.If a is valid theni.result CSP-BACKTRACKING(A)ii.If result failure then return result5.Return failure第40页/共76页第41页/共76页第42页/共76页CSP回溯效率的关键问题回溯效率的关键问题第43页/共76页CSP回溯效率的关键问题回溯效率的关键问题第44页/共76页把值5赋给X1导致变量X2, X3, .,

24、 X8的值域减小（值域中的一些值被移去） 12345678X1 X2 X3 X4 X5 X6 X7 X8第45页/共76页WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBTWANTSAQNSWV第46页/共76页WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRRGBRGBRGBRGBRGBRGBTWANTSAQNSWV前向检验把值 Red 从 NT 和 SA 的值域中移去第47页/共76页WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRGBGRGBRGBGBRGBTWANTSAQNSWV第48页/共76

25、页WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRBGRBRGBBRGBRBGRBBBRGBTWANTSAQNSWV第49页/共76页WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRBGRBRGBBRGBRBGRBBBRGB空集:当前的赋值 (WA R), (Q G), (V B)无法得到（构成）问题的解第50页/共76页第51页/共76页第52页/共76页不再需要校验A是否合法第53页/共76页需要传递更新后的变量值域第54页/共76页第55页/共76页第56页/共76页第57页/共76页4 3 2 3 4每个未赋值变量的值的个数新的赋值前向检验第58页/共76页4 2 1 3每个未赋值变量的值的个数（新）新的赋值前向检验第59页/共76页WANTSAQNSWVTWANTSA第60页/共76页第61页/共76页WANTSAQNSWVTSA第62页/共76页第63页/共76页WANTSAQNSWVTWANT第64页/共76页BlueWANTSAQNSWVTWANT第65页/共76页1) Most-constrained-variable heuristic2) Most-constraining-variable heuristic