人工智能约束满足问题

第五章约束满足问题Review:LastChapterBest-firstsearch

Heuristicfunctionsestimatecostsofshortestpaths

Goodheuristicscandramaticallyreducesearchcost

Greedybest-firstsearchexpandslowesth

—incompleteandnotalwaysoptimal

A*searchexpandslowestg+h

—completeandoptimal

—alsooptimallyefficient(uptotie-breaks,forforwardsearch)

Admissibleheuristicscanbederivedfromexactsolutionofrelaxedproblems

Review:LastChapterLocalsearchalgorithms

thepathtothegoalisirrelevant;thegoalstateitselfisthesolutionkeepasingle"current"state,trytoimproveit

Hill-climbingsearch

dependingoninitialstate,cangetstuckinlocalmaxima

Simulatedannealingsearch

escapelocalmaximabyallowingsome“bad”movesbut graduallydecreasetheirfrequency

Localbeamsearch

Keeptrackofkstatesratherthanjustone

Geneticalgorithms本章大纲CSPexamples

BacktrackingsearchforCSPs

Problemstructureandproblemdecomposition

LocalsearchforCSPs

Constraintsatisfactionproblems(CSPs) Standardsearchproblem:

stateisa“blackbox“–anyolddatastructurethatsupportsgoaltest, eval,successor

任何可以由目标测试、评价函数、后继函数访问的数据结构

CSP:

stateisdefinedbyvariablesXi

withvaluesfromdomain（值域）Di

goaltestisasetofconstraintsspecifyingallowablecombinationsofvaluesforsubsetsofvariables

每个约束包括一些变量的子集，并指定这些子集的值之间允许进行的合并

Simpleexampleofaformalrepresentationlanguage（形式化表示方法）

Allowsusefulgeneral-purpose（通用的，而不是问题特定的）algorithmswithmorepowerthanstandardsearchalgorithmsExample:Map-Coloring变量

WA,NT,Q,NSW,V,SA,T

值域

Di={red,green,blue}

约束:adjacentregionsmusthavedifferentcolors

e.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≠≠greenBinary（二元元）约约束与与两两个变变量有有关,e.g.,SA≠≠WAHigher-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.哪一个变量量应该被下下一个赋值值?2.赋值应该以以什么样的的顺序被尝尝试?3.能更早察觉觉到不可避避免的失败败吗?4.Canwetakeadvantageofproblemstructure?本章大纲CSPexamplesBacktrackingsearchforCSPsProblemstructureandproblemdecompositionLocalsearchforCSPs问题的结构构T岛和大陆是是不连通的约束图中的的连通域是可辨认的的问题的结构构假设每个子子问题有总总共n个变量中的的c个变量最差情况下下的工作量量为O(n/c·dc)，是n的线性函数数E.g.,n=80,d=2,c=20280=4billionyearsat10millionnodes/sec4·220=0.4secondsat10millionnodes/sec树状结构的的CSPsTheorem:iftheconstraintgraphhasnoloops,theCSPcanbesolvedinO(n··d2)time任何一个树树状结构的的CSP问题可以在变变量个数的线线性时间内求求解ComparetogeneralCSPs,whereworst-casetimeisO(dn)这个性质同样样适用于逻辑辑与概率推理理:一个重要的例例子：语法约约束与推理复复杂度之间的的关系Algorithmfor树状结构的CSPs1.任选一个节点点作为树的根根节点，从跟跟节点到叶节节点按顺序排排列，每个节节点的父节点点都在它的前前面2.令j从n到2,在弧(Parent(Xj),Xj)上应用弧相容容算法，从Xj的值域中删除除必要的值3.令j从1到n,赋给变量Xj与变量Parent(Xj)相容的值Complexity:O(n·d2)近似树状结构构调整:删除一个变量量，修建其邻邻居的值域割集调整:删除一组变量量（环割集））使剩下的约约束图为一颗颗树环割集大小c→运行时间O(dc(n-c)d2),当c很小时比直接接回溯有巨大大的节省寻找最小的环环割集是一个个NP难题，但但存在有有效的近近似算法法本章大纲纲CSPexamplesBacktrackingsearchforCSPsProblemstructureandproblemdecompositionLocalsearchforCSPsCSPs的迭代代算法法爬山算算法、、模拟拟退火火算法法是处处理完完全状状态的的形式式化问问题（（所有有变量量已被被赋值值）的的典型型算法法应用到到CSPs:允许状状态有有未满满足的的约束束条件件操作者者再次分分配变量值值变量选选择:随机选选择任任意有有冲突突的变变量选择新新值的的时候候采用用min-conflicts（最小小冲突突）启发式式:choosevaluethatviolatesthefewestconstraints选择会会造成成与其其它变变量的的冲突突最小小的值值i.e.,爬山算算法中h(n)=totalnumberofviolatedconstraintsExample:4-Queens状态:4queensin4columns(44=256states)行动:movequeenincolumn目标测测试:noattacks评价:h(n)