搜索
第五章约束满足问题Review:LastChapter•Best-firstsearchHeuristicfunctionsestimatecostsofshortestpathsGoodheuristicscandramaticallyreducesearchcostGreedybest-firstsearchexpandslowesth—incompleteandnotalwaysoptimalA*searchexpandslowestg+h—completeandoptimal—alsooptimallyefficient(uptotie-breaks,forforwardsearch)AdmissibleheuristicscanbederivedfromexactsolutionofrelaxedproblemsReview:LastChapterLocalsearchalgorithms•thepathtothegoalisirrelevant;thegoalstateitselfisthesolution•keepasinglecurrentstate,trytoimproveitHill-climbingsearchdependingoninitialstate,cangetstuckinlocalmaximaSimulatedannealingsearchescapelocalmaximabyallowingsome“bad”movesbutgraduallydecreasetheirfrequencyLocalbeamsearchKeeptrackofkstatesratherthanjustoneGeneticalgorithms本章大纲•CSPexamples•BacktrackingsearchforCSPs•Problemstructureandproblemdecomposition•LocalsearchforCSPsConstraintsatisfactionproblems(CSPs)Standardsearchproblem:stateisa“blackbox“–anyolddatastructurethatsupportsgoaltest,eval,successor任何可以由目标测试、评价函数、后继函数访问的数据结构CSP:stateisdefinedbyvariablesXiwithvaluesfromdomain（值域）Digoaltestisasetofconstraintsspecifyingallowablecombinationsofvaluesforsubsetsofvariables每个约束包括一些变量的子集，并指定这些子集的值之间允许进行的合并Simpleexampleofaformalrepresentationlanguage（形式化表示方法）Allowsusefulgeneral-purpose（通用的，而不是问题特定的）algorithmswithmorepowerthanstandardsearchalgorithmsExample:Map-Coloring变量WA,NT,Q,NSW,V,SA,T值域Di={red,green,blue}约束:adjacentregionsmusthavedifferentcolorse.g.,WA≠NT,or(ifthelanguageallowsthis),or(WA,NT)∈{(red,green),(red,blue),(green,red),(green,blue),…}Example:Map-ColoringSolutionsareassignmentssatisfyingallconstraints,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个变量,值域大小d→O(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.,SA≠green•Binary（二元）约束与两个变量有关,e.g.,SA≠WA•Higher-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+10·X1X1+W+W=U+10·X2X2+T+T=O+10·X3X3=F,T≠0,F≠0约束超图Real-worldCSPsAssignmentproblems（分配问题）e.g.,whoteacheswhatclasswhoreviewswhichpapersTimetablingproblems（时间表安排问题）e.g.,whichclassisofferedwhenandwhere?Hardwareconfiguration（硬件配置问题）Transportationscheduling（交通调度）Factoryscheduling（工厂调度）Floorplanning（平面布置）Noticethatmanyreal-worldproblemsinvolvereal-valuedvariables列举分配指数时间dnButcompletecanwebecleveraboutexponentialtimealgorithms?形式化描述标准搜索(incremental增量形式化)从简单直白的方法开始，状态被定义为已被赋值的变量•初始状态:空的赋值,{}•后继函数:给一个未赋值变量赋值使之不与当前状态冲突→fail如果没有合法赋值•目标测试:检验当前赋值是否完全1.ThisisthesameforallCSPs!2.Everysolutionappearsatdepthnwithnvariables→usedepth-firstsearch3.Pathisirrelevant,socanalsousecomplete-stateformulation（完全状态形式化）4.b=(n-l)datdepthl,hencen!·dnleaves!!!!Backtrackingsearch回溯搜索变量赋值具有可交换性,也就是说[WA=redthenNT=green]sameas[NT=greenthenWA=red]在搜索树的每个节点上只考虑单个变量的可能赋值b=dandtherearednleavesDepth-firstsearchforCSPswithsingle-variableassignmentsiscalledbacktrackingsearch回溯搜索是处理CSP问题最基础的无信息搜索算法Cansolven-queensforn≈25回溯搜索BacktrackingexampleBacktrackingexampleBacktrackingexampleBacktrackingexample提高回溯效率General-purposemethodscangivehugegainsinspeed:1.哪一个变量应该被下一个赋值?2.赋值应该以什么样的顺序被尝试?3.能更早察觉到不可避免的失败吗?4.Canwetakeadvantageofproblemstructure?MinimumremainingvaluesMinimumremainingvalues最少剩余值(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—弧相容最简单的传播形式是使每条弧相容X→Y是相容的，当且仅当对变量X中的任意值x都存在相容赋值yArcconsistency—弧相容最简单的传播形式是使每条弧相容X→Y是相容的，当且仅当对变量X中的任意值x都存在相容赋值yArcconsistency—弧相容最简单的传播形式是使每条弧相容X→Y是相容的，当且仅当对变量X中的任意值x都存在相容赋值y如果X失去了一个值,X的邻居需要再次核对Arcconsistency—弧相容最简单的传播形式是使每条弧相容X→Y是相容的，当且仅当对变量X中的任意值x都存在相容赋值y如果X失去了一个值,X的邻居需要再次核对弧相容能比前向检验更早发现矛盾被运行于搜索前的预处理，或者每一次赋值后弧相容算法AC-3O(n2d3)(butdetectingallisNP-hard)提高回溯效率General-purposemethodscangivehugegainsinspeed:1.哪一个变量应该被下一个赋值