E 约束满足.ppt

约束满足问题 CSP ConstraintSatisfactionProblems CSP 对于困难的决策 我们将推迟到它变得容易的时候再做决定 R N Chap 5 我们想做些什么 搜索技术通常按照一个任意的次序对可能进行选择 一般很少有效的信息能够帮助如何进行选择在许多问题中 状态的到达与进行选择的次序无关 可交换 即采取不同的次序进行选择也一样可以到达同一个状态那能否通过选定某种适合的选择次序能够更有效的解决这些问题呢 甚至可以避免进行选择 约束传播ConstraintPropagation 将一个皇后放入到一个方格里移去所有可能攻击到的方格 6655556 5555567 ConstraintPropagation 计算每一行 每一列不会受到攻击的方格数将一个皇后放置在有着最小数目的行或列上再次移去可能受到攻击的所有方格 344335 433345 重复前述过程 ConstraintPropagation 43234 33343 ConstraintPropagation 42213 3331 ConstraintPropagation 221 221 ConstraintPropagation ConstraintPropagation 21 12 ConstraintPropagation 1 1 ConstraintPropagation 我们需要些什么 后继函数与目标测试还需要 通过约束传播 propagatetheconstraints 信息 比如通过对一个皇后位置的约束来影响其他皇后的位置提前的失败测试 failuretest 约束的清晰表示约束传播算法 约束满足问题 CSP ConstraintSatisfactionProblem CSP 变量的集合variables X1 X2 Xn 每一个变量Xi所有可能的取值 构成该变量的值域Di 通常Di是有限的约束的集合constraints C1 C2 Cp 每个约束描述了一个变量子集与特定的某些值合法的结合对应关系目标 每一个变量都得到了一个赋值 且所有的约束得到满足 地图着色问题 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 V 8 皇后问题 8个变量Xi i 1to8每个变量的值域均为 1 2 8 约束表示为如下形式 Xi k Xj kforallj 1to8 j i对角线也是相同的约束 StreetPuzzle 课本习题5 13 Ni 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 WhoownstheZebra WhodrinksWater StreetPuzzle Ni 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 StreetPuzzle Ni 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 StreetPuzzle Ni 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 约束 StreetPuzzle Ni 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 TheEnglishmanlivesintheRedhouseTheSpaniardhasaDogTheJapaneseisaPainterTheItaliandrinksTeaTheNorwegianlivesinthefirsthouseontheleft N1 NorwegianTheowneroftheGreenhousedrinksCoffeeTheGreenhouseisontherightoftheWhitehouseTheSculptorbreedsSnailsTheDiplomatlivesintheYellowhouseTheownerofthemiddlehousedrinksMilk D3 MilkTheNorwegianlivesnextdoortotheBluehouseTheViolinistdrinksFruitjuiceTheFoxisinthehousenexttotheDoctor sTheHorseisnexttotheDiplomat s StreetPuzzle Ni 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 TheEnglishmanlivesintheRedhouse C1 RedTheSpaniardhasaDog A1 DogTheJapaneseisaPainterTheItaliandrinksTeaTheNorwegianlivesinthefirsthouseontheleft N1 NorwegianTheowneroftheGreenhousedrinksCoffeeTheGreenhouseisontherightoftheWhitehouseTheSculptorbreedsSnailsTheDiplomatlivesintheYellowhouseTheownerofthemiddlehousedrinksMilk D3 MilkTheNorwegianlivesnextdoortotheBluehouseTheViolinistdrinksFruitjuice J3 ViolinistTheFoxisinthehousenexttotheDoctor sTheHorseisnexttotheDiplomat s 有限CSPvs 无限CSPFinitevs InfiniteCSP 有限CSP 每个变量的值域有有限个值无限CSP 一些或所有的变量的值域是无限的E g 实数线性规划 本课程只讨论有限CSP CSP描述为搜索问题 n个变量X1 Xn合法赋值 Xi1 vi1 Xik vik 0 k n 即取值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个变量都得到了赋值 4变量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 回溯搜索BacktrackingSearch 本质即使用递归的简化深度优先算法 回溯搜索 3变量 赋值Assignment 赋值Assignment X1 v11 X1 v11 回溯搜索 3变量 赋值Assignment X1 v11 X3 v31 X1 v11 v31 X3 回溯搜索 3变量 赋值Assignment X1 v11 X3 v31 X1 v11 v31 X3 X2 假设没有一个X2的取值能构成合法赋值 回溯搜索 3变量 赋值Assignment X1 v11 X3 v32 X1 v11 X3 v32 v31 X2 回溯搜索 3变量 赋值Assignment X1 v11 X3 v32 X1 v11 X3 v32 X2 假设仍然没有一个X2的取值能构成合法赋值 搜索算法回溯到前一个变量 X3 并尝试另外的赋值 但假设X3只有两个可能的取值 于是算法回溯到X1 v31 X2 回溯搜索 3变量 赋值Assignment X1 v12 X1 v11 X3 v32 X2 v31 X2 v12 回溯搜索 3变量 Assignment X1 v12 X2 v21 X1 v11 X3 v32 X2 v31 X2 v12 v21 X2 回溯搜索 3变量 Assignment X1 v12 X2 v21 X1 v11 X3 v32 X2 v31 X2 v12 v21 X2 回溯搜索 3变量 Assignment X1 v12 X2 v21 X3 v32 X1 v11 X3 v32 X2 v31 X2 v12 v21 X2 v32 X3 回溯搜索 3变量 Assignment X1 v12 X2 v21 X3 v32 X1 v11 X3 v32 X2 v31 X2 v12 v21 X2 v32 X3 算法不需要考虑那些在其它子树中次序一样的X3赋值 回溯搜索 3变量 Assignment X1 v12 X2 v21 X3 v32 X1 v11 X3 v32 X2 v31 X2 v12 v21 X2 v32 X3 由于只有三个变量 因此赋值已完全 回溯搜索 3变量 回溯算法BacktrackingAlgorithm CSP BACKTRACKING A IfassignmentAiscompletethenreturnAX selectavariablenotinAD selectanorderingonthedomainofXForeachvaluevinDdoAdd X v toAIfAisvalidthenresult CSP BACKTRACKING A Ifresult failurethenreturnresultReturnfailureCallCSP BACKTRACKING 该递归算法会保存太多的数据到内存中 用迭代改进将会节省许多内存 感兴趣的同学可以进一步思考 地图着色问题MapColoring CSP回溯效率的关键问题 CSP BACKTRACKING A IfassignmentAiscompletethenreturnAX selectavariablenotinAD selectanorderingonthedomainofXForeachvaluevinDdoAdd X v toAIfaisvalidthenresult CSP BACKTRACKING A Ifresult failurethenreturnresultReturnfailure 下一个将选择哪一个变量来赋值 Thecurrentassignmentmaynotleadtoanysolution butthealgorithmstilldoesknowit Selectingtherightvariabletowhichtoassignavaluemayhelpdiscoverthecontradictionmorequickly变量X的 多个 值应该按一个什么样的次序进行赋值 Thecurrentassignmentmaybepartofasolution SelectingtherightvaluetoassigntoXmayhelpdiscoverthissolutionmorequicklyMoreonthesequestionsinashortwhile CSP回溯效率的关键问题 下一个将选择哪一个变量来赋值 当前的赋值不一定就能得到问题的解 正确的选择一个变量将有助于更快的发现约束关系变量X的 多个 值应该按一个什么样的次序进行赋值 Thecurrentassignmentmaybepartofasolution SelectingtherightvaluetoassigntoXmayhelpdiscoverthissolutionmorequicklyMoreonthesequestionsinashortwhile CSP回溯效率的关键问题 下一个将选择哪一个变量来赋值 当前的赋值不一定就能得到问题的解 正确的选择一个变量将有助于更快的发现约束关系变量X的 多个 值应该按一个什么样的次序进行赋值 当前的赋值可能会是解的一部分 正确的选择一个值赋给X将有助于更快的找到解Moreonthesequestionsinashortwhile CSP回溯效率的关键问题 下一个将选择哪一个变量来赋值 当前的赋值不一定就能得到问题的解 正确的选择一个变量将有助于更快的发现约束关系变量X的 多个 值应该按一个什么样的次序进行赋值 当前的赋值可能会是解的一部分 正确的选择一个值赋给X将有助于更快的找到解有关问题将很快得到解答 CSP回溯效率的关键问题 前向检验ForwardChecking 把值5赋给X1导致变量X2 X3 X8的值域减小 值域中的一些值被移去 一种简单的约束传播技术 地图着色问题的前向检验 地图着色问题的前向检验 地图着色问题的前向检验 地图着色问题的前向检验 空集 当前的赋值 WA R Q G V B 无法得到 构成 问题的解 地图着色问题的前向检验 前向检验 通用形式 一旦一对变量和值 X v 加入到赋值A 则do 对于每个A之外的变量do 对每一个与联系Y和A中的变量的约束Cdo 将所有不满足C的值从Y的值域中移去 回溯算法修改 CSP BACKTRACKING A var domains IfassignmentAiscompletethenreturnAX selectavariablenotinAD selectanorderingonthedomainofXForeachvaluevinDdoAdd X v toAvar domains forwardchecking var domains X v A Ifavariablehasanemptydomainthenreturnfailureresult CSP BACKTRACKING A var domains Ifresult failurethenreturnresultReturnfailure CSP BACKTRACKING A var domains IfassignmentAiscompletethenreturnAX selectavariablenotinAD selectanorderingonthedomainofXForeachvaluevinDdoAdd X v toAvar domains forwardchecking var domains X v A Ifavariablehasanemptydomainthenreturnfailureresult CSP BACKTRACKING A var domains Ifresult failurethenreturnresultReturnfailure 不再需要校验A是否合法 回溯算法修改 CSP BACKTRACKING A var domains IfassignmentAiscompletethenreturnAX selectavariablenotinAD selectanorderingonthedomainofXForeachvaluevinDdoAdd X v toAvar domains forwardchecking var domains X v A Ifavariablehasanemptydomainthenreturnfailureresult CSP BACKTRACKING A var domains Ifresult failurethenreturnresultReturnfailure 需要传递更新后的变量值域 回溯算法修改 CSP BACKTRACKING A var domains IfassignmentAiscompletethenreturnAX selectavariablenotinAD selectanorderingonthedomainofXForeachvaluevinDdoAdd X v toAvar domains forwardchecking var domains X v A Ifavariablehasanemptydomainthenreturnfailureresult CSP BACKTRACKING A var domains Ifresult failurethenreturnresultReturnfailure 回溯算法修改 下一个将选择哪一个变量来赋值 最多约束变量启发式Most constrained variableheuristic 最多约束变量启发式Most constrained variableheuristic对该变量的赋值应该按照什么次序进行尝试 最少约束值启发式Least constraining valueheuristic 以上启发式规则容易使人困惑记住所有的变量最终都将得到一个赋值 然而值域中仅有一个值必须赋给变量 最多约束变量启发式 下一个将选择哪一个变量来赋值 选择具有最少剩余值的变量 基本原理 将分支因子最小化 8 Queens 43234 前向检验 8 Queens 4213 前向检验 MapColoring SA的剩余值域大小为1 剩余值Blue Q的剩余值域大小为2NSW V和T的剩余值域大小为3 选择SA 最多约束变量启发式 下一个将选择哪一个变量来赋值 在同样拥有最小剩余值域的多个变量 即受到的约束最多 中 选择其中受到其他未赋值变量的约束个数最多的变量 基本原理 增加未来移去值的数量 以减少未来的分支因子 MapColoring 在未进行任何赋值之前 所有变量的值域大小均为3 但SA陷入的约束个数 5 比其他变量多 选择SA并对其进行赋值 如Blue 最少约束值启发式 对选定变量的赋值应该按照什么次序进行 选择X的一个值首先对X进行赋值 该值将最少的移去当前赋值之外的变量值域的值 基本原理 由于仅有一个值最终会赋给X 应首先选取最少约束的值 因为该值看起来最不可能导致非法的赋值 说明 需要对所有的值采用启发式进行前向检验 而不仅是针对已选的值 MapColoring Q的值域还剩余两个值 BlueandRed把Blue赋给Q 则导致SA剩余0个值 而赋Red则剩余1个值 Blue MapColoring Q的值域还剩余两个值 BlueandRed把Blue赋给Q 则导致SA剩余0个值