約束傳播-智能科學(xué)與人工智能

約束推理

史忠植中國科學(xué)院計算技術(shù)探討所高級人工智能第三章2023/3/5史忠植約束推理2第三章約束推理3.1概述3.2回溯法3.3約束傳播3.4回跳法3.5約束推理系統(tǒng)COPS3.6ILOGSOLVER3.7約束邏輯程序設(shè)計在八皇后問題中，處理過程不是依據(jù)某種確定的計算法則，而是利用摸索和回溯的探究技術(shù)求解。為了求得合法布局，在計算機(jī)中要存儲布局的當(dāng)前狀態(tài)。從最初的布局狀態(tài)起先，一步步地進(jìn)行摸索，每摸索一步形成一個新的狀態(tài)，整個摸索過程形成了一棵隱含的狀態(tài)樹。八皇后問題7654321001234567接受DFS/BFS搜尋策略TheDFS/BFStreewillenumerateupto

648combinations(assumelimitdepthto8).64^8=2^48=2.8x10^14Noteredundancy:Q1in(1,3),Q2in(2,7)…vs.Q1in(2,7),Q2in(1,3)…2023/3/5史忠植約束推理5概述一個約束滿足問題(ConstraintSatisfactionProblem,簡稱CSP)包含一組變量與一組變量間的約束。?變量表示領(lǐng)域參數(shù)，每個變量都有一個固定的值域。一個變量的值域可能是有限的，例如一個布爾變量的值域包含兩個值；也可能是離散無限的，如整數(shù)域；也可能是連續(xù)的，照實(shí)數(shù)域。{x1,x2,…xn},{D1,D2,…Dn},.{4,5,6,7}{red,green,blue}

約束滿足問題CSPGiven:(1)setofvariables,(2)domainsofthevariables(3)constraintsthatthevariableshavetosatisfyFind:Anassignmentofvaluestothevariables,sothatthesevaluessatisfyallthegivenconstraints.Inoptimisationproblems,alsospecifyoptimisationcriterion2023/3/56史忠植約束推理2023/3/5史忠植約束推理7概述?約束可用于描述領(lǐng)域?qū)ο蟮男再|(zhì)、相互關(guān)系、任務(wù)要求、目標(biāo)等。約束滿足問題的目標(biāo)就是找到全部變量的一個（或多個）賦值，使全部約束都得到滿足。一元謂詞。序關(guān)系語言，只包含偏序關(guān)系或?qū)嵶兞可系拇笮￡P(guān)系。形如“x-y>c”的方程。單位系數(shù)的線性方程與不等式，即全部的系數(shù)為-1,0,1。隨意系數(shù)的線性方程與不等式。約束的布爾組合。代數(shù)與三角方程。2023/3/5史忠植約束推理8概述約束表示易于理解、編碼及有效實(shí)現(xiàn)，它具有以下優(yōu)點(diǎn):約束表示允許以說明性的方式來表達(dá)領(lǐng)域?qū)W問，表達(dá)實(shí)力較強(qiáng)，應(yīng)用程序只需指定問題的目標(biāo)條件及數(shù)據(jù)間的相互關(guān)系。因而具有邏輯表示的類似性質(zhì)。約束表示允許變量的域包含隨意多個值，而不像命題只取真假二值。所以它保存了問題的一些結(jié)構(gòu)信息，如變量域的大小、變量間的相關(guān)性等，從而為問題求解供應(yīng)啟發(fā)式信息。易于并行實(shí)現(xiàn)。因為約束網(wǎng)絡(luò)上的信息傳播可以認(rèn)為是同時的。適合于遞增型系統(tǒng)。約束可以遞增式地加入到約束網(wǎng)絡(luò)。易于與領(lǐng)域相關(guān)的問題求解模型相連接。各種數(shù)學(xué)規(guī)劃技術(shù)，方程求解技術(shù)等,都可以自然地嵌入約束系統(tǒng)。2023/3/5史忠植約束推理9約束推理約束搜尋約束搜尋主要探討有限域上的約束滿足。對有限域而言，約束滿足問題一般狀況下是一個NP問題。約束語言2023/3/5史忠植約束推理10約束搜尋

回溯法。

約束傳播。

智能回溯與真值維護(hù)。

可變次序例示。

局部修正法。2023/3/5史忠植約束推理11約束語言CONSTRAINTSCHIPCOPSILOG2023/3/5史忠植約束推理12CONSTRAINTS約束語言CONSTRAINTS是一個面對電路描述的約束表示語言。作為一個約束表示語言， 它運(yùn)用了符號處理技術(shù)來求解數(shù)學(xué)方程。在CONSTRAITS中，物理部件的功能及器件的結(jié)構(gòu)都用約束表示。這些約束一般是線性方程與不等式,也包括條件表達(dá)式。約束變量一般是表示物理量的實(shí)變量。也有一些取離散值的變量。如開關(guān)的狀態(tài)、三極管的工作狀態(tài)等。系統(tǒng)接受表達(dá)式推理與值推理。并實(shí)現(xiàn)相關(guān)制導(dǎo)的回溯。

2023/3/5史忠植約束推理13CONSTRAINTS約束語言CONSTRAINTS的一個優(yōu)點(diǎn)是在類型層次中表示約束，用約束來表示物理對象的功能與結(jié)構(gòu)。其缺點(diǎn)是該語言缺乏類似于面對對象語言中的方法那樣的成分，不能定義特定于某個類的概念。同時，約束傳播方法比較單一，既缺乏實(shí)域上的區(qū)間傳播機(jī)制，也缺乏有限域上的域傳播機(jī)制。

2023/3/5史忠植約束推理14約束邏輯程序設(shè)計語言CHIPCHIP(ConstrainthandlinginProlog)就是這樣較有影響一個約束邏輯程序設(shè)計語言，其目的是簡便、敏捷而有效地解決一大類組合問題。它通過供應(yīng)幾種新的計算域而增加邏輯程序設(shè)計的實(shí)力；有限域、布爾項及有理項，對于每個計算域，都供應(yīng)有效的約束求解技術(shù)，即有限域上的一樣性技術(shù)，布爾域的布爾合一技術(shù)及有理數(shù)域上的單純型法。除此以外，CHIP還包含一個一般的延遲計算機(jī)制。CHIP主要應(yīng)用于兩個領(lǐng)域:運(yùn)籌學(xué)與硬件設(shè)計。CHIP缺乏類型機(jī)制，而這種機(jī)制對于表達(dá)領(lǐng)域概念是極其重要的。2023/3/5史忠植約束推理15面對對象約束語言COPSCOPS系統(tǒng)利用面對對象技術(shù)，將說明性約束表達(dá)與類型層次結(jié)合起來。在形式上吸取了常規(guī)語言，主要是面對對象的程序設(shè)計語言的基本形式。內(nèi)部求解時接受約束推理機(jī)制，使說明性約束表達(dá)式與類型層次相結(jié)合，實(shí)現(xiàn)學(xué)問的結(jié)構(gòu)化封裝，充分發(fā)揮兩者的優(yōu)點(diǎn)，力圖實(shí)現(xiàn)一個具有較強(qiáng)表達(dá)實(shí)力和較高求解效率的約束滿足系統(tǒng)。2023/3/5史忠植約束推理16面對對象約束語言COPSCOPS的設(shè)計考慮了軟件工程的應(yīng)用要求，盡量將一個不確定問題確定化：它允許條件語句與循環(huán)語句，而不是單純以遞歸的形式來實(shí)現(xiàn)迭代計算；通過類方法的重栽實(shí)現(xiàn)同一約束的不同實(shí)現(xiàn)，提高了程序的執(zhí)行效率。COPS系統(tǒng)同時是一個漸增式的開放系統(tǒng)，用戶能通過類型層次定義，實(shí)現(xiàn)新的數(shù)據(jù)類型和新的約束關(guān)系。約束語言COPS具有很多人工智能程序設(shè)計語言的特點(diǎn)，如約束傳播、面對目標(biāo)和數(shù)據(jù)驅(qū)動的問題求解、有限步的回溯、對象分層中的繼承等。

2023/3/5史忠植約束推理17在實(shí)際應(yīng)用中，算法的表現(xiàn)形式千變?nèi)f化，但是算法的狀況也和數(shù)據(jù)結(jié)構(gòu)類似，很多算法的設(shè)計思想具有相像之處，我們可以對它們分類進(jìn)行學(xué)習(xí)和探討。常用的算法大致有如下一些：貪心法分治法：如二分法檢索回溯法動態(tài)規(guī)劃法局部搜尋法分支限界法常用的算法2023/3/5史忠植約束推理18評價一個程序優(yōu)劣的重要依據(jù)是看這個程序的執(zhí)行須要占用多少機(jī)器資源。人們最關(guān)切的就是程序所用算法運(yùn)行時所要花費(fèi)的時間代價和程序中運(yùn)用的數(shù)據(jù)結(jié)構(gòu)占有的空間代價。算法的空間代價(或稱空間困難性)：當(dāng)被解決問題的規(guī)模(以某種單位計算)由1增至n時，解該問題的算法所需占用的空間也以某種單位由f(1)增至f(n)，這時我們稱該算法的空間代價是f(n)。算法的時間代價(或稱時間困難性)：當(dāng)問題規(guī)模以某種單位由1增至n時，對應(yīng)算法所耗費(fèi)的時間也以某種單位由g(1)增至g(n)，這時我們稱算法的時間代價是g(n)。算法分析2023/3/5史忠植約束推理19窮盡搜尋方法窮盡搜尋方法即產(chǎn)生全部可能的樹，然后依據(jù)評價標(biāo)準(zhǔn)選擇一棵最優(yōu)的樹。Exhaustive-Search-Top(P){wherePisaCSPoftheform(V,D,C)}1.f:=thenullassignment2.returnExhaustive-Search(f,P)2023/3/5史忠植約束推理20窮盡搜尋方法

Exhaustive-Search(f,P)1.iffisatotalassignmentofthevariablesinP2.iffsatisfiestheconstraintsinP3.answer:=f4.else5.answer:=Unsat6.else7.v:=somevariableinPthatisnotyetassignedavaluebyf8.answer:=Unsat9.foreachvaluewhileanswer=Unsat10.f(v):=11.answer:=Exhaustive-Search(f,P)12.returnanswer2023/3/5史忠植約束推理21貪心法貪心法把構(gòu)造可行解的工作分階段來完成。在各個階段，選擇那些在某些意義下是局部最優(yōu)的方案，期望各階段的局部最優(yōu)的選擇帶來整體最優(yōu)。例：Dijkstra的最短路徑算法、Kruskal的求最小生成樹算法、信號燈問題2023/3/5史忠植約束推理22回溯算法有些問題須要徹底的搜尋才能解決問題，然而，徹底的搜尋要以大量的運(yùn)算時間為代價，對于這種狀況可以通過回溯法來去掉一些分支，從而大大削減搜尋的次數(shù)。八皇后問題迷宮問題深度優(yōu)先周游樹或圖約束推理ppt四皇后問題中隱含的狀態(tài)樹

四皇后問題2023/3/5史忠植約束推理244-QueensPuzzle2023/3/5史忠植約束推理254-QueensTree回溯算法BacktrackSearchemptyassignment1stvariable2ndvariable3rdvariableAssignment={}回溯算法BacktrackSearchemptyassignment1stvariable2ndvariable3rdvariableAssignment={(var1=v11)}回溯算法BacktrackSearchemptyassignment1stvariable2ndvariable3rdvariableAssignment={(var1=v11),(var2=v21)}回溯算法BacktrackSearchemptyassignment1stvariable2ndvariable3rdvariableAssignment={(var1=v11),(var2=v21),(var3=v31)}回溯算法BacktrackSearchemptyassignment1stvariable2ndvariable3rdvariableAssignment={(var1=v11),(var2=v21),(var3=v32)}回溯算法BacktrackSearchemptyassignment1stvariable2ndvariable3rdvariableAssignment={(var1=v11),(var2=v22)}回溯算法BacktrackSearchemptyassignment1stvariable2ndvariable3rdvariableAssignment={(var1=v11),(var2=v22),(var3=v31)}2023/3/5史忠植約束推理33回溯算法

Backtracking-Top(P)1f:=thenullassignment2returnBacktracking(f,P)2023/3/5史忠植約束推理34回溯算法

Backtracking(f,P)1iffisatotalassignmentofthevariablesinP2answer:=f3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6foreachvaluewhileanswer=Umsat7f(v):=x8iffsatisfiestheconstraintsinP9answer:=Backtracking(f,P)10returnanswer2023/3/5史忠植約束推理35BacktrackingAlgorithmBasedondepth-firstrecursivesearchApproachTestswhethersolutionhasbeenfoundIffoundsolution,returnitElseforeachchoicethatcanbemadeMakethatchoiceRecurIfrecursionreturnsasolution,returnitIfnochoicesremain,returnfailureSometimescalled“searchtree”2023/3/5史忠植約束推理36回溯算法盡管回溯法好于生成測試法，但對于非平凡問題仍舊是低效的。其緣由在于搜尋空間中不同路徑的搜尋重復(fù)相同的失敗子路徑。一些探討者認(rèn)為，造成這種反復(fù)的緣由是所謂的局部不一樣性。最簡潔的情形是所謂的結(jié)點(diǎn)不一樣性。對一個變量vi的一個一元約束。存在域中一個值vi不滿足該約束。這樣，每當(dāng)vi取到a時就會出現(xiàn)不一樣性。另一種重復(fù)的情形是所謂的弧不一樣性。2023/3/5史忠植約束推理37

約束傳播

CONSTRAINTPROPAGATION弧一樣性Arcconsistency2023/3/5史忠植約束推理38弧一樣性Arcconsistency假如對vi的當(dāng)前域中的全部值x，存在vj的當(dāng)前域中的某值y使得vi=x和vj=y是vi與vj之間的約束所允許的，則弧(vi,vj)是弧一樣的?；∫粯有缘母拍钍怯邢虻摹＜?vi,vj)是弧一樣的并不自動地意味著(vj,vi)是一樣的。2023/3/5史忠植約束推理39CONSTRAINTPROPAGATIONAlloftheMackworthalgorithmsmakeuseofaReviseprocedure.LetDvbethecurrentdomainofv,LetDwbethecurrentdomainofw,LetPbetheconstraintpredicatethatholdsbetweenvandw,thenReviseupdatesDvasfollows:2023/3/5史忠植約束推理40CONSTRAINTPROPAGATIONMackworth1977AC-1

AC-2AC-32023/3/5史忠植約束推理41約束傳播修改算法REVISE(Vi,Vj)1DELETEfalse; 2foreachxDido 3ifthereisnosuchyjDj4 suchthat(x,yj)isconsistent,5then 6 deletexfromDi; 7 DELETEtrue; 8endif 9endfor 10returnDELETE; 11endREVISE2023/3/5史忠植約束推理42弧一樣性算法AC-11Q;2repeat 3CHANGEfalse;4foreach(Vi,Vj)Qdo5 CHANGEREVISE(Vi,Vj)CHANGE;6endfor;7untilnot(CHANGE);8endAC-12023/3/5史忠植約束推理43弧一樣性算法AC-31Q;2WhileQnotempty 3Selectanddeleteanyarc(Vk,Vm)fromQ;4If(REVISE(Vk,Vm))ThenQ{(Vi,Vk)suchthat(Vi,Vk)arcs(G),ik,im};6endfor;7endwhile;8endAC-3弧一樣性算法AC-3IfXi’sdomainisfilteredalltheconstraintsassociatedwithitandothervariablesareaddedtothequeueBinaryconstraintXi,Xj弧一樣性算法AC-3時間困難性:n2=numberofconstraints(edges;nisthe#ofvariables)d=numberofvaluespervariableREMOVE-ARC-INCONSISTENCYtakesO(d2)timeEachvariableisinsertedinQueueuptodtimes,sinceatmostdvaluescanbedeletedAC3takesO(n2d3)timetorun2023/3/5史忠植約束推理46BackjumpingBackjumping-Top(P)1f:=thenullassignment2<answer,conflict-set>:=Backjumping(f,P)3returnanswer

2023/3/5史忠植約束推理47BackjumpingBackjumping(f,P)1iffisatotalassignmentofthevariablesinP2answer:=<f,>3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6conflict-set:=

7foreachvalue8f(v):=x9iffsatisfiestheconstraintsinP10<answer,new-conflicts>:=Backjumping(f,P)

2023/3/5史忠植約束推理48Backjumping11else12new-conflicts:=thesetofvariablesinaviolatedconstraint13ifanswerUnsat14return<answer,>15elseifvnew-conflicts16return<Unsat,new-conflicts>17else18conflict-set:=conflict-set(new-conflicts{v})19return<Unsat,conflict-set>2023/3/5史忠植約束推理49COPS

Constraint:predicateexpression

P(t1,...,tn)wherePisbuiltinfunction,suchas

sumtimeseq(equal)neq(notequal)ge(greatthanorequalto)gt(greatthan)alsocanbedefinedbyusers2023/3/5史忠植約束推理50COPS

Conditionalconstraint

condition1:constraint1;..conditionn:constraintn

wherecondition1,...,conditionnarebooleanexpressions.constraint1,...constraintnareconstraintsorcontraintstable.

2023/3/5史忠植約束推理51COPS

RULE

Ruleisusedtodefinenewfunction,method,predicate,oraddnewconstraintintoobject.

RULE[class::]predicate(varibles)(booleanexpression){constraint_1;

-constraint_n;CASE booleanexpression_1:constraint_1;

- booleanexpression_m:constraint_m;}

2023/3/5史忠植約束推理52COPS

Forexample:

RULEmultiple(INTEGER:*x,INTEGER:y,INTEGER:z)(neq(y,0)){ equal(x,divide(z,y)); }

z=x*y2023/3/5史忠植約束推理53COPS

CLASS[class_name][:superclass_name] { //attributesdefinitiondatetype:attribute_name; ... //ruledefinition rule_name; ... //functiondefinition function_name; ... //methoddefinition method_name;...}2023/3/5史忠植約束推理54COPS

Implementation

ProgramwrittenbyCOPSconsistsofclassesandrules.COPSconstraintprogramminglanguageisadeclarativelanguage,providingclasses,methodswhichareexistinobjectorientedlanguage.ItissimilarwithC++.COPShasthefeatures:

constraintobjectorientedlogicprogrammingproductionsystem2023/3/5史忠植約束推理55COPS

COPS_Compiler1{2Callyacctoparsetheprogramand3 togenerateinternalstructures.4Initializatiion5 CreateCopsConstanttrueNode;6 Allocatememoriesforglobalvariables.

2023/3/5史忠植約束推理56COPS7Interprtetheprogramwiththeinternalstructures.8 ConstraintnetworksarebuiltupforUnsolved9 constraintsandvariables.10whilesomeconstraintsintheconstraintnetworksaretriggered,11intepretethetriggeredconstraints.12}2023/3/5史忠植約束推理57COPSInterpreter:

1{2switch(constrainttype)3caseConstant:4returnConstant:5caseglobalvariable:6interpreteglobalvariable:7caselocalvariableorargument:8 interpretelocalvariableorargument:9caseobject-attributepair;10interpreteobject-attributepair:11casefunctioncall:2023/3/5史忠植約束推理58COPS12 interpretefunctioncall:13casemethodcall:14 interpretemethodcall:15caseCASEexpression:16 interpreteCASEexpression:17...18default:20reporterror21}2023/3/5史忠植約束推理59ILOGSOLVERCombinesobjectorientedprogrammingwithconstraintlogicprogramming,containinglogicvariables,incrementalconstraintsatisfactionandbacktracking.

variables:C++object

integervariableCtIntVarfloatingvariableCtFloatVarbooleanvariableCtBoolVarMemoryManagement

new:delete:2023/3/5史忠植約束推理60ILOGSOLVERConstraints

CtTell(x==(y+z));

Basicconstraints:=,,,<,>,+,-,*,/,subset,superset,union,intersection,member,booleanor,booleanand,booleannot,booleanxor,

CtTell((x==0)||(y==0));

CtIfThen(x<100,x=x+1);

Search

2023/3/5史忠植約束推理61ILOGSOLVERCTGOALn:howtoexecute

CTGOAL1(CtInstantiate,CtIntVar*x){CtInta=x->chooseValue();CtOr(Constraint(x==a),CtAnd(Constraint(x!=a),CtInstantiate(x)));}

2023/3/5史忠植約束推理62

ILOGSchedule1.0Schedule

CtScheduleclass

Globalobject:timeoriginal---tineMintimehorizon---timeMax

2023/3/5史忠植約束推理63

ILOGSchedule1.0Resources

CtResource

CtDiscreteResource

CtUnaryResource

CtDiscreteEnergy

CtStateResource

2023/3/5史忠植約束推理64

ILOGSchedule1.0Activities

CtActivityclass

CtIntervalActivity

Anactivityisdefinedbyitsstarttime,endtimeandduration

Activitiesrequire,provide,consumeandproduceresources2023/3/5史忠植約束推理65

SchedulingProblemPricespaidastasksbegin$1000perdayAvailability:Day0:$20000,Day15:+$90002023/3/5史忠植約束推理66Constraints

//Tocreateaschedulewithorigin0andgivenhorizon.CtSchedule*schedule=newCtSchedule(0,horizon);

//Tocreateanactivitywiththegivenduration.CtIntervalActivity*act=newCtIntervalActivity(schedule,duration);

//Topostaprecedenceconstraintbetweenact1andact2.act2->startsAfterEnd(act1,0);

2023/3/5史忠植約束推理67Constraints//Tocreateatotalbudgetoflimitedcapacity(here29000).CtDiscreteResource*res=newCtDiscreteResource(schedule,CtRequiredResource,capacity);

//Tostatethatonlycap(here20000)isavailablepriortoa//givendate(here15).res->setCapacityMax(0,date,cap);

//Tostatethatanactivityactconsumescunitsofres.act->consumes(res,c);2023/3/5史忠植約束推理68AlgorithmProgram

CtBooleanIsUnScheduled(CtActivity*act){//Returntrueifactdoesnothaveafixedstarttime.if(act->getStartVariable()->isBound())returnCtFalse;elsereturnCtTrue;}2023/3/5史忠植約束推理69AlgorithmProgramCtBooleanIsMoreUrgent(CtActivity*act1,CtActivity*act2){//Returnstrueifact1ismoreurgentthanact2.//Returnstrueifact2isunbound(==0)if(act2==0)returnCtTrue;elseif(act1->getStartMax()<act2->getStartMax())returnCtTrue;elsereturnCtFalse;}2023/3/5史忠植約束推理70AlgorithmProgram

CtActivity*SelectActivity(CtSchedule*schedule){//Returnstheunscheduledactivitywiththesmallestlatest//statrttime.Returns0ifallactivitiesarescheduled.CtActivity*bestActivity=0;//Createsaniteratortoiterateonallactivities.CtActivityIterator*iterator(schedule);CtActivity*newActivity;while(iterator.next(newactivity))if((IsUnScheduled(newActivity))&&(IsMoreUgent(newActivity,bestActivity)))bestactivity=newActivity;ret