人工智能约束满足问题PPT

第五章约束满足问题,Review:LastChapter,Best-firstsearchHeuristicfunctionsestimatecostsofshortestpathsGoodheuristicscandramaticallyreducesearchcostGreedybest-firstsearchexpandslowesthincompleteandnotalwaysoptimalA*searchexpandslowestg+hcompleteandoptimalalsooptimallyefficient(uptotie-breaks,forforwardsearch)Admissibleheuristicscanbederivedfromexactsolutionofrelaxedproblems,Review:LastChapter,Localsearchalgorithmsthepathtothegoalisirrelevant;thegoalstateitselfisthesolutionkeepasinglecurrentstate,trytoimproveitHill-climbingsearchdependingoninitialstate,cangetstuckinlocalmaximaSimulatedannealingsearchescapelocalmaximabyallowingsome“bad”movesbutgraduallydecreasetheirfrequencyLocalbeamsearchKeeptrackofkstatesratherthanjustoneGeneticalgorithms,本章大纲,CSPexamplesBacktrackingsearchforCSPsProblemstructureandproblemdecompositionLocalsearchforCSPs,Constraintsatisfactionproblems(CSPs),Standardsearchproblem:stateisa“blackbox“anyolddatastructurethatsupportsgoaltest,eval,successor任何可以由目标测试、评价函数、后继函数访问的数据结构CSP:stateisdefinedbyvariablesXiwithvaluesfromdomain（值域）Digoaltestisasetofconstraintsspecifyingallowablecombinationsofvaluesforsubsetsofvariables每个约束包括一些变量的子集，并指定这些子集的值之间允许进行的合并Simpleexampleofaformalrepresentationlanguage（形式化表示方法）Allowsusefulgeneral-purpose（通用的，而不是问题特定的）algorithmswithmorepowerthanstandardsearchalgorithms,Example:Map-Coloring,变量WA,NT,Q,NSW,V,SA,T值域Di=red,green,blue约束:adjacentregionsmusthavedifferentcolorse.g.,WANT,or(ifthelanguageallowsthis),or(WA,NT)(red,green),(red,blue),(green,red),(green,blue),Example:Map-Coloring,Solutionsareassignmentssatisfyingallconstraints,e.g.,WA=red,NT=green,Q=red,NSW=green,V=red,SA=blue,T=green,Constraintgraph（约束图）,BinaryCSP:每个约束与2个变量有关约束图:节点是变量,边是约束,General-purposeCSPalgorithms（通用CSP算法）usethegraphstructuretospeedupsearch.E.g.,Tasmaniaisanindependentsubproblem!,CSP的种类,离散变量finitedomains有限值域:n个变量,值域大小dO(dn)完全赋值e.g.,BooleanCSPs/布尔CSP问题(NP-complete)infinitedomains无限值域(integers,strings,etc.)e.g.,jobscheduling,variablesarestart/enddaysforeachjob不能通过枚举来描述值域，只能用约束语言,e.g.,线性约束可解,非线性约束不可解连续值域的变量e.g.,哈勃望远镜观测的开始、结束时间线性规划问题linearconstraintssolvableinpolynomialtimebylinearprogramming(LP)methods,约束的种类,Unary（一元）约束只限制单个变量的取值,e.g.,SAgreenBinary（二元）约束与两个变量有关,e.g.,SAWAHigher-order（高阶）约束involve3ormorevariables,e.g.,cryptarithmetic（密码算数）columnconstraints偏好约束(softconstraints),e.g.,redisbetterthangreenoftenrepresentablebyacostforeachvariableassignment（个体变量赋值的耗散）约束优化问题,Example:密码算数,变量:FTUWROX1X2X3值域:0,1,2,3,4,5,6,7,8,9约束:alldiff(F,T,U,W,R,O)O+O=R+10X1X1+W+W=U+10X2X2+T+T=O+10X3X3=F,T0,F0,约束超图,Real-worldCSPs,Assignmentproblems（分配问题）e.g.,whoteacheswhatclasswhoreviewswhichpapersTimetablingproblems（时间表安排问题）e.g.,whichclassisofferedwhenandwhere?Hardwareconfiguration（硬件配置问题）Transportationscheduling（交通调度）Factoryscheduling（工厂调度）Floorplanning（平面布置）Noticethatmanyreal-worldproblemsinvolvereal-valuedvariables,列举分配,指数时间dnButcompletecanwebecleveraboutexponentialtimealgorithms?,形式化描述标准搜索(incremental增量形式化),从简单直白的方法开始，状态被定义为已被赋值的变量初始状态:空的赋值,后继函数:给一个未赋值变量赋值使之不与当前状态冲突fail如果没有合法赋值目标测试:检验当前赋值是否完全1.ThisisthesameforallCSPs!2.Everysolutionappearsatdepthnwithnvariablesusedepth-firstsearch3.Pathisirrelevant,socanalsousecomplete-stateformulation（完全状态形式化）4.b=(n-l)datdepthl,hencen!dnleaves!,Backtrackingsearch回溯搜索,变量赋值具有可交换性,也就是说WA=redthenNT=greensameasNT=greenthenWA=red在搜索树的每个节点上只考虑单个变量的可能赋值b=dandtherearednleavesDepth-firstsearchforCSPswithsingle-variableassignmentsiscalledbacktrackingsearch回溯搜索是处理CSP问题最基础的无信息搜索算法Cansolven-queensforn25,回溯搜索,Backtrackingexample,Backtrackingexample,Backtrackingexample,Backtrackingexample,提高回溯效率,General-purposemethodscangivehugegainsinspeed:1.哪一个变量应该被下一个赋值?2.赋值应该以什么样的顺序被尝试?3.能更早察觉到不可避免的失败吗?4.Canwetakeadvantageofproblemstructure?,Minimumremainingvalues,Minimumremainingvalues最少剩余值(MRV):选择“合法”取值最少的变量,Whyminratherthanmax?被称为“最受约束变量”或“失败优先”启发式,Degreeheuristic（度启发式）,在MRV无法抉择时启动度启发式度启发式:通过选择涉及对其它未赋值变量的约束数最大的变量,提高回溯效率,General-purposemethodscangivehugegainsinspeed:1.哪一个变量应该被下一个赋值?2.赋值应该以什么样的顺序被尝试?3.能更早察觉到不可避免的失败吗?4.Canwetakeadvantageofproblemstructure?,最少约束值,一个变量被选定,choosetheleastconstrainingvalue（最少约束值）:这个选择的值是在约束图中排除邻居变量的可选值最少的需注意的是可能需要经过一些计算来确定这个值,结合以上启发式来解决1000queens是可行的,提高回溯效率,General-purposemethodscangivehugegainsinspeed:1.哪一个变量应该被下一个赋值?2.赋值应该以什么样的顺序被尝试?3.能更早察觉到不可避免的失败吗?4.Canwetakeadvantageofproblemstructure?,Forwardchecking前向检验,Idea:保持记录未赋值变量的剩余合法值当任一变量没有合法值时结束搜索,前向检验,Idea:保持记录未赋值变量的剩余合法值当任一变量没有合法值时结束搜索,前向检验,Idea:保持记录未赋值变量的剩余合法值当任一变量没有合法值时结束搜索,前向检验,Idea:保持记录未赋值变量的剩余合法值当任一变量没有合法值时结束搜索,Constraintpropagation约束传播,前向检验将信息从已赋值变量传播到未赋值变量，但是并不能提前检测出所有矛盾:,NTandSAcannotbothbeblue!约束传播必须反复应用直到不在有矛盾,Arcconsistency弧相容,最简单的传播形式是使每条弧相容XY是相容的，当且仅当对变量X中的任意值x都存在相容赋值y,Arcconsistency弧相容,最简单的传播形式是使每条弧相容XY是相容的，当且仅当对变量X中的任意值x都存在相容赋值y,Arcconsistency弧相容,最简单的传播形式是使每条弧相容XY是相容的，当且仅当对变量X中的任意值x都存在相容赋值y,如果X失去了一个值,X的邻居需要再次核对,Arcconsistency弧相容,最简单的传播形式是使每条弧相容XY是相容的，当且仅当对变量X中的任意值x都存在相容赋值y,如果X失去了一个值,X的邻居需要再次核对弧相容能比前向检验更早发现矛盾被运行于搜索前的预处理，或者每一次赋值后,弧相容算法AC-3,O(n2d3)(butdetectingallisNP-hard),提高回溯效率,General-purposemethodscangivehugegainsinspeed:1.哪一个变量应该被下一个赋值?2.赋值应该以什么样的顺序被尝试?3.能更早察觉到不可避免的失败吗?4.Canwetakeadvantageofproblemstructure?,本章大纲,CSPexamplesBacktrackingsearchforCSPsProblemstructureandproblemdecompositionLocalsearchforCSPs,问题的结构,T岛和大陆是不连通的约束图中的连通域是可辨认的,问题的结构,假设每个子问题有总共n个变量中的c个变量最差情况下的工作量为O(n/cdc)，是n的线性函数E.g.,n=80,d=2,c=20280=4billionyearsat10millionnodes/sec4220=0.4secondsat10millionnodes/sec,树状结构的CSPs,Theorem:iftheconstraintgraphhasnoloops,theCSPcanbesolvedinO(nd2)time任何一个树状结构的CSP问题可以在变量个数的线性时间内求解ComparetogeneralCSPs,whereworst-casetimeisO(dn)这个性质同样适用于逻辑与概率推理:一个重要的例子：语法约束与推理复杂度之间的关系,Algorithmfor树状结构的CSPs,1.任选一个节点作为树的根节点，从跟节点到叶节点按顺序排列，每个节点的父节点都在它的前面,2.令j从n到2,在弧(Parent(Xj),Xj)上应用弧相容算法，从Xj的值域中删除必要的值3.令j从1到n,赋给变量Xj与变量Parent(Xj)相容的值Complexity:O(nd2),近似树状结构,调整:删除一个变量，修建其邻居的值域,割集调整:删除一组变量（环割集）使剩下的约束图为一颗树环割集大小c运行时间O(dc(n-c)d2),当c很小时比直接回溯有巨大的节省寻找最小的环割集是一个NP难题，但存在有效的近似算法,本章大纲,CSPexamplesBacktrackingsearchforCSPsProblemstructureandproblemdecompositionLocalsearchforCSPs,CSPs的迭代算法,爬山算法、模拟退火算法是处理完全状态的形式化问题（所有变量已被赋值）的典型算法应用到CSPs:允许状态有未满足的约束条件操作者再次分配变量值变量选择:随机选择任意有冲突的变量选择新值的时候采用min-conflicts（最小冲突）启发式:choosevaluethatviolatesthefewestconstraints选择会造成与其它变量的冲突最小的值i.e.,爬山算法中h(n)=total