人工智能：约束满足问题

《人工智能》第2章

问题求解智能体(3)2024/2/171约束满足问题(CSP)

ConstraintSatisfactionProblems(CSP)

2024/2/172我们想做些什么？状态具有内部结构，并存在很多约束在许多问题中，状态的到达与进行选择的次序无关（“可交换”），即采取不同的次序进行选择也一样可以到达同一个状态那能否通过选定某种适合的选择次序能够更有效的解决这些问题呢？甚至可以避免进行选择？2024/2/173约束传播

ConstraintPropagation将一个皇后放入到一个方格里移去所有可能攻击到的方格2024/2/p>

5

5

5

5

6

7ConstraintPropagation计算每一行、每一列不会受到攻击的方格数将一个皇后放置在有着最小数目的行或列上再次移去可能受到攻击的所有方格2024/2/1753443354

3

3

3

4

5重复前述过程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我们需要些什么？后继函数与目标测试还需要:通过约束传播（propagatetheconstraints）信息，比如通过对一个皇后位置的约束来影响其他皇后的位置提前的失败测试（failuretest）约束的清晰表示

约束传播算法2024/2/1713约束满足问题(CSP)

ConstraintSatisfactionProblem(CSP)变量的集合

variables{X1,X2,…,Xn}每一个变量Xi所有可能的取值，构成该变量的值域Di；通常Di是有限的约束的集合

constraints

{C1,C2,…,Cp}每个约束描述了一个变量子集与特定的某些值合法的结合对应关系目标:

每一个变量都得到了一个赋值，且所有的约束得到满足2024/2/1714地图着色问题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

VWANTSAQNSWVTWANTSAQNSWVT2024/2/17158-皇后问题8个变量Xi,i=1to8

每个变量的值域均为:{1,2,…,8}

约束表示为如下形式:Xi=kXj

kforallj=1to8,j

i对角线也是相同的约束2024/2/17162024/2/1717数字游戏Sudoku变量:每个(开)正方形定义域:{1,2,…,9}约束:每行9-格都不同每列9-格都不同每个区域内的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)其余的类似，留给同学们思考(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.无限CSP

Finitevs.InfiniteCSP有限CSP

:每个变量的值域有有限个值无限CSP

:一些或所有的变量的值域是无限的

E.g.,实数线性规划:本课程只讨论有限CSP

2024/2/1724CSP描述为搜索问题n个变量X1,...,Xn合法赋值:{Xi1

vi1,...,Xik

vik},0kn,

即取值vi1,...,vik满足所有与变量Xi1,...,Xik有关的约束完全赋值:

k由0到n，每个变量都得到了赋值

[变量值域大小为d,则有O(dn)种完全赋值]状态:合法赋值初始状态:空赋值{},即k=0，也就是还没有变量得到赋值状态的后继:

{Xi1

vi1,...,Xik

vik}{Xi1

vi1,...,Xik

vik,Xik+1

vik+1}目标测试:k=n，即n个变量都得到了赋值2024/2/17254变量X1,...,X4令节点N的合法赋值为:

A={X1

v1,X3

v3}以为变量X4取值为例令X4

的值域为{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本质即使用递归的简化深度优先算法,每次为一个变量选择值，当没有合法的值可以再赋给该变量时就回溯。2024/2/1727回溯算法

BacktrackingAlgorithmCSP-BACKTRACKING(A)IfassignmentAiscompletethenreturnAX

selectavariablenotinADselectanorderingonthedomainofXForeachvaluevinDdoAdd(X

v)toAIfAisvalidthenresult

CSP-BACKTRACKING(A)Ifresult

failurethenreturnresultReturnfailureCallCSP-BACKTRACKING({})2024/2/1728地图着色问题

MapColoring{}WA=redWA=greenWA=blueWA=redNT=greenWA=redNT=blueWA=redNT=greenQ=redWA=redNT=greenQ=blueWANTSAQNSWVT2024/2/17292024/2/1730简单回溯例子2024/2/1731简单回溯例子2024/2/1732简单回溯例子2024/2/1733简单回溯例子CSP回溯效率的关键问题CSP-BACKTRACKING(A)IfassignmentAiscompletethenreturnAX

select

avariablenotinADselectanorderingonthedomainofXForeachvaluevinDdoAdd(X

v)toAIfaisvalidthenresultCSP-BACKTRACKING(A)Ifresult

failurethenreturnresultReturnfailure2024/2/1734下一个将选择哪一个变量来赋值?

Thecurrentassignmentmaynotleadtoanysolution,butthealgorithmstilldoesknowit.Selectingtherightvariabletowhichtoassignavaluemayhelpdiscoverthecontradictionmorequickly变量X的（多个）值应该按一个什么样的次序进行赋值?

Thecurrentassignmentmaybepartofasolution.SelectingtherightvaluetoassigntoXmayhelpdiscoverthissolutionmorequicklyMoreonthesequestionsinashortwhile...CSP回溯效率的关键问题2024/2/1735最少剩余值启发式

下一个将选择哪一个变量来赋值?

选择具有最少剩余值的变量——最少剩余值（MRV）启发式，也称为“最受约束变量”或“失败优先”启发式

[基本原理:对不合法的值尽早剪枝，将分支因子最小化]2024/2/17368-Queens43234每个未赋值变量的值的个数新的赋值前向检验2024/2/17378-Queens4213每个未赋值变量的值的个数（新）新的赋值前向检验2024/2/1738MapColoringSA的剩余值域大小为1（剩余值Blue）Q的剩余值域大小为2NSW,V和T的剩余值域大小为3

选择SAWANTSAQNSWVTWANTSA2024/2/1739最多约束变量启发式下一个将选择哪一个变量来赋值?

在同样拥有最小剩余值域的多个变量（即受到的约束最多）中，选择其中受到其他未赋值变量的约束个数最多的变量——度启发式。

[基本原理:增加未来移去值的数量，以减少未来的分支因子]2024/2/1740MapColoringWANTSAQNSWVTSA在未进行任何赋值之前，所有变量的值域大小均为3，但SA陷入的约束个数(5)比其他变量多

选择SA并对其进行赋值(如

Blue）2024/2/1741最少约束值启发式对选定变量的赋值应该按照什么次序进行?

选择X的一个值首先对X进行赋值，该值将最少地移去当前赋值之外的变量值域的值

[基本原理:由于仅有一个值最终会赋给X，应首先选取最少约束的值，因为该值看起来最不可能导致非法的赋值]

[说明:需要对所有的值采用启发式进行前向检验，而不仅是针对已选的值]2024/2/1742{}MapColoringWANTSAQNSWVTWANTQ的值域还剩余两个值:BlueandRed把Blue赋给Q，则导致SA剩余0个值，而赋Red则剩余1个值2024/2/1743{Blue}MapColoringWANTSAQNSWVTWANTQ的值域还剩余两个值:BlueandRed把Blue赋给Q，则导致SA剩余0个值，而赋Red则剩余1个值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目前为止，我们的搜索算法只有在函数选择了一个变量的时候才考虑该变量的约束，如果在搜索中早一些或者在搜索开始之前就考虑某些约束，我们能急剧减小搜索空间。一种简单的约束传播技术:前向检验2024/2/1746前向检验

ForwardChecking前向检验

ForwardChecking把值5赋给X1导致变量X2,X3,...,X8的值域减小（值域中的一些值被移去）

12345678X1

X2

X3

X4

X5

X6

X7

X8通过约束传播信息：2024/2/1747地图着色问题的前向检验WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBTWANTSAQNSWV2024/2/1748WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRRGBRGBRGBRGBRGBRGBTWANTSAQNSWV前向检验把值Red从NT和SA的值域中移去地图着色问题的前向检验2024/2/1749WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRGBGRGBRGBGBRGBTWANTSAQNSWV地图着色问题的前向检验2024/2/1750WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRBGRBRGBBRGBRBGRBBBRGBTWANTSAQNSWV地图着色问题的前向检验2024/2/1751WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRBGRBRGBBRGBRBGRBBBRGB空集:当前的赋值

{(WA

R),(Q

G),(V

B)}无法得到（构成）问题的解地图着色问题的前向检验2024/2/1752前向检验

(通用形式)一旦一对变量和值(X

v)加入到赋值A，则do:

对于每个A之外的变量do:

对每一个与联系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不再需要校验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虽然前向检验能检验出许多矛盾，但还是无法检验出所有矛盾。第三行：当WA为red、Q为green时，NT和SA备选均只剩下blue，但是这两个区域相邻而无法染相同颜色。前向检验检测不出这样的矛盾。2024/2/1758WANTQNSWVSATRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBGBRGBRBGRBRGBBRGBRBGRBRGB约束传播是将一个变量的约束内容传播到其他变量上如：我们需要将约束从WA和Q传播到NT和SA，再传播到NT和SA之间的约束上以检测矛盾。弧相容：一种比前向检验更强的约束传播的快速方法。2024/2/1759约束传播

ConstraintPropagation弧相容

ArcConsistency“弧”是指约束图中的有向弧，诸如SA和NSW之间的弧。给定SA和NSW的当前值域，如果对于SA的每个取值x，NSW都有某个取值y和x相容，那么这条弧就是相容的。反之，NSW到SA的弧相互是不相容的。2024/2/1760TWANTSAQNSWV2024/2/1761Timecomplexity:O(n2d3)Arcconsistencyalgorithm：AC-3K相容弧相容不能解决每个可能的矛盾，例如图中赋值{WA-red，NSW-red}是矛盾的，但是AC-3不会找到这个矛盾。K相容：如果对于任何k-1个变量的相容赋值，第k个变量总能被赋予一个和前k-1个变量相容的值，那么这个CSP问题就是k相容的。2024/2/1762TWANTSAQNSWVK相容举例：1相容指每个单独的变量自己不是矛盾的，也称为节点相容；2相容和弧相容一样；3相容指任何一对相邻的变量总可以扩展到第三个邻居变量，也成为路径相容。如果一个图是k相容的，也是k-1相容的、k-2相容的，……直到1相容，则这个图是强k相容的。K相容和强K相容是否等价？亦即K相容是否一定K-1相容？2024/2/1763K相容K相容而非K-1相容的例子有K个变量X1...XK，其中X1的值域为{1,2}，X2,...,XK的值域均为{1}；约束条件为:X1不等于X2；X1不等于X3；X2=X3=...=XK=1。对这个例子，{X1=1,X4=X5=...=XK=1}是一个K-2相容赋值，但是对这个相容赋值没有相容的K-1赋值；而对K-1的相容赋值{X2=X3=...=XK=1}或{X1=2，X2到XK中有K-2个变量取值为1}均有相容的K赋值{X1=2,X2=X3=...=XK=1}2024/2/1764K相容假设我们的CSP问题有n个节点而且是强n相容的，那么无需回溯就能求解该问题。首先对x1选择一个相容值，由于是2相容，也能保证给x2选择一个相容值，x3、x4等等同理。我们只需在值域内的d个值中找到与x1……xi-1相容的值，找到解的时间复杂度O(nd)但是，任何建立n相容的算法在最坏情况下必须花费n的指数级时间2024/2/1765K相容处理特殊约束Alldiff约束：要求设计的全部变量必须取不同的值。Alldiff的矛盾检测的一个简单形式包括如下工作：如果约束涉及m个变量，它们共有n个可能的不同取值，并且m>n，那么这个约束不能被满足。算法：删除约束中只有单值值域的变量，然后将这些变量的取值从其余变量的值域中删去。只要还有单值变量就重复该过程，如果得到一个空的值域或者剩下的变量数比剩余的取值数大，则产生矛盾。2024/2/1766处理特殊约束如何用Alldiff检测不完全赋值{WA=red，NSW=red}的矛盾？SA，NT和Q通过Alldiff约束连接；通过在该不完全赋值上应用AC-3算法，每个变量的值域缩小为{green，blue}，此时三个变量只有两种颜色可选，违背ALLdiff约束。2024/2/1767处理特殊约束资源约束（atmost约束）如atmost（10，PA1,PA2,PA3,PA4），PA1,PA2,PA3,PA4表示分配给四项任务的人员个数，总分配不超过10人。当每个变量的值域为{3，4，5，6}时，不满足atmost约束。如果值域为{2，3，4，5，6},那么5和6可以从值域中删去。2024/2/1768智能回溯若按变量顺序Q，NSW，V，T，SA，WA，NT应用简单回溯，假设已进行了不完全赋值{Q=red，NSW=green，V=blue，T=red}，当尝试下一个变量SA时，发现任何值都不满足约束。我们倒退回T试着给T赋一种新的颜色，显然这种做法很蠢！更智能的回溯：倒退回导致失败的变量集合中的一个变量，该集合成为冲突集，上面情况中的冲突集为{Q，NSW，V}。2024/2/1769TWANTSAQNSWV一般来说，变量X的冲突集是通过约束与X相连接的现在已赋值的变量集合。后向跳转方法回溯到冲突集中时间最近的变量，上例中后向跳转跳过T而尝试V的新值。CSP-BACKTRACKING修改：令算法在检验可赋值的合法值时保存一个冲突集，如果没有找到合法值，则利用失败标记返回冲突集中时间最近变量。2024/2/1770智能回溯问题的结构独立子问题——