E约束满足人工智能(AI).pptx

约束满足问题约束满足问题 (CSP)Constraint Satisfaction Problems(CSP)(对于困难的决策，我们将推迟到它变得容易的时候再做决定)R&N:Chap.5E约束满足人工智能(AI)共77页，您现在浏览的是第1页!我们想做些什么？我们想做些什么？搜索技术通常按照一个任意的次序对可能进行选择，一般很少有效的信息能够帮助如何进行选择在许多问题中，状态的到达与进行选择的次序无关（“可交换”），即采取不同的次序进行选择也一样可以到达同一个状态那能否通过选定某种适合的选择次序能够更有效的解决这些问题呢？甚至可以避免进行选择？E约束满足人工智能(AI)共77页，您现在浏览的是第2页!约束传播约束传播Constraint Propagation将一个皇后放入到一个方格里移去所有可能攻击到的方格E约束满足人工智能(AI)共77页，您现在浏览的是第3页!66555565 5 5 5 5 6 7Constraint Propagation计算每一行、每一列不会受到攻击的方格数将一个皇后放置在有着最小数目的行或列上再次移去可能受到攻击的所有方格E约束满足人工智能(AI)共77页，您现在浏览的是第4页!432343 3 3 4 3Constraint PropagationE约束满足人工智能(AI)共77页，您现在浏览的是第5页!2212 2 1Constraint PropagationE约束满足人工智能(AI)共77页，您现在浏览的是第6页!Constraint Propagation11 E约束满足人工智能(AI)共77页，您现在浏览的是第7页!我们需要些什么？我们需要些什么？后继函数与目标测试还需要:通过约束传播（propagate the constraints）信息，比如通过对一个皇后位置的约束来影响其他皇后的位置提前的失败测试（failure test）约束的清晰表示 约束传播算法E约束满足人工智能(AI)共77页，您现在浏览的是第8页!地图着色问题地图着色问题 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 VWANTSAQNSWVTWANTSAQNSWVTE约束满足人工智能(AI)共77页，您现在浏览的是第9页!Street Puzzle（课本习题课本习题5.13）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 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 DoctorsThe Horse is next to the DiplomatsWho owns the Zebra?Who drinks Water?E约束满足人工智能(AI)共77页，您现在浏览的是第10页!Street Puzzle12345Ni=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 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 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)E约束满足人工智能(AI)共77页，您现在浏览的是第11页!Street Puzzle12345Ni=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 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 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 DiplomatsE约束满足人工智能(AI)共77页，您现在浏览的是第12页!有限有限CSP vs.无限无限CSPFinite vs.Infinite CSP有限CSP:每个变量的值域有有限个值无限CSP:一些或所有的变量的值域是无限的E.g.,实数线性规划:本课程只讨论有限CSPE约束满足人工智能(AI)共77页，您现在浏览的是第13页!E约束满足人工智能(AI)共77页，您现在浏览的是第14页!E约束满足人工智能(AI)共77页，您现在浏览的是第15页!回溯搜索回溯搜索(3 变量变量)赋值 Assignment=E约束满足人工智能(AI)共77页，您现在浏览的是第16页!赋值 Assignment=(X1,v11),(X3,v31)X1v11v31X3回溯搜索回溯搜索(3 变量变量)E约束满足人工智能(AI)共77页，您现在浏览的是第17页!赋值 Assignment=(X1,v11),(X3,v32)X1v11X3v32v31X2回溯搜索回溯搜索(3 变量变量)E约束满足人工智能(AI)共77页，您现在浏览的是第18页!赋值 Assignment=(X1,v12)X1v11X3v32X2v31X2v12回溯搜索回溯搜索(3 变量变量)E约束满足人工智能(AI)共77页，您现在浏览的是第19页!Assignment=(X1,v12),(X2,v21)X1v11X3v32X2v31X2v12v21X2算法不需要考虑与其他子树中次序一样的变量回溯搜索回溯搜索(3 变量变量)E约束满足人工智能(AI)共77页，您现在浏览的是第20页!Assignment=(X1,v12),(X2,v21),(X3,v32)X1v11X3v32X2v31X2v12v21X2v32X3算法不需要考虑那些在其它子树中次序一样的X3赋值回溯搜索回溯搜索(3 变量变量)E约束满足人工智能(AI)共77页，您现在浏览的是第21页!回溯算法回溯算法Backtracking AlgorithmCSP-BACKTRACKING(A)1.If assignment A is plete then return A2.X select a variable not 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 failureCall CSP-BACKTRACKING()该递归算法会保存太多的数据到内存中，用迭代改进将会节省许多内存，感兴趣的同学可以进一步思考。E约束满足人工智能(AI)共77页，您现在浏览的是第22页!CSP回溯效率的关键问题回溯效率的关键问题CSP-BACKTRACKING(A)1.If assignment A is plete then return A2.X select a variable not 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 failureE约束满足人工智能(AI)共77页，您现在浏览的是第23页!1)下一个将选择哪一个变量来赋值?当前的赋值不一定就能得到问题的解，正确的选择一个变量将有助于更快的发现约束关系2)变量X的（多个）值应该按一个什么样的次序进行赋值?The current assignment may be part of a solution.Selecting the right value to assign to X may help discover this solution more quicklyMore on these questions in a short while.CSP回溯效率的关键问题回溯效率的关键问题E约束满足人工智能(AI)共77页，您现在浏览的是第24页!1)下一个将选择哪一个变量来赋值?当前的赋值不一定就能得到问题的解，正确的选择一个变量将有助于更快的发现约束关系2)变量X的（多个）值应该按一个什么样的次序进行赋值?当前的赋值可能会是解的一部分，正确的选择一个值赋给X将有助于更快的找到解有关问题将很快得到解答CSP回溯效率的关键问题回溯效率的关键问题E约束满足人工智能(AI)共77页，您现在浏览的是第25页!地图着色问题的前向检验地图着色问题的前向检验WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBTWANTSAQNSWVE约束满足人工智能(AI)共77页，您现在浏览的是第26页!WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRGBGRGBRGBGBRGBTWANTSAQNSWV地图着色问题的前向检验地图着色问题的前向检验E约束满足人工智能(AI)共77页，您现在浏览的是第27页!WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRBGRBRGBBRGBRBGRBBBRGB空集:当前的赋值 (WA R),(Q G),(V B)无法得到（构成）问题的解地图着色问题的前向检验地图着色问题的前向检验E约束满足人工智能(AI)共77页，您现在浏览的是第28页!回溯算法修改回溯算法修改CSP-BACKTRACKING(A,var-domains)1.If assignment A is plete then return A2.X select a variable not in A3.D select an ordering on the domain of X4.For each value v in D do a.Add(Xv)to Ab.var-domains forward checking(var-domains,X,v,A)c.If a variable has an empty domain then return failured.result CSP-BACKTRACKING(A,var-domains)e.If result failure then return result5.Return failureE约束满足人工智能(AI)共77页，您现在浏览的是第29页!CSP-BACKTRACKING(A,var-domains)1.If assignment A is plete then return A2.X select a variable not in A3.D select an ordering on the domain of X4.For each value v in D do a.Add(Xv)to Ab.var-domains forward checking(var-domains,X,v,A)c.If a variable has an empty domain then return failured.result CSP-BACKTRACKING(A,var-domains)e.If result failure then return result5.Return failure需要传递更新后的变量值域回溯算法修改回溯算法修改E约束满足人工智能(AI)共77页，您现在浏览的是第30页!1)下一个将选择哪一个变量来赋值?最多约束变量启发式 Most-constrained-variable heuristic 最多约束变量启发式 Most-constrained-variable heuristic2)对该变量的赋值应该按照什么次序进行尝试?最少约束值启发式 Least-constraining-value heuristic以上启发式规则容易使人困惑记住所有的变量最终都将得到一个赋值，然而值域中仅有一个值必须赋给变量E约束满足人工智能(AI)共77页，您现在浏览的是第31页!8-Queens4 3 2 3 4每个未赋值变量的值的个数新的赋值前向检验E约束满足人工智能(AI)共77页，您现在浏览的是第32页!Map ColoringSA的剩余值域大小为1（剩余值Blue）Q的剩余值域大小为2NSW,V 和 T的剩余值域大小为3 选择 SAWANTSAQNSWVTWANTSAE约束满足人工智能(AI)共77页，您现在浏览的是第33页!Map ColoringWANTSAQNSWVTSA在未进行任何赋值之前，所有变量的值域大小均为3，但SA陷入的约束个数(5)比其他变量多选择SA并对其进行赋值(如 Blue）E约束满足人工智能(AI)共77页，您现在浏览的是第34页!Map ColoringWANTSAQNSWVTWANTQ的值域还剩余两个值:Blue and Red把Blue赋给Q，则导致SA剩余0个值，而赋Red则剩余1个值E约束满足人工智能(AI)共77页，您现在浏览的是第35页!Modified Backtracking AlgorithmCSP-BACKTRACKING(A,var-domains)1.If assignment A is plete then return A2.X select a variable not in A3.D select an ordering on the domain of X4.For each value v in D do a.Add(Xv)to Ab.var-domains forward checking(var-domains,X,v,A)c.If a variable has an empty domain then return failured.result CSP-BACKTRACKING(A,var-domains)e.If result failure then return result5.Return failure1)Most-constrained-variable heuristic2)Most-constraining-variable heuristic3)Least-constraining-value heuristicE约束满足人工智能(AI)共77页，您现在浏览的是第36页!RadiosurgeryTumor=badBrain=goodCritical structures=good and sensitiveMinimally invasive procedure that uses a beam of radiation as an ablative surgical instrument to destroy tumorsE约束满足人工智能(AI)共77页，您现在浏览的是第37页!Inputs1)Regions of interestE约束满足人工智能(AI)共77页，您现在浏览的是第38页!Beam SamplingE约束满足人工智能(AI)共77页，您现在浏览的是第39页!Case Results50%Isodose Surface80%Isodose SurfaceLINAC systemCyberknifeE约束满足人工智能(AI)共77页，您现在浏览的是第40页!3443354 3 3 3 4 5重复前述过程Constraint PropagationE约束满足人工智能(AI)共77页，您现在浏览的是第41页!422133 3 3 1Constraint PropagationE约束满足人工智能(AI)共77页，您现在浏览的是第42页!Constraint Propagation211 2E约束满足人工智能(AI)共77页，您现在浏览的是第43页!Constraint PropagationE约束满足人工智能(AI)共77页，您现在浏览的是第44页!约束满足问题约束满足问题(CSP)Constraint Satisfaction Problem(CSP)变量的集合 variables X1,X2,Xn每一个变量Xi所有可能的取值，构成该变量的值域Di；通常Di是有限的约束的集合 constraints C1,C2,Cp每个约束描述了一个变量子集与特定的某些值合法的结合对应关系目标:每一个变量都得到了一个赋值，且所有的约束得到满足E约束满足人工智能(AI)共77页，您现在浏览的是第45页!8-皇后问题皇后问题 8 个变量 Xi,i=1 to 8 每个变量的值域均为:1,2,8 约束表示为如下形式:Xi=k Xj k for all j=1 to 8,j i对角线也是相同的约束所有的约束都是二进制表示E约束满足人工智能(AI)共77页，您现在浏览的是第46页!Street Puzzle12345Ni=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 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 DoctorsThe Horse is next to the Diplomats i,j1,5,ij,Ni Nj i,j1,5,ij,Ci Cj.E约束满足人工智能(AI)共77页，您现在浏览的是第47页!Street Puzzle12345Ni=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 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 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)一元（unary）约束E约束满足人工智能(AI)共77页，您现在浏览的是第48页!Street Puzzle12345Ni=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 Dog 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 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 DiplomatsE约束满足人工智能(AI)共77页，您现在浏览的是第49页!CSP 描述为搜索问题描述为搜索问题n个变量 X1,.,Xn合法赋值:Xi1 vi1,.,Xik vik,0 k n,即取值vi1,.,vik满足所有与变量Xi1,.,Xik有关的约束完全赋值:k由0到n，每个变量都得到了赋值 变量值域大小为d,则有O(dn)种完全赋值状态:合法赋值初始状态:空赋值,即 k=0，也就是还没有变量得到赋值状态的后继:Xi1vi1,.,Xikvik Xi1vi1,.,Xikvik,Xik+1vik+1目标测试:k=n，即n个变量都得到了赋值E约束满足人工智能(AI)共77页，您现在浏览的是第50页!4 变量 X1,.,X4令节点N的合法赋值为:A=X1 v1,X3 v3 以为变量X4取值为例令X4 的值域为 v4,1,v4,2,v4,3A的后继为以下赋值中的合法赋值:X1 v1,X3 v3,X4 v4,1 X1 v1,X3 v3,X4 v4,2 X1 v1,X3 v3,X4 v4,3 E约束满足人工智能(AI)共77页，您现在浏览的是第51页!回溯搜索回溯搜索Backtracking Search本质即使用递归的简化深度优先算法E约束满足人工智能(AI)共77页，您现在浏览的是第52页!赋值 Assignment=(X1,v11)X1v11回溯搜索回溯搜索(3 变量变量)E约束满足人工智能(AI)共77页，您现在浏览的是第53页!赋值 Assignment=(X1,v11),(X3,v31)X1v11v31X3X2假设没有一个X2的取值能构成合法赋值于是，搜索算法回溯到前一个变量(X3)并尝试另外的赋值回溯搜索回溯搜索(3 变量变量)E约束满足人工智能(AI)共77页，您现在浏览的是第54页!赋值 Assignment=(X1,v11),(X3,v32)X1v11X3v32X2假设仍然没有一个X2的取值能构成合法赋值搜索算法回溯到前一个变量(X3)并尝试另外的赋值。但假设X3只有两个可能的取值。于是算法回溯到X1v31X2回溯搜索回溯搜索(3 变量变量)E约束满足人工智能(AI)共77页，您现在浏览的是第55页!Assignment=(X1,v12),(X2,v21)X1v11X3v32X2v31X2v12v21X2回溯搜索回溯搜索(3 变量变量)E约束满足人工智能(AI)共77页，您现在浏览的是第56页!Assignment=(X1,v12),(X2,v21),(X3,v32)X1v11X3v32X2v31X2v12v21X2v32X3回溯搜索回溯搜索(3 变量变量)E约束满足人工智能(AI)共77页，您现在浏览的是第57页!Assignment=(X1,v12),(X2,v21),(X3,v32)X1v11X3v32X2v31X2v12v21X2v32X3由于只有三个变量，因此赋值已完全回溯搜索回溯搜索(3 变量变量)E约束满足人工智能(AI)共77页，您现在浏览的是第58页!地图着色问题地图着色问题Map ColoringWA=redWA=greenWA=blueWA=redNT=greenWA=redNT=blueWA=redNT=greenQ=redWA=redNT=greenQ=blueWANTSAQNSWVTE约束满足人工智能(AI)共77页，您现在浏览的是第59页!1)下一个将选择哪一个变量来赋值?The current assignment may not lead to any solution,but the algorithm still does know it.Selecting the right variable to which to assign a value may help discover the contradiction more quickly2)变量X的（多个）值应该按一个什么样的次序进行赋值?The current assignment may be part of a solution.Selecting the right value to assign to X may help discover this solution more quicklyMore on these questions in a short while.CSP回溯效率的关键问题回溯效率的关键问题E约束满足人工智能(AI)共77页，您现在浏览的是第60页!1)下一个将选择哪一个变量来赋值?当前的赋值不一定就能得到问题的解，正确的选择一个变量将有助于更快的发现约束关系2)变量X的（多个）值应该按一个什么样的次序进行赋值?当前的赋值可能会是解的一部分，正确的选择一个值赋给X将有助于更快的找到解More on these questions in a short while.CSP回溯效率的关键问题回溯效率的关键问题E约束满足人工智能(AI)共77页，您现在浏览的是第61页!前向检验前向检验Forward Checking把值5赋给X1导致变量X2,X3,.,X8的值域减小（值域中的一些值被移去）12345678X1 X2 X3 X4 X5 X6 X7 X8一种简单的约束传播技术:E约束满足人工智能(AI)共77页，您现在浏览的是第62页!WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRRGBRGBRGBRGBRGBRGBTWANTSAQNSWV前向检验把值 Red 从 NT 和 SA 的值域中移去地图着色问题的前向检验地图着色问题的前向检验E约束满足人工智能(AI)共77页，您现在浏览的是第63页!WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRBGRBRGBBRGBRBGRBBBRGBTWANTSAQNSWV地图着色问题的前向检验地图着色问题的前向检验E约束满足人工智能(AI)共77页，您现在浏览的是第64页!前向检验前向检验(通用形式通用形式)一旦一对变量和值(Xv)加入到赋值A，则 do:对于每个A之外的变量 do:对每一个与联系Y和A中的变量的约束C do:将所有不满足C的值从Y的值域中移去E约束满足人工智能(AI)共77页，您现在浏览的是第65页!CSP-BACKTRACKING(A,var-domains)1.If assignment A is plete then return A2.X select a variable not in A3.D select an ordering on the domain of X4.For each value v in D do a.Add(Xv)to Ab.var-domains forward checking(var-domains,X,v,A)c.If a variable has an empty domain then return failured.result CSP-BACKTRACKING(A,var-domains)e.If result failure then return result5.Return failure不再需要校验A是否合法回溯算法修改回溯算法修改E约束满足人工智能(AI)共77页，您现在浏览的是第66页!CSP-BACKTRACKING(A,var-domains)1.If assignment A is plete then return A2.X select a variable not in A3.D select an ordering on the domain of X4.For each value v in D do a.Add(Xv)to Ab.var-domains forward checking(var-domains,X,v,A)c.If a variable has an empty domain then return failured.result CSP-BACKTRACKING(A,var-domains)e.If result failure then return result5.Return failure回溯算法修改回溯算法修改E约束满足人工智能(AI)共77页，您现在浏览的是第67页!最多约束变量启发式最多约束变量启发式1)下一个将选择哪一个变量来赋值?选择具有最少剩余值的变量基本原理:将分支因子最小化E约束满足人工智能(AI)共77页，您现在浏览的是第68页!8-Queens4 2 1 3每个未赋值变量的值的个数（新）新的赋值前向检验E约束满足人工智能(AI)共77页，您现在浏览的是第69页!最多约束变量启发式最多约束变量启发式1)下一个将选择哪一个变量来赋值?在同样拥有最小剩余值域的多个变量（即受到的约束