人工智能05约束满足问题

第五章约束满足问题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≠green

Binary（二元）约束与两个变量有关,

e.g.,SA≠WA

Higher-order（高阶）约束involve3ormorevariables,

e.g.,cryptarithmetic（密码算数）columnconstraints

偏好约束

(softconstraints),e.g.,redisbetterthangreen

oftenrepresentablebyacostforeachvariableassignment（个体变量赋值的耗散）

→约束优化问题Example:密码算数变量:FTUWROX1X2X3

值域:{0,1,2,3,4,5,6,7,8,9}

约束:

alldiff(F,T,U,W,R,O)

O+O=R+10·X1

X1+W+W=U+10·X2

X2+T+T=O+10·X3X3=F,T≠0,F≠0约束超图Real-worldCSPsAssignmentproblems（分配问题）

e.g.,whoteacheswhatclass

whoreviewswhichpapersTimetablingproblems（时间表安排问题）

e.g.,whichclassisofferedwhenandwhere?Hardwareconfiguration（硬件配置问题）Transportationscheduling（交通调度）Factoryscheduling（工厂调度）Floorplanning（平面布置）Noticethatmanyreal-worldproblemsinvolvereal-valuedvariables

列举分配

指数时间

dn

Butcomplete

canwebecleveraboutexponentialtimealgorithms?

形式化描述标准搜索

(incremental增量形式化)从简单直白的方法开始，状态被定义为已被赋值的变量

初始状态:空的赋值,{}后继函数:给一个未赋值变量赋值使之不与当前状态冲突

→fail如果没有合法赋值

目标测试:检验当前赋值是否完全 1.ThisisthesameforallCSPs!

2.Everysolutionappearsatdepthnwithnvariables

→usedepth-firstsearch

3.Pathisirrelevant,socanalsousecomplete-stateformulation（完全状态形式化）

4.b=(n-l)datdepthl,hencen!·dn

leaves!!!!Backtrackingsearch回溯搜索变量赋值具有可交换性,也就是说

[WA=redthenNT=green]sameas[NT=greenthenWA=red]在搜索树的每个节点上只考虑单个变量的可能赋值

b=dandthereare

dn

leavesDepth-firstsearchforCSPswithsingle-variableassignmentsiscalled

backtrackingsearch回溯搜索是处理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—约束传播前向检验将信息从已赋值变量传播到未赋值变量，但是并不能提前检测出所有矛盾:NT

andSA

cannotbothbeblue!

约束传播必须反复应用直到不在有矛盾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?本章大纲CSPexamples

BacktrackingsearchforCSPs

Problemstructureandproblemdecomposition

LocalsearchforCSPs

问题的结构 T岛和大陆是不连通的

约束图中的连通域是可辨认的问题的结构假设每个子问题有总共n个变量中的c个变量最差情况下的工作量为O(n/c·dc)，是n的线性函数E.g.,n=80,d=2,c=20 280=4billionyearsat10millionnodes/sec 4·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难题，但存在有效的近似算法本章大纲CSPexamples

BacktrackingsearchforCSPs

Problemstructureandproblemdecomposition

LocalsearchforCSPs

CSPs的迭代算法爬山算法、模拟退火算法是处理完全状态的形式化问题（所有变量已被赋值）的典型算法应用到CSPs:

允许状态有未满足的约束条件

操作者再次分配变量值变量选择:随机选择任意有冲突的变量选择新值的时候采用

min-conflicts（最小冲突）启发式: choosevaluethatviolatesthefewestcons