人工智能：約束滿足問(wèn)題

《人工智能》第2章

問(wèn)題求解智能體(3)2024/2/171約束滿足問(wèn)題(CSP)

ConstraintSatisfactionProblems(CSP)

2024/2/172我們想做些什么？狀態(tài)具有內(nèi)部結(jié)構(gòu)，并存在很多約束在許多問(wèn)題中，狀態(tài)的到達(dá)與進(jìn)行選擇的次序無(wú)關(guān)（“可交換”），即采取不同的次序進(jìn)行選擇也一樣可以到達(dá)同一個(gè)狀態(tài)那能否通過(guò)選定某種適合的選擇次序能夠更有效的解決這些問(wèn)題呢？甚至可以避免進(jìn)行選擇？2024/2/173約束傳播

ConstraintPropagation將一個(gè)皇后放入到一個(gè)方格里移去所有可能攻擊到的方格2024/2/p>

5

5

5

5

6

7ConstraintPropagation計(jì)算每一行、每一列不會(huì)受到攻擊的方格數(shù)將一個(gè)皇后放置在有著最小數(shù)目的行或列上再次移去可能受到攻擊的所有方格2024/2/1753443354

3

3

3

4

5重復(fù)前述過(guò)程ConstraintPropagation2024/2/176432343

3

3

4

3ConstraintPropagation2024/2/177422133

3

3

1ConstraintPropagation2024/2/1782212

2

1ConstraintPropagation2024/2/179ConstraintPropagation211

22024/2/1710ConstraintPropagation11

2024/2/1711ConstraintPropagation2024/2/1712我們需要些什么？后繼函數(shù)與目標(biāo)測(cè)試還需要:通過(guò)約束傳播（propagatetheconstraints）信息，比如通過(guò)對(duì)一個(gè)皇后位置的約束來(lái)影響其他皇后的位置提前的失敗測(cè)試（failuretest）約束的清晰表示

約束傳播算法2024/2/1713約束滿足問(wèn)題(CSP)

ConstraintSatisfactionProblem(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è)賦值，且所有的約束得到滿足2024/2/1714地圖著色問(wèn)題7個(gè)變量

{WA,NT,SA,Q,NSW,V,T}

每個(gè)變量的值域是一樣的:

{red,green,blue}

兩個(gè)相鄰的變量不能取相同的值:

WA

NT,WA

SA,NT

SA,NT

Q,SA

Q,

SA

NSW,SA

V,Q

NSW,NSW

VWANTSAQNSWVTWANTSAQNSWVT2024/2/17158-皇后問(wèn)題8個(gè)變量Xi,i=1to8

每個(gè)變量的值域均為:{1,2,…,8}

約束表示為如下形式:Xi=kXj

kforallj=1to8,j

i對(duì)角線也是相同的約束2024/2/17162024/2/1717數(shù)字游戲Sudoku變量:每個(gè)(開(kāi))正方形定義域:{1,2,…,9}約束:每行9-格都不同每列9-格都不同每個(gè)區(qū)域內(nèi)的9-格都不同StreetPuzzle12345Ni={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}TheEnglishmanlivesintheRedhouseTheSpaniardhasaDogTheJapaneseisaPainterTheItaliandrinksTeaTheNorwegianlivesinthefirsthouseontheleftTheowneroftheGreenhousedrinksCoffeeTheGreenhouseisontherightoftheWhitehouseTheSculptorbreedsSnailsTheDiplomatlivesintheYellowhouseTheownerofthemiddlehousedrinksMilkTheNorwegianlivesnextdoortotheBluehouseTheViolinistdrinksFruitjuiceTheFoxisinthehousenexttotheDoctor’sTheHorseisnexttotheDiplomat’sWhoownstheZebra?WhodrinksWater?2024/2/1718StreetPuzzle12345Ni={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}TheEnglishmanlivesintheRedhouseTheSpaniardhasaDogTheJapaneseisaPainterTheItaliandrinksTeaTheNorwegianlivesinthefirsthouseontheleftTheowneroftheGreenhousedrinksCoffeeTheGreenhouseisontherightoftheWhitehouseTheSculptorbreedsSnailsTheDiplomatlivesintheYellowhouseTheownerofthemiddlehousedrinksMilkTheNorwegianlivesnextdoortotheBluehouseTheViolinistdrinksFruitjuiceTheFoxisinthehousenexttotheDoctor’sTheHorseisnexttotheDiplomat’s

i,j[1,5],ij,NiNj

i,j[1,5],ij,CiCj

...2024/2/1719StreetPuzzle12345Ni={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}TheEnglishmanlivesintheRedhouseTheSpaniardhasaDogTheJapaneseisaPainterTheItaliandrinksTeaTheNorwegianlivesinthefirsthouseontheleftTheowneroftheGreenhousedrinksCoffeeTheGreenhouseisontherightoftheWhitehouseTheSculptorbreedsSnailsTheDiplomatlivesintheYellowhouseTheownerofthemiddlehousedrinksMilkTheNorwegianlivesnextdoortotheBluehouseTheViolinistdrinksFruitjuiceTheFoxisinthehousenexttotheDoctor’sTheHorseisnexttotheDiplomat’s(Ni=English)

(Ci=Red)(Ni=Japanese)

(Ji=Painter)(N1=Norwegian)其余的類似，留給同學(xué)們思考(Ci=White)

(Ci+1=Green)(C5

White)(C1

Green)2024/2/1720StreetPuzzle12345Ni={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}TheEnglishmanlivesintheRedhouseTheSpaniardhasaDogTheJapaneseisaPainterTheItaliandrinksTeaTheNorwegianlivesinthefirsthouseontheleftTheowneroftheGreenhousedrinksCoffeeTheGreenhouseisontherightoftheWhitehouseTheSculptorbreedsSnailsTheDiplomatlivesintheYellowhouseTheownerofthemiddlehousedrinksMilkTheNorwegianlivesnextdoortotheBluehouseTheViolinistdrinksFruitjuiceTheFoxisinthehousenexttotheDoctor’sTheHorseisnexttotheDiplomat’s(Ni=English)

(Ci=Red)(Ni=Japanese)

(Ji=Painter)(N1=Norwegian)(Ci=White)

(Ci+1=Green)(C5

White)(C1

Green)一元（unary）約束2024/2/1721StreetPuzzle12345Ni={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}TheEnglishmanlivesintheRedhouseTheSpaniardhasaDogTheJapaneseisaPainterTheItaliandrinksTeaTheNorwegianlivesinthefirsthouseontheleftN1=NorwegianTheowneroftheGreenhousedrinksCoffeeTheGreenhouseisontherightoftheWhitehouseTheSculptorbreedsSnailsTheDiplomatlivesintheYellowhouseTheownerofthemiddlehousedrinksMilkD3=MilkTheNorwegianlivesnextdoortotheBluehouseTheViolinistdrinksFruitjuiceTheFoxisinthehousenexttotheDoctor’sTheHorseisnexttotheDiplomat’s2024/2/1722StreetPuzzle12345Ni={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}TheEnglishmanlivesintheRedhouseC1

RedTheSpaniardhasaDogA1

DogTheJapaneseisaPainterTheItaliandrinksTeaTheNorwegianlivesinthefirsthouseontheleftN1=NorwegianTheowneroftheGreenhousedrinksCoffeeTheGreenhouseisontherightoftheWhitehouseTheSculptorbreedsSnailsTheDiplomatlivesintheYellowhouseTheownerofthemiddlehousedrinksMilkD3=MilkTheNorwegianlivesnextdoortotheBluehouseTheViolinistdrinksFruitjuiceJ3

ViolinistTheFoxisinthehousenexttotheDoctor’sTheHorseisnexttotheDiplomat’s2024/2/1723有限CSPvs.無(wú)限CSP

Finitevs.InfiniteCSP有限CSP

:每個(gè)變量的值域有有限個(gè)值無(wú)限CSP

:一些或所有的變量的值域是無(wú)限的

E.g.,實(shí)數(shù)線性規(guī)劃:本課程只討論有限CSP

2024/2/1724CSP描述為搜索問(wèn)題n個(gè)變量X1,...,Xn合法賦值:{Xi1

vi1,...,Xik

vik},0kn,

即取值vi1,...,vik滿足所有與變量Xi1,...,Xik有關(guān)的約束完全賦值:

k由0到n，每個(gè)變量都得到了賦值

[變量值域大小為d,則有O(dn)種完全賦值]狀態(tài):合法賦值初始狀態(tài):空賦值{},即k=0，也就是還沒(méi)有變量得到賦值狀態(tài)的后繼:

{Xi1

vi1,...,Xik

vik}{Xi1

vi1,...,Xik

vik,Xik+1

vik+1}目標(biāo)測(cè)試:k=n，即n個(gè)變量都得到了賦值2024/2/17254變量X1,...,X4令節(jié)點(diǎn)N的合法賦值為:

A={X1

v1,X3

v3}以為變量X4取值為例令X4

的值域?yàn)閧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}2024/2/1726回溯搜索

BacktrackingSearch本質(zhì)即使用遞歸的簡(jiǎn)化深度優(yōu)先算法,每次為一個(gè)變量選擇值，當(dāng)沒(méi)有合法的值可以再賦給該變量時(shí)就回溯。2024/2/1727回溯算法

BacktrackingAlgorithmCSP-BACKTRACKING(A)IfassignmentAiscompletethenreturnAX

selectavariablenotinADselectanorderingonthedomainofXForeachvaluevinDdoAdd(X

v)toAIfAisvalidthenresult

CSP-BACKTRACKING(A)Ifresult

failurethenreturnresultReturnfailureCallCSP-BACKTRACKING({})2024/2/1728地圖著色問(wèn)題

MapColoring{}WA=redWA=greenWA=blueWA=redNT=greenWA=redNT=blueWA=redNT=greenQ=redWA=redNT=greenQ=blueWANTSAQNSWVT2024/2/17292024/2/1730簡(jiǎn)單回溯例子2024/2/1731簡(jiǎn)單回溯例子2024/2/1732簡(jiǎn)單回溯例子2024/2/1733簡(jiǎn)單回溯例子CSP回溯效率的關(guān)鍵問(wèn)題CSP-BACKTRACKING(A)IfassignmentAiscompletethenreturnAX

select

avariablenotinADselectanorderingonthedomainofXForeachvaluevinDdoAdd(X

v)toAIfaisvalidthenresultCSP-BACKTRACKING(A)Ifresult

failurethenreturnresultReturnfailure2024/2/1734下一個(gè)將選擇哪一個(gè)變量來(lái)賦值?

Thecurrentassignmentmaynotleadtoanysolution,butthealgorithmstilldoesknowit.Selectingtherightvariabletowhichtoassignavaluemayhelpdiscoverthecontradictionmorequickly變量X的（多個(gè)）值應(yīng)該按一個(gè)什么樣的次序進(jìn)行賦值?

Thecurrentassignmentmaybepartofasolution.SelectingtherightvaluetoassigntoXmayhelpdiscoverthissolutionmorequicklyMoreonthesequestionsinashortwhile...CSP回溯效率的關(guān)鍵問(wèn)題2024/2/1735最少剩余值啟發(fā)式

下一個(gè)將選擇哪一個(gè)變量來(lái)賦值?

選擇具有最少剩余值的變量——最少剩余值（MRV）啟發(fā)式，也稱為“最受約束變量”或“失敗優(yōu)先”啟發(fā)式

[基本原理:對(duì)不合法的值盡早剪枝，將分支因子最小化]2024/2/17368-Queens43234每個(gè)未賦值變量的值的個(gè)數(shù)新的賦值前向檢驗(yàn)2024/2/17378-Queens4213每個(gè)未賦值變量的值的個(gè)數(shù)（新）新的賦值前向檢驗(yàn)2024/2/1738MapColoringSA的剩余值域大小為1（剩余值Blue）Q的剩余值域大小為2NSW,V和T的剩余值域大小為3

選擇SAWANTSAQNSWVTWANTSA2024/2/1739最多約束變量啟發(fā)式下一個(gè)將選擇哪一個(gè)變量來(lái)賦值?

在同樣擁有最小剩余值域的多個(gè)變量（即受到的約束最多）中，選擇其中受到其他未賦值變量的約束個(gè)數(shù)最多的變量——度啟發(fā)式。

[基本原理:增加未來(lái)移去值的數(shù)量，以減少未來(lái)的分支因子]2024/2/1740MapColoringWANTSAQNSWVTSA在未進(jìn)行任何賦值之前，所有變量的值域大小均為3，但SA陷入的約束個(gè)數(shù)(5)比其他變量多

選擇SA并對(duì)其進(jìn)行賦值(如

Blue）2024/2/1741最少約束值啟發(fā)式對(duì)選定變量的賦值應(yīng)該按照什么次序進(jìn)行?

選擇X的一個(gè)值首先對(duì)X進(jìn)行賦值，該值將最少地移去當(dāng)前賦值之外的變量值域的值

[基本原理:由于僅有一個(gè)值最終會(huì)賦給X，應(yīng)首先選取最少約束的值，因?yàn)樵撝悼雌饋?lái)最不可能導(dǎo)致非法的賦值]

[說(shuō)明:需要對(duì)所有的值采用啟發(fā)式進(jìn)行前向檢驗(yàn)，而不僅是針對(duì)已選的值]2024/2/1742{}MapColoringWANTSAQNSWVTWANTQ的值域還剩余兩個(gè)值:BlueandRed把Blue賦給Q，則導(dǎo)致SA剩余0個(gè)值，而賦Red則剩余1個(gè)值2024/2/1743{Blue}MapColoringWANTSAQNSWVTWANTQ的值域還剩余兩個(gè)值:BlueandRed把Blue賦給Q，則導(dǎo)致SA剩余0個(gè)值，而賦Red則剩余1個(gè)值2024/2/1744ModifiedBacktrackingAlgorithmCSP-BACKTRACKING(A,var-domains)IfassignmentAiscompletethenreturnAX

selectavariablenotinADselectanorderingonthedomainofXForeachvaluevinDdoAdd(X

v)toAvar-domains

forwardchecking(var-domains,X,v,A)IfavariablehasanemptydomainthenreturnfailureresultCSP-BACKTRACKING(A,var-domains)Ifresult

failurethenreturnresultReturnfailure 1)Most-constrained-variableheuristic

2)Most-constraining-variableheuristic

3)Least-constraining-valueheuristic2024/2/1745目前為止，我們的搜索算法只有在函數(shù)選擇了一個(gè)變量的時(shí)候才考慮該變量的約束，如果在搜索中早一些或者在搜索開(kāi)始之前就考慮某些約束，我們能急劇減小搜索空間。一種簡(jiǎn)單的約束傳播技術(shù):前向檢驗(yàn)2024/2/1746前向檢驗(yàn)

ForwardChecking前向檢驗(yàn)

ForwardChecking把值5賦給X1導(dǎo)致變量X2,X3,...,X8的值域減?。ㄖ涤蛑械囊恍┲当灰迫ィ?/p>

12345678X1

X2

X3

X4

X5

X6

X7

X8通過(guò)約束傳播信息：2024/2/1747地圖著色問(wèn)題的前向檢驗(yàn)WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBTWANTSAQNSWV2024/2/1748WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRRGBRGBRGBRGBRGBRGBTWANTSAQNSWV前向檢驗(yàn)把值Red從NT和SA的值域中移去地圖著色問(wèn)題的前向檢驗(yàn)2024/2/1749WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRGBGRGBRGBGBRGBTWANTSAQNSWV地圖著色問(wèn)題的前向檢驗(yàn)2024/2/1750WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRBGRBRGBBRGBRBGRBBBRGBTWANTSAQNSWV地圖著色問(wèn)題的前向檢驗(yàn)2024/2/1751WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRBGRBRGBBRGBRBGRBBBRGB空集:當(dāng)前的賦值

{(WA

R),(Q

G),(V

B)}無(wú)法得到（構(gòu)成）問(wèn)題的解地圖著色問(wèn)題的前向檢驗(yàn)2024/2/1752前向檢驗(yàn)

(通用形式)一旦一對(duì)變量和值(X

v)加入到賦值A(chǔ)，則do:

對(duì)于每個(gè)A之外的變量do:

對(duì)每一個(gè)與聯(lián)系Y和A中的變量的約束C

do:

將所有不滿足C的值從Y的值域中移去

2024/2/1753回溯算法修改CSP-BACKTRACKING(A,var-domains)IfassignmentAiscompletethenreturnAXselectavariablenotinADselectanorderingonthedomainofXForeachvaluevinDdoAdd(X

v)toAvar-domains

forwardchecking(var-domains,X,v,A)IfavariablehasanemptydomainthenreturnfailureresultCSP-BACKTRACKING(A,var-domains)Ifresult

failurethenreturnresultReturnfailure2024/2/1754CSP-BACKTRACKING(A,var-domains)IfassignmentAiscompletethenreturnAXselectavariablenotinADselectanorderingonthedomainofXForeachvaluevinDdoAdd(X

v)toAvar-domains

forwardchecking(var-domains,X,v,A)IfavariablehasanemptydomainthenreturnfailureresultCSP-BACKTRACKING(A,var-domains)Ifresult

failurethenreturnresultReturnfailure不再需要校驗(yàn)A是否合法回溯算法修改2024/2/1755CSP-BACKTRACKING(A,var-domains)IfassignmentAiscompletethenreturnAXselectavariablenotinADselectanorderingonthedomainofXForeachvaluevinDdoAdd(X

v)toAvar-domains

forwardchecking(var-domains,X,v,A)IfavariablehasanemptydomainthenreturnfailureresultCSP-BACKTRACKING(A,var-domains)Ifresult

failurethenreturnresultReturnfailure需要傳遞更新后的變量值域回溯算法修改2024/2/1756CSP-BACKTRACKING(A,var-domains)IfassignmentAiscompletethenreturnAX

selectavariablenotinADselectanorderingonthedomainofXForeachvaluevinDdoAdd(X

v)toAvar-domains

forwardchecking(var-domains,X,v,A)IfavariablehasanemptydomainthenreturnfailureresultCSP-BACKTRACKING(A,var-domains)Ifresult

failurethenreturnresultReturnfailure回溯算法修改2024/2/1757約束傳播

ConstraintPropagation雖然前向檢驗(yàn)?zāi)軝z驗(yàn)出許多矛盾，但還是無(wú)法檢驗(yàn)出所有矛盾。第三行：當(dāng)WA為red、Q為green時(shí)，NT和SA備選均只剩下blue，但是這兩個(gè)區(qū)域相鄰而無(wú)法染相同顏色。前向檢驗(yàn)檢測(cè)不出這樣的矛盾。2024/2/1758WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRBGRBRGBBRGBRBGRBRGB約束傳播是將一個(gè)變量的約束內(nèi)容傳播到其他變量上如：我們需要將約束從WA和Q傳播到NT和SA，再傳播到NT和SA之間的約束上以檢測(cè)矛盾?；∠嗳荩阂环N比前向檢驗(yàn)更強(qiáng)的約束傳播的快速方法。2024/2/1759約束傳播

ConstraintPropagation弧相容

ArcConsistency“弧”是指約束圖中的有向弧，諸如SA和NSW之間的弧。給定SA和NSW的當(dāng)前值域，如果對(duì)于SA的每個(gè)取值x，NSW都有某個(gè)取值y和x相容，那么這條弧就是相容的。反之，NSW到SA的弧相互是不相容的。2024/2/1760TWANTSAQNSWV2024/2/1761Timecomplexity:O(n2d3)Arcconsistencyalgorithm：AC-3K相容弧相容不能解決每個(gè)可能的矛盾，例如圖中賦值{WA-red，NSW-red}是矛盾的，但是AC-3不會(huì)找到這個(gè)矛盾。K相容：如果對(duì)于任何k-1個(gè)變量的相容賦值，第k個(gè)變量總能被賦予一個(gè)和前k-1個(gè)變量相容的值，那么這個(gè)CSP問(wèn)題就是k相容的。2024/2/1762TWANTSAQNSWVK相容舉例：1相容指每個(gè)單獨(dú)的變量自己不是矛盾的，也稱為節(jié)點(diǎn)相容；2相容和弧相容一樣；3相容指任何一對(duì)相鄰的變量總可以擴(kuò)展到第三個(gè)鄰居變量，也成為路徑相容。如果一個(gè)圖是k相容的，也是k-1相容的、k-2相容的，……直到1相容，則這個(gè)圖是強(qiáng)k相容的。K相容和強(qiáng)K相容是否等價(jià)？亦即K相容是否一定K-1相容？2024/2/1763K相容K相容而非K-1相容的例子有K個(gè)變量X1...XK，其中X1的值域?yàn)閧1,2}，X2,...,XK的值域均為{1}；約束條件為:X1不等于X2；X1不等于X3；X2=X3=...=XK=1。對(duì)這個(gè)例子，{X1=1,X4=X5=...=XK=1}是一個(gè)K-2相容賦值，但是對(duì)這個(gè)相容賦值沒(méi)有相容的K-1賦值；而對(duì)K-1的相容賦值{X2=X3=...=XK=1}或{X1=2，X2到XK中有K-2個(gè)變量取值為1}均有相容的K賦值{X1=2,X2=X3=...=XK=1}2024/2/1764K相容假設(shè)我們的CSP問(wèn)題有n個(gè)節(jié)點(diǎn)而且是強(qiáng)n相容的，那么無(wú)需回溯就能求解該問(wèn)題。首先對(duì)x1選擇一個(gè)相容值，由于是2相容，也能保證給x2選擇一個(gè)相容值，x3、x4等等同理。我們只需在值域內(nèi)的d個(gè)值中找到與x1……xi-1相容的值，找到解的時(shí)間復(fù)雜度O(nd)但是，任何建立n相容的算法在最壞情況下必須花費(fèi)n的指數(shù)級(jí)時(shí)間2024/2/1765K相容處理特殊約束Alldiff約束：要求設(shè)計(jì)的全部變量必須取不同的值。Alldiff的矛盾檢測(cè)的一個(gè)簡(jiǎn)單形式包括如下工作：如果約束涉及m個(gè)變量，它們共有n個(gè)可能的不同取值，并且m>n，那么這個(gè)約束不能被滿足。算法：刪除約束中只有單值值域的變量，然后將這些變量的取值從其余變量的值域中刪去。只要還有單值變量就重復(fù)該過(guò)程，如果得到一個(gè)空的值域或者剩下的變量數(shù)比剩余的取值數(shù)大，則產(chǎn)生矛盾。2024/2/1766處理特殊約束如何用Alldiff檢測(cè)不完全賦值{WA=red，NSW=red}的矛盾？SA，NT和Q通過(guò)Alldiff約束連接；通過(guò)在該不完全賦值上應(yīng)用AC-3算法，每個(gè)變量的值域縮小為{green，blue}，此時(shí)三個(gè)變量只有兩種顏色可選，違背ALLdiff約束。2024/2/1767處理特殊約束資源約束（atmost約束）如atmost（10，PA1,PA2,PA3,PA4），PA1,PA2,PA3,PA4表示分配給四項(xiàng)任務(wù)的人員個(gè)數(shù)，總分配不超過(guò)10人。當(dāng)每個(gè)變量的值域?yàn)閧3，4，5，6}時(shí)，不滿足atmost約束。如果值域?yàn)閧2，3，4，5，6},那么5和6可以從值域中刪去。2024/2/1768智能回溯若按變量順序Q，NSW，V，T，SA，WA，NT應(yīng)用簡(jiǎn)單回溯，假設(shè)已進(jìn)行了不完全賦值{Q=red，NSW=green，V=blue，T=red}，當(dāng)嘗試下一個(gè)變量SA時(shí)，發(fā)現(xiàn)任何值都不滿足約束。我們倒退回T試著給T賦一種新的顏色，顯然這種做法很蠢！更智能的回溯：倒退回導(dǎo)致失敗的變量集合中的一個(gè)變量，該集合成為沖突集，上面情況中的沖突集為{Q，NSW，V}。2024/2/1769TWANTSAQNSWV一般來(lái)說(shuō)，變量X的沖突集是通過(guò)約束與X相連接的現(xiàn)在已賦值的變量集合。后向跳轉(zhuǎn)方法回溯到?jīng)_突集中時(shí)間最近的變量，上例中后向跳轉(zhuǎn)跳過(guò)T而嘗試V的新值。CSP-BACKTRACKING修改：令算法在檢驗(yàn)可賦值的合法值時(shí)保存一個(gè)沖突集，如果沒(méi)有找到合法值，則利用失敗標(biāo)記返回沖突集中時(shí)間最近變量。2024/2/1770智能回溯問(wèn)題的結(jié)構(gòu)獨(dú)立子問(wèn)題——