高級人工智能之約束推理

高級人工智能第三章約束推理史忠植

中國科學院計算技術所10/19/20221史忠植高級人工智能第三章約束推理理3.1概概述述3.2回回溯溯法3.3約約束束傳播3.4回回跳跳法3.5約約束束推理系系統(tǒng)COPS3.6ILOGSOLVER1/15/20202史忠植高高級人人工智能能3.1概述最優(yōu)化問問題經(jīng)濟學所所推崇的的帕累托托最優(yōu)::幾個人拎拎著水桶桶在一個個水龍頭頭前面排排隊打水水，水桶有大有有小。他他們怎樣樣排隊，，才能使使得總的的排隊時間最短短。這是是一個尋尋求“最最優(yōu)化””的題目目，目標標是節(jié)省總總的排隊隊時間，，達到最最優(yōu)。1/15/20203史忠植高高級人人工智能能3.1概述優(yōu)化問題題

運籌學遺傳算法法神經(jīng)網(wǎng)絡絡約束推理理1/15/20204史忠植高高級人人工智能能運籌學的的工作步步驟1）提出出和形成成問題，，2）建立立模型，，3）求解解，4）解的的檢驗，，5）解的的控制，，6）解的的實施。。1/15/20205史忠植高高級人人工智能能線性規(guī)劃劃問題例1(廣廣告方式式的選擇擇)中華華家電公公司推銷銷一種新新型洗衣衣機,有有關數(shù)據(jù)據(jù)見下表表.銷售售部第一一月的廣廣告預算算為20000元,要要求至少少有8電電視商業(yè)業(yè)節(jié)目,,15家家報紙廣廣告/電電視廣告告費不得得超過12000元,,電臺廣廣播至少少隔日有有一次..現(xiàn)問該該公司銷銷售部應應當采用用怎樣的的廣告宣宣傳計劃劃,才能能取得最最好的效效果?1/15/20206史忠植高高級人人工智能能表1廣告方式廣告費用(元/次)可用最高次數(shù)/月期望的宣傳效果/單位電視臺a(白天,1分鐘)5001650電視臺b(晚上,30鈔)10001080每日晨報/(半版)1002430星期日報/(半版)300440廣播電臺/(1分鐘)8025151/15/20207史忠植高高級人人工智能能1/15/20208史忠植高高級人人工智能能

1/15/20209史忠植高高級人人工智能能

1/15/202010史忠植高高級人人工智能能求解---單純形形法將所給問問題化為為標準形形找出一個個初始可可行基,,建立初初始單純純形表檢查所有有檢驗數(shù)數(shù)(若全全為非負負,則已已得到最最優(yōu)解,,計算停停止.否否則繼續(xù)續(xù)下一步步)考察是否否無解((若是,,計算停停止,否否則繼續(xù)續(xù)下一步步)確定入基基變量,,出基變變量對初始單單純形表表進行單單純形變變換1/15/202011史忠植高高級人人工智能能3.1概述一個約束束滿足問問題(ConstraintSatisfactionProblem,簡稱CSP))包含一組組變量與與一組變變量間的的約束。。?變量表表示領域域參數(shù)，，每個變變量都有有一個固固定的值值域。一個變量量的值域域可能是是有限的的，例如如一個布布爾變量量的值域包含兩兩個值；；也可能能是離散散無限的的，如整整數(shù)域；；也可能是連續(xù)續(xù)的，如如實數(shù)域域。{x1,x2,……xn},{D1,,D2,,…Dn},..{4,5,6,,7}red,,green,blue}}

1/15/202012史忠植高高級人人工智能能3.1概述?約束可可用于描描述領域域對象的的性質、、相互關關系、任任務要求、目目標等。。約束滿滿足問問題的的目標就就是找到到所有變量的一一個（或或多個））賦值，，使所有有約束都都得到滿滿足。一元謂詞詞。序關系語語言，只只包含偏偏序關系系或實變變量上的的大小關關系。形如“x-y>>c””的方程。。單位系數(shù)數(shù)的線性性方程與與不等式式，即所所有的系系數(shù)為-1,0,1。。任意系數(shù)數(shù)的線性性方程與與不等式式。約束的布布爾組合合。代數(shù)與三三角方程程。1/15/202013史忠植高高級人人工智能能3.1概述約束表示示易于理理解、編編碼及有有效實現(xiàn)現(xiàn)，它具具有以下下優(yōu)點::約束表示示允許以以說明性性的方式式來表達達領域知知識，表表達能力較強強，應用用程序只只需指定定問題的的目標條條件及數(shù)數(shù)據(jù)間的相互關關系。因因而具有有邏輯表表示的類類似性質質。約束表示示允許變變量的域域包含任任意多個個值，而而不像命命題只取真假假二值。。所以它它保存了了問題的的一些結結構信息息，如變量域的的大小、、變量間間的相關關性等，，從而為為問題求求解提供供啟發(fā)式信信息。易于并行行實現(xiàn)。。因為約約束網(wǎng)絡絡上的信信息傳播播可以認認為是同時的。。適合于遞遞增型系系統(tǒng)。約約束可以以遞增式式地加入入到約束束網(wǎng)絡。。易于與領領域相關關的問題題求解模模型相銜銜接。各各種數(shù)學學規(guī)劃技技術，方程程求解技技術等,,都可可以自然然地嵌入入約束系系統(tǒng)。1/15/202014史忠植高高級人人工智能能3.1約束推理理約束搜索索約束搜索索主要研研究有限限域上的的約束滿滿足。對對有限域域而言，，約束滿足足問題一一般情況況下是一個個NP問題。約束語言言1/15/202015史忠植高高級人人工智能能3.1約束搜索索回溯法。。約束傳播播。智能回溯溯與真值值維護。?？勺兇涡蛐蚶?。。局部修正正法。1/15/202016史忠植高高級人人工智能能約束語言言CONSTRAINTSCHIPCOPSILOG1/15/202017史忠植高高級人人工智能能CONSTRAINTS約束語言言CONSTRAINTS是一個面面向電路路描述的的約束表表示語言言。作為一個個約束表表示語言言，它它使用了了符號處處理技術術來求解解數(shù)學方方程。在CONSTRAITS中，物理理部件的的功能及及器件的的結構都都用約束束表示。。這些約束束一般是是線性方方程與不不等式,,也包包括條件件表達式式。約束束變量一般是表表示物理理量的實實變量。。也有一一些取離離散值的的變量。。如開關關的狀態(tài)、三極極管的工工作狀態(tài)態(tài)等。系系統(tǒng)采用用表達式式推理與與值推理理。并實實現(xiàn)相關制導導的回溯溯。

1/15/202018史忠植高高級人人工智能能CONSTRAINTS約束語言言CONSTRAINTS的一個優(yōu)優(yōu)點是在在類型層層次中表表示約束束，用約約束來表示物物理對象象的功能能與結構構。其缺缺點是該該語言缺缺乏類似似于面向向對象語言言中的方方法那樣樣的成分分，不能能定義特特定于某某個類的的概念。。同時，約約束傳播播方法比比較單一一，既缺缺乏實域域上的區(qū)區(qū)間傳播播機制，，也缺乏有有限域上上的域域傳播機機制。

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

1/15/202022史忠植高高級人人工智能能在實際應應用中，，算法的的表現(xiàn)形形式千變變?nèi)f化，，但是算算法的情情況也和和數(shù)據(jù)結結構類似似，許多多算法的的設計思思想具有有相似之之處，我我們可以以對它們們分類進進行學習習和研究究。常用的算算法大致致有如下下一些：：貪心法分治法：：如二分分法檢索索回溯法動態(tài)規(guī)劃劃法局部搜索索法分支限界界法1/15/202023史忠植高高級人人工智能能算法分析析評價一個個程序優(yōu)優(yōu)劣的重重要依據(jù)據(jù)是看這這個程序序的執(zhí)行行需要占占用多少少機器資資源。人人們最關關心的就就是程序序所用算算法運行行時所要要花費的的時間代價價和程序中中使用的的數(shù)據(jù)結結構占有有的空間代價價。算法的空空間代價價(或稱空間復雜雜性)：當被被解決問問題的規(guī)規(guī)模(以以某種單單位計算算)由1增至n時，解該該問題的的算法所所需占用用的空間間也以某某種單位位由f(1)增至f(n)，這時我們們稱該算算法的空空間代價價是f(n)。算法的時時間代價價(或稱時間復雜雜性)：當問問題規(guī)模模以某種種單位由由1增至至n時，對應應算法所所耗費的的時間也也以某種種單位由由g(1)增至g(n)，這時我們們稱算法法的時間間代價是是g(n)。1/15/202024史忠植高高級人人工智能能窮盡搜索索方法窮盡搜索索方法即產(chǎn)生所所有可能能的樹，，然后根根據(jù)評價價標準選選擇一棵棵最優(yōu)的的樹。Exhaustive-Search-Top((P){{wherePisaCSPoftheform(V,,D,C)}1.f::=thenullassignment2.returnExhaustive-Search(f,P))1/15/202025史忠植高高級人人工智能能窮盡搜索索方法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.returnanswer1/15/202026史忠植高高級人人工智能能貪心法貪心法把把構造可可行解的的工作分分階段來來完成。。在各個個階段，，選擇那那些在某某些意義義下是局局部最優(yōu)優(yōu)的方案案，期望望各階段段的局部部最優(yōu)的的選擇帶帶來整體體最優(yōu)。。例：Dijkstra的最最短路徑徑算法、、Kruskal的求求最小生生成樹算算法、信信號燈問問題1/15/202027史忠植高高級人人工智能能回溯算法法有些問題題需要徹徹底的搜搜索才能能解決問問題，然然而，徹徹底的搜搜索要以以大量的的運算時時間為代代價，對對于這種種情況可可以通過過回溯法法來去掉掉一些分分支，從從而大大大減少搜搜索的次次數(shù)。八皇后問問題迷宮問題題深度優(yōu)先先周游樹樹或圖1/15/202028史忠植高高級人人工智能能回溯算法法Backtracking--Top(P))1f::=thenullassignment2returnBacktracking((f,P)1/15/202029史忠植高高級人人工智能能回溯算法法Backtracking((f,P)1iffisatotalassignmentofthevariablesinP2answer::=f3else4v::=somevariableinPthatisnotyetassignedavaluebyf5answer::=Unsat6foreachvaluewhileanswer==Umsat7f(v)::=x8iffsatisfiestheconstraintsinP9answer::=Backtracking((f,P)10returnanswer1/15/202030史忠植高高級人人工智能能回溯算法法盡管回溯溯法好于于生成測測試法，，但對于于非平凡凡問題仍仍然是低低效的。。其原因因在于搜搜索空間間中不同同路徑的的搜索重重復相同同的失敗敗子路徑徑。一些些研究者者認為，，造成這這種反復復的原因因是所謂謂的局部部不一致致性。最最簡單的的情形是是所謂的的結點不不一致性性。對一一個變量量vi的一個一一元約束束。存在在域中一一個值vi不滿足該該約束。。這樣，，每當vi取到a時就會出出現(xiàn)不一致性性。另一種重重復的情情形是是所謂的的弧不一一致性。。1/15/202031史忠植高高級人人工智能能3.3約束傳播播CONSTRAINTPROPAGATION弧一致性性Arcconsistency1/15/202032史忠植高高級人人工智能能弧一致性性Arcconsistency如果對vi的當前域域中的所所有值x，存在vj的當前域域中的某某值y使得vi=x和vj=y是vi與vj之間的約約束所允允許的，，則弧((vi,vj)是弧一致致的。弧一致性性的概念念是有向向的。即即(vi,vj)是弧一致致的并不不自動地地意味著著(vj,vi)是一致的的。1/15/202033史忠植高高級人人工智能能3.3CONSTRAINTPROPAGATIONAlloftheMackworthalgorithmsmakeuseofaReviseprocedure.LetDvbethecurrentdomainofv,LetDwbethecurrentdomainofw,LetPbetheconstraintpredicatethatholdsbetweenvandw,,thenReviseupdatesDvasfollows:1/15/202034史忠植高高級人人工智能能CONSTRAINTPROPAGATIONMackworth1977AC-1AC-2AC-31/15/202035史忠植高高級人人工智能能約束傳播播修改算算法REVISE((Vi,,Vj))1DELETEfalse;2foreachxDido3ifthereisnosuchyjDj4 suchthat(x,yj)isconsistent,5then6deletexfromDi;;7DELETEtrue;8endif9endfor10returnDELETE;11endREVISE1/15/202036史忠植高高級人人工智能能AC-11Q;2repeat3CHANGEfalse;4foreach((Vi,Vj)Qdo5CHANGEREVISE((Vi,,Vj)CHANGE;;6endfor;7untilnot(CHANGE);;8endAC-11/15/202037史忠植高高級人人工智能能AC-31Q;2WhileQnotempty3Selectanddeleteanyarc((Vk,Vm)fromQ;4If(REVISE((Vk,Vm))ThenQ{(Vi,Vk)suchthat((Vi,,Vk)arcs(G),ik,im};6endfor;7endwhile;8endAC-31/15/202038史忠植高高級人人工智能能BackjumpingBackjumping-Top(P))1f::=thenullassignment2<<answer,,conflict-set>::=Backjumping(f,P)3returnanswer

1/15/202039史忠植高高級人人工智能能BackjumpingBackjumping(f,P))1iffisatotalassignmentofthevariablesinP2answer::=<<f,,>3else4v::=somevariableinPthatisnotyetassignedavaluebyf5answer::=Unsat6conflict-set::=

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

1/15/202040史忠植高高級人人工智能能Backjumping11else12new-conflicts::=thesetofvariablesinaviolatedconstraint13ifanswerUnsat14return<<answer,>15elseifvnew--conflicts16return<<Unsat,,new-conflicts>>17else18conflict-set::=conflict-set(new-conflicts{v}))19return<<Unsat,conflict--set>1/15/202041史忠植高高級人人工智能能COPSConstraint:predicateexpression

P(t1,....,,tn)wherePisbuiltinfunction,suchassumtimeseq(equal))neq(notequal)ge(greatthanorequalto)gt(greatthan)alsocanbedefinedbyusers1/15/202042史忠植高高級人人工智能能COPSConditionalconstraint

condition1:constraint1;..conditionn:constraintn

wherecondition1,....,,conditionnarebooleanexpressions.constraint1,....constraintnareconstraintsorcontraintstable.1/15/202043史忠植高高級人人工智能能COPSRULERuleisusedtodefinenewfunction,method,predicate,,oraddnewconstraintintoobject.

RULE[class:::]predicate((varibles)(booleanexpression){constraint_1;; -constraint_n;;CASEbooleanexpression_1::constraint_1;;-booleanexpression_m::constraint_m;;}

1/15/202044史忠植高高級人人工智能能COPS

Forexample:

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

z=x**y1/15/202045史忠植高高級人人工智能能COPSCLASS[[class__name][[:superclass__name] {//attributesdefinitiondatetype::attribute__name;...//ruledefinitionrule_name;;...//functiondefinitionfunction_name;...//methoddefinitionmethod__name;...}1/15/202046史忠植高高級人人工智能能COPSImplementation

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

constraintobjectorientedlogicprogrammingproductionsystem1/15/202047史忠植高高級人人工智能能COPSCOPS_Compiler1{{2Callyacctoparsetheprogramand3togenerateinternalstructures.4Initializatiion5CreateCopsConstanttrueNode;6Allocatememoriesforglobalvariables.1/15/202048史忠植高高級人人工智能能COPS7Interprtetheprogramwiththeinternalstructures.8ConstraintnetworksarebuiltupforUnsolved9constraintsandvariables.10whilesomeconstraintsintheconstraintnetworksaretriggered,,11intepretethetriggeredconstraints.12}}1/15/202049史忠植高高級人人工智能能COPSInterpreter:

1{{2switch((constrainttype)3caseConstant::4returnConstant:5caseglobalvariable:6interpreteglobalvariable::7caselocalvariableorargument::8interpretelocalvariableorargument:9caseobject-attributepair;10interpreteobject--attributepair::11casefunctioncall:1/15/202050史忠植高高級人人工智能能COPS12interpretefunctioncall:13casemethodcall:14interpretemethodcall::15caseCASEexpression::16interpreteCASEexpression:17.....18default:20reporterror21}}1/15/202051史忠植高高級人人工智能能ILOGSOLVERCombinesobjectorientedprogrammingwithconstraintlogicprogramming,containinglogicvariables,incrementalconstraintsatisfactionandbacktracking.

variables::C++object

integervariableCtIntVarfloatingvariableCtFloatVarbooleanvariableCtBoolVarMemoryManagement

new::delete::1/15/202052史忠植高高級人人工智能能ILOGSOLVERConstraints

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

1/15/202053史忠植高高級人人工智能能ILOGSOLVERCTGOALn:howtoexecute

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

1/15/202054史忠植高高級人人工智能能ILOGSchedule1..0Schedule

CtScheduleclass

Globalobject:timeoriginal----tineMintimehorizon-----timeMax

1/15/202055史忠植高高級人人工智能能ILOGSchedule1..0Resources

CtResource

CtDiscreteResource

CtUnaryResource

CtDiscreteEnergyCtStateResource

1/15/202056史忠植高高級人人工智能能ILOGSchedule1..0Activities

CtActivityclass

CtIntervalActivity

Anactivityisdefinedbyitsstarttime,endtimeandduration

Activitiesrequire,,provide,,consumeandproduceresources1/15/202057史忠植高高級人人工智能能SchedulingProblemPricespaidastasksbegin$$1000perdayAvailability::Day0:$20000,Day15:++$90001/15/202058史忠植高高級人人工智能能Constraints//Tocreateaschedulewithorigin0andgivenhorizon.CtSchedule*schedule=newCtSchedule(0,horizon);;

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

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

1/15/202059史忠植高高級人人工智能能Constraints//Tocreateatotalbudgetoflimitedcapacity((here29000)..CtDiscreteResource*res=newCtDiscreteResource(schedule,,CtRequiredResource,capacity);;

//Tostatethatonlycap(here20000)isavailablepriortoa//givendate(here15).