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

《E约束满足人工智能(AI)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、约束满足问题(CSP)ConstraintSatisfactionProblems(CSP)(对于困难的决策，我们将推迟到它变得容易的时候再做决定)R&N:Chap.5我们想做些什么？搜索技术通常按照一个任意的次序对可能进行选择，一般很少有效的信息能够帮助如何进行选择在许多问题中，状态的到达与进行选择的次序无关（“可交换”），即采取不同的次序进行选择也一样可以到达同一个状态那能否通过选定某种适合的选择次序能够更有效的解决这些问题呢？甚至可以避免进行选择？约束传播ConstraintPropagation将一个皇后放入到一个方格里移去所有可能攻击到的方格66555565555567Cons

2、traintPropagation计算每一行、每一列不会受到攻击的方格数将一个皇后放置在有着最小数目的行或列上再次移去可能受到攻击的所有方格344335433345重复前述过程ConstraintPropagation4323433343ConstraintPropagation422133331ConstraintPropagation221221ConstraintPropagationConstraintPropagation2112ConstraintPropagation11ConstraintPropagation我们需要些什么？后继函数与目标测试还需要:通过约束传播（pro

3、pagatetheconstraints）信息，比如通过对一个皇后位置的约束来影响其他皇后的位置提前的失败测试（failuretest）约束的清晰表示约束传播算法约束满足问题(CSP)ConstraintSatisfactionProblem(CSP)变量的集合variables{X1,X2,…,Xn}每一个变量Xi所有可能的取值，构成该变量的值域Di；通常Di是有限的约束的集合constraints{C1,C2,…,Cp}每个约束描述了一个变量子集与特定的某些值合法的结合对应关系目标:每一个变量都得到了一个赋值，且所有的约束得到满足地图着色问题7个变量{WA,NT,SA,Q,NSW,V

4、,T}每个变量的值域是一样的:{red,green,blue}两个相邻的变量不能取相同的值:WANT,WASA,NTSA,NTQ,SAQ,SANSW,SAV,QNSW,NSWVWANTSAQNSWVTWANTSAQNSWVT8-皇后问题8个变量Xi,i=1to8每个变量的值域均为:{1,2,…,8}约束表示为如下形式:Xi=kXjkforallj=1to8,ji对角线也是相同的约束所有的约束都是二进制表示StreetPuzzle（课本习题5.13）12345Ni={English,Spaniard,Japanese,Italian,Norwegian}Ci={

5、Red,Green,White,Yellow,Blue}Di={Tea,Coffee,Milk,Fruit-juice,Water}Ji={Painter,Sculptor,Diplomat,Violinist,Doctor}Ai={Dog,Snails,Fox,Horse,Zebra}TheEnglishmanlivesintheRedhouseTheSpaniardhasaDogTheJapaneseisaPainterTheItaliandrinksTeaTheNorwegianlivesinthefirsthouseontheleftTheowneroftheGreenhouse

6、drinksCoffeeTheGreenhouseisontherightoftheWhitehouseTheSculptorbreedsSnailsTheDiplomatlivesintheYellowhouseTheownerofthemiddlehousedrinksMilkTheNorwegianlivesnextdoortotheBluehouseTheViolinistdrinksFruitjuiceTheFoxisinthehousenexttotheDoctor’sTheHorseisnexttotheDiplomat’sWhoownstheZebra?Whodrinks

7、Water?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