E約束滿足人工智能(AI)課件

1、約束滿足問題 (CSP) Constraint Satisfaction Problems (CSP)(對(duì)于困難的決策，我們將推遲到它變得容易的時(shí)候再做決定) R&N: Chap. 5約束滿足問題 (CSP) Constraint Satis我們想做些什么？搜索技術(shù)通常按照一個(gè)任意的次序?qū)赡苓M(jìn)行選擇，一般很少有效的信息能夠幫助如何進(jìn)行選擇在許多問題中，狀態(tài)的到達(dá)與進(jìn)行選擇的次序無關(guān)（“可交換”） ，即采取不同的次序進(jìn)行選擇也一樣可以到達(dá)同一個(gè)狀態(tài)那能否通過選定某種適合的選擇次序能夠更有效的解決這些問題呢？甚至可以避免進(jìn)行選擇？我們想做些什么？搜索技術(shù)通常按照一個(gè)任意的次序?qū)赡苓M(jìn)行選擇約束傳

2、播Constraint Propagation將一個(gè)皇后放入到一個(gè)方格里移去所有可能攻擊到的方格約束傳播Constraint Propagation將一個(gè)66555565 5 5 5 5 6 7Constraint Propagation計(jì)算每一行、每一列不會(huì)受到攻擊的方格數(shù)將一個(gè)皇后放置在有著最小數(shù)目的行或列上再次移去可能受到攻擊的所有方格65 5 5 5 5 6 7C3443354 3 3 3 4 5重復(fù)前述過程Constraint Propagation34 3 3 3 4 5432343 3 3 4 3Constraint Propagation3 3 3 4 3422133 3 3

3、1Constraint Propagation3 3 3 2212 2 1Constraint Propagation2 2 1Constraint PropagatioConstraint Propagation211 2Constraint Propagation1 2Constraint Propagation11 Constraint Propagation1 Constraint PropagationConstraint Propagation我們需要些什么？后繼函數(shù)與目標(biāo)測(cè)試還需要:通過約束傳播（ propagate the constraints ）信息，比如通過對(duì)一個(gè)皇后位置

4、的約束來影響其他皇后的位置提前的失敗測(cè)試（failure test）約束的清晰表示 約束傳播算法我們需要些什么？后繼函數(shù)與目標(biāo)測(cè)試約束滿足問題 (CSP) Constraint Satisfaction Problem (CSP)變量的集合 variables X1, X2, , Xn每一個(gè)變量Xi所有可能的取值，構(gòu)成該變量的值域Di；通常Di是有限的約束的集合 constraints C1, C2, , Cp每個(gè)約束描述了一個(gè)變量子集與特定的某些值合法的結(jié)合對(duì)應(yīng)關(guān)系目標(biāo): 每一個(gè)變量都得到了一個(gè)賦值，且所有的約束得到滿足約束滿足問題 (CSP) Constraint Satis地圖著色問題

5、7 個(gè)變量 WA,NT,SA,Q,NSW,V,T 每個(gè)變量的值域是一樣的: red, green, blue 兩個(gè)相鄰的變量不能取相同的值:WANT, WASA, NTSA, NTQ, SAQ, SANSW, SAV,QNSW, NSWVWANTSAQNSWVTWANTSAQNSWVT地圖著色問題 7 個(gè)變量 WA,NT,SA,Q,NSW,V8-皇后問題 8 個(gè)變量 Xi, i = 1 to 8 每個(gè)變量的值域均為: 1,2,8 約束表示為如下形式:Xi = k Xj k for all j = 1 to 8, ji對(duì)角線也是相同的約束所有的約束都是二進(jìn)制表示8-皇后問題 8 個(gè)變量 Xi,

6、i = 1 to 8所有的Street Puzzle（課本習(xí)題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 Sp

7、aniard 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 d

8、rinks 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?Street Puzzle（課本習(xí)題5.13）12345NiStreet Puzzle12345Ni = English, Spaniard, Japanese, Italian, Norwegi

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

10、irst 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 juiceTh

11、e Fox is in the house next to the DoctorsThe Horse is next to the Diplomatsi,j1,5, ij, Ni Nji,j1,5, ij, Ci Cj .Street Puzzle12345Ni = EnglisStreet Puzzle12345Ni = English, Spaniard, Japanese, Italian, NorwegianCi = Red, Green, White, Yellow, BlueDi = Tea, Coffee, Milk, Fruit-juice, WaterJi = Painter

12、, 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 ri

13、ght 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) (C

14、i = Red)(Ni = Japanese) (Ji = Painter)(N1 = Norwegian)其余的類似，留給同學(xué)們思考(Ci = White) (Ci+1 = Green)(C5 White)(C1 Green)Street Puzzle12345Ni = EnglisStreet Puzzle12345Ni = English, Spaniard, Japanese, Italian, NorwegianCi = Red, Green, White, Yellow, BlueDi = Tea, Coffee, Milk, Fruit-juice, WaterJi = Pain

15、ter, 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

16、 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)

17、 (Ci = Red)(Ni = Japanese) (Ji = Painter)(N1 = Norwegian)(Ci = White) (Ci+1 = Green)(C5 White)(C1 Green)一元（unary）約束Street Puzzle12345Ni = EnglisStreet Puzzle12345Ni = English, Spaniard, Japanese, Italian, NorwegianCi = Red, Green, White, Yellow, BlueDi = Tea, Coffee, Milk, Fruit-juice, WaterJi = Pai

18、nter, 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

19、 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 t

20、he DiplomatsStreet Puzzle12345Ni = EnglisStreet 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 t

21、he 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

22、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 DiplomatsStreet Puzzle12345Ni = Englis有限CSP vs. 無限CSPFinite vs. Infinite

23、CSP有限CSP : 每個(gè)變量的值域有有限個(gè)值無限CSP : 一些或所有的變量的值域是無限的E.g., 實(shí)數(shù)線性規(guī)劃:本課程只討論有限CSP有限CSP vs. 無限CSPFinite vs. InfCSP 描述為搜索問題n個(gè)變量 X1, ., Xn合法賦值 : Xi1 vi1, ., Xik vik, 0 k n, 即取值vi1, ., vik滿足所有與變量Xi1, ., Xik有關(guān)的約束完全賦值: k由0到n，每個(gè)變量都得到了賦值 變量值域大小為d, 則有O(dn) 種完全賦值狀態(tài): 合法賦值初始狀態(tài): 空賦值 , 即 k = 0，也就是還沒有變量得到賦值狀態(tài)的后繼: Xi1vi1, .,

24、Xikvik Xi1vi1, ., Xikvik, Xik+1vik+1目標(biāo)測(cè)試: k = n，即n個(gè)變量都得到了賦值CSP 描述為搜索問題n個(gè)變量 X1, ., XnE約束滿足人工智能(AI)課件4 變量 X1, ., X4令節(jié)點(diǎn)N的合法賦值為: A = X1 v1, X3 v3 以為變量X4取值為例令X4 的值域?yàn)?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 4 變量 X1, ., X4E約束滿足人工智能(AI)課件回溯搜索Back

25、tracking Search本質(zhì)即使用遞歸的簡化深度優(yōu)先算法回溯搜索Backtracking Search本質(zhì)即使用遞回溯搜索(3 變量)賦值 Assignment = 回溯搜索(3 變量)賦值 Assignment = 賦值 Assignment = (X1,v11)X1v11回溯搜索(3 變量)賦值 Assignment = (X1,v11)X1v1賦值 Assignment = (X1,v11), (X3,v31)X1v11v31X3回溯搜索(3 變量)賦值 Assignment = (X1,v11), (X3賦值 Assignment = (X1,v11), (X3,v31)X1v1

26、1v31X3X2假設(shè)沒有一個(gè)X2的取值能構(gòu)成合法賦值于是，搜索算法回溯到前一個(gè)變量(X3)并嘗試另外的賦值回溯搜索(3 變量)賦值 Assignment = (X1,v11), (X3賦值 Assignment = (X1,v11), (X3,v32)X1v11X3v32v31X2回溯搜索(3 變量)賦值 Assignment = (X1,v11), (X3賦值 Assignment = (X1,v11), (X3,v32)X1v11X3v32X2假設(shè)仍然沒有一個(gè)X2的取值能構(gòu)成合法賦值搜索算法回溯到前一個(gè)變量(X3)并嘗試另外的賦值。但假設(shè)X3只有兩個(gè)可能的取值。于是算法回溯到X1v31X2

27、回溯搜索(3 變量)賦值 Assignment = (X1,v11), (X3賦值 Assignment = (X1,v12)X1v11X3v32X2v31X2v12回溯搜索(3 變量)賦值 Assignment = (X1,v12)X1v1Assignment = (X1,v12), (X2,v21)X1v11X3v32X2v31X2v12v21X2回溯搜索(3 變量)Assignment = (X1,v12), (X2,v2Assignment = (X1,v12), (X2,v21)X1v11X3v32X2v31X2v12v21X2算法不需要考慮與其他子樹中次序一樣的變量回溯搜索(3 變

28、量)Assignment = (X1,v12), (X2,v2Assignment = (X1,v12), (X2,v21), (X3,v32)X1v11X3v32X2v31X2v12v21X2v32X3回溯搜索(3 變量)Assignment = (X1,v12), (X2,v2Assignment = (X1,v12), (X2,v21), (X3,v32)X1v11X3v32X2v31X2v12v21X2v32X3算法不需要考慮那些在其它子樹中次序一樣的X3賦值回溯搜索(3 變量)Assignment = (X1,v12), (X2,v2Assignment = (X1,v12), (X

29、2,v21), (X3,v32)X1v11X3v32X2v31X2v12v21X2v32X3由于只有三個(gè)變量，因此賦值已完全回溯搜索(3 變量)Assignment = (X1,v12), (X2,v2回溯算法Backtracking AlgorithmCSP-BACKTRACKING(A)If assignment A is complete then return AX select a variable not in AD select an ordering on the domain of XFor each value v in D do Add (Xv) to AIf A is

30、valid thenresult CSP-BACKTRACKING(A)If result failure then return resultReturn failureCall CSP-BACKTRACKING()該遞歸算法會(huì)保存太多的數(shù)據(jù)到內(nèi)存中，用迭代改進(jìn)將會(huì)節(jié)省許多內(nèi)存，感興趣的同學(xué)可以進(jìn)一步思考?；厮菟惴˙acktracking Algorithm該遞地圖著色問題Map ColoringWA=redWA=greenWA=blueWA=redNT=greenWA=redNT=blueWA=redNT=greenQ=redWA=redNT=greenQ=blueWANTSAQNSWVT

31、地圖著色問題Map ColoringWA=redWA=CSP回溯效率的關(guān)鍵問題CSP-BACKTRACKING(A)If assignment A is complete then return AX select a variable not in AD select an ordering on the domain of XFor each value v in D do Add (Xv) to AIf a is valid thenresult CSP-BACKTRACKING(A)If result failure then return resultReturn failureCS

32、P回溯效率的關(guān)鍵問題下一個(gè)將選擇哪一個(gè)變量來賦值?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 quickly變量X的（多個(gè)）值應(yīng)該按一個(gè)什么樣的次序進(jìn)行賦值?The current assignment may be part of a solution. Selec

33、ting the right value to assign to X may help discover this solution more quicklyMore on these questions in a short while .CSP回溯效率的關(guān)鍵問題下一個(gè)將選擇哪一個(gè)變量來賦值?The current as下一個(gè)將選擇哪一個(gè)變量來賦值? 當(dāng)前的賦值不一定就能得到問題的解，正確的選擇一個(gè)變量將有助于更快的發(fā)現(xiàn)約束關(guān)系變量X的（多個(gè)）值應(yīng)該按一個(gè)什么樣的次序進(jìn)行賦值? The current assignment may be part of a solution. Select

34、ing the right value to assign to X may help discover this solution more quicklyMore on these questions in a short while .CSP回溯效率的關(guān)鍵問題下一個(gè)將選擇哪一個(gè)變量來賦值? 當(dāng)前的賦值不一定就能得到問下一個(gè)將選擇哪一個(gè)變量來賦值? 當(dāng)前的賦值不一定就能得到問題的解，正確的選擇一個(gè)變量將有助于更快的發(fā)現(xiàn)約束關(guān)系變量X的（多個(gè)）值應(yīng)該按一個(gè)什么樣的次序進(jìn)行賦值? 當(dāng)前的賦值可能會(huì)是解的一部分，正確的選擇一個(gè)值賦給X將有助于更快的找到解More on these questio

35、ns in a short while .CSP回溯效率的關(guān)鍵問題下一個(gè)將選擇哪一個(gè)變量來賦值? 當(dāng)前的賦值不一定就能得到問下一個(gè)將選擇哪一個(gè)變量來賦值? 當(dāng)前的賦值不一定就能得到問題的解，正確的選擇一個(gè)變量將有助于更快的發(fā)現(xiàn)約束關(guān)系變量X的（多個(gè)）值應(yīng)該按一個(gè)什么樣的次序進(jìn)行賦值? 當(dāng)前的賦值可能會(huì)是解的一部分，正確的選擇一個(gè)值賦給X將有助于更快的找到解有關(guān)問題將很快得到解答CSP回溯效率的關(guān)鍵問題下一個(gè)將選擇哪一個(gè)變量來賦值? 當(dāng)前的賦值不一定就能得到問前向檢驗(yàn)Forward Checking把值5賦給X1導(dǎo)致變量X2, X3, ., X8的值域減?。ㄖ涤蛑械囊恍┲当灰迫ィ?1234567

36、8X1 X2 X3 X4 X5 X6 X7 X8一種簡單的約束傳播技術(shù) :前向檢驗(yàn)Forward Checking把值5賦給X1導(dǎo)致地圖著色問題的前向檢驗(yàn)WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBTWANTSAQNSWV地圖著色問題的前向檢驗(yàn)WANTQNSWVSATRGBRGBRWANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRRGBRGBRGBRGBRGBRGBTWANTSAQNSWV前向檢驗(yàn)把值 Red 從 NT 和 SA 的值域中移去地圖著色問題的前向檢驗(yàn)WANTQNSWVSATRGBRGBRGBRGBRGBRGBWANTQNSWVSATRGBR

37、GBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRGBGRGBRGBGBRGBTWANTSAQNSWV地圖著色問題的前向檢驗(yàn)WANTQNSWVSATRGBRGBRGBRGBRGBRGBWANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRBGRBRGBBRGBRBGRBBBRGBTWANTSAQNSWV地圖著色問題的前向檢驗(yàn)WANTQNSWVSATRGBRGBRGBRGBRGBRGBWANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRBGRBRGBBRGBRBGRBBBRGB空

38、集:當(dāng)前的賦值 (WA R), (Q G), (V B)無法得到（構(gòu)成）問題的解地圖著色問題的前向檢驗(yàn)WANTQNSWVSATRGBRGBRGBRGBRGBRGB前向檢驗(yàn) (通用形式)一旦一對(duì)變量和值(Xv)加入到賦值A(chǔ) ，則 do: 對(duì)于每個(gè)A之外的變量 do: 對(duì)每一個(gè)與聯(lián)系Y和A中的變量的約束C do: 將所有不滿足C的值從Y的值域中移去前向檢驗(yàn) (通用形式)一旦一對(duì)變量和值(Xv)加入到賦值A(chǔ)回溯算法修改CSP-BACKTRACKING(A, var-domains)If assignment A is complete then return AX select a variable

39、 not in AD select an ordering on the domain of XFor each value v in D do Add (Xv) to Avar-domains forward checking(var-domains, X, v, A)If a variable has an empty domain then return failureresult CSP-BACKTRACKING(A, var-domains)If result failure then return resultReturn failure回溯算法修改CSP-BACKTRACKING

40、(A, var-domains)If assignment A is complete then return AX select a variable not in AD select an ordering on the domain of XFor each value v in D do Add (Xv) to Avar-domains forward checking(var-domains, X, v, A)If a variable has an empty domain then return failureresult CSP-BACKTRACKING(A, var-doma

41、ins)If result failure then return resultReturn failure不再需要校驗(yàn)A是否合法回溯算法修改不再需要校驗(yàn)A是否合法回溯算法修改CSP-BACKTRACKING(A, var-domains)If assignment A is complete then return AX select a variable not in AD select an ordering on the domain of XFor each value v in D do Add (Xv) to Avar-domains forward checking(var-d

42、omains, X, v, A)If a variable has an empty domain then return failureresult CSP-BACKTRACKING(A, var-domains)If result failure then return resultReturn failure需要傳遞更新后的變量值域回溯算法修改需要傳遞更新后的變量值域回溯算法修改CSP-BACKTRACKING(A, var-domains)If assignment A is complete then return AX select a variable not in AD sel

43、ect an ordering on the domain of XFor each value v in D do Add (Xv) to Avar-domains forward checking(var-domains, X, v, A)If a variable has an empty domain then return failureresult CSP-BACKTRACKING(A, var-domains)If result failure then return resultReturn failure回溯算法修改回溯算法修改下一個(gè)將選擇哪一個(gè)變量來賦值? 最多約束變量啟發(fā)

44、式 Most-constrained-variable heuristic 最多約束變量啟發(fā)式 Most-constrained-variable heuristic對(duì)該變量的賦值應(yīng)該按照什么次序進(jìn)行嘗試? 最少約束值啟發(fā)式 Least-constraining-value heuristic以上啟發(fā)式規(guī)則容易使人困惑記住所有的變量最終都將得到一個(gè)賦值，然而值域中僅有一個(gè)值必須賦給變量下一個(gè)將選擇哪一個(gè)變量來賦值? 最多約束變量啟發(fā)式 M最多約束變量啟發(fā)式下一個(gè)將選擇哪一個(gè)變量來賦值?選擇具有最少剩余值的變量基本原理: 將分支因子最小化最多約束變量啟發(fā)式下一個(gè)將選擇哪一個(gè)變量來賦值?8-Que

45、ens4 3 2 3 4每個(gè)未賦值變量的值的個(gè)數(shù)新的賦值前向檢驗(yàn)8-Queens4 3 2 3 48-Queens4 2 1 3每個(gè)未賦值變量的值的個(gè)數(shù)（新）新的賦值前向檢驗(yàn)8-Queens4 2 1 Map ColoringSA的剩余值域大小為1（剩余值Blue）Q的剩余值域大小為2NSW, V 和 T的剩余值域大小為3 選擇 SAWANTSAQNSWVTWANTSAMap ColoringSA的剩余值域大小為1（剩余值Blu最多約束變量啟發(fā)式下一個(gè)將選擇哪一個(gè)變量來賦值?在同樣擁有最小剩余值域的多個(gè)變量（即受到的約束最多）中，選擇其中受到其他未賦值變量的約束個(gè)數(shù)最多的變量基本原理: 增加未

46、來移去值的數(shù)量，以減少未來的分支因子最多約束變量啟發(fā)式下一個(gè)將選擇哪一個(gè)變量來賦值?Map ColoringWANTSAQNSWVTSA在未進(jìn)行任何賦值之前，所有變量的值域大小均為3，但SA陷入的約束個(gè)數(shù)(5)比其他變量多選擇SA并對(duì)其進(jìn)行賦值(如 Blue）Map ColoringWANTSAQNSWVTSA在未進(jìn)行最少約束值啟發(fā)式對(duì)選定變量的賦值應(yīng)該按照什么次序進(jìn)行?選擇X的一個(gè)值首先對(duì)X進(jìn)行賦值，該值將最少的移去當(dāng)前賦值之外的變量值域的值基本原理: 由于僅有一個(gè)值最終會(huì)賦給X ，應(yīng)首先選取最少約束的值，因?yàn)樵撝悼雌饋碜畈豢赡軐?dǎo)致非法的賦值說明: 需要對(duì)所有的值采用啟發(fā)式進(jìn)行前向檢驗(yàn)，而不

47、僅是針對(duì)已選的值最少約束值啟發(fā)式對(duì)選定變量的賦值應(yīng)該按照什么次序進(jìn)行?Map ColoringWANTSAQNSWVTWANTQ的值域還剩余兩個(gè)值: Blue and Red把Blue賦給Q ，則導(dǎo)致SA剩余0個(gè)值，而賦Red則剩余1個(gè)值Map ColoringWANTSAQNSWVTWANTBlueMap ColoringWANTSAQNSWVTWANTQ的值域還剩余兩個(gè)值: Blue and Red把Blue賦給Q ，則導(dǎo)致SA剩余0個(gè)值，而賦Red則剩余1個(gè)值BlueMap ColoringWANTSAQNSWVTModified Backtracking AlgorithmCSP-BA

48、CKTRACKING(A, var-domains)If assignment A is complete then return AX select a variable not in AD select an ordering on the domain of XFor each value v in D do Add (Xv) to Avar-domains forward checking(var-domains, X, v, A)If a variable has an empty domain then return failureresult CSP-BACKTRACKING(A, var-domains)If result failure then ret