高級人工智能之約束推理

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

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

優(yōu)化問題

運(yùn)籌學(xué)

遺傳算法

神經(jīng)網(wǎng)絡(luò)

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

1/17/20239

1/17/202310求解--單純純形法將所給問題化化為標(biāo)準(zhǔn)形找出一個初始始可行基,建建立初始單純純形表檢查所有檢驗驗數(shù)(若全為為非負(fù),則已已得到最優(yōu)解解,計算停止止.否則繼續(xù)續(xù)下一步)考察是否無解解(若是,計計算停止,否否則繼續(xù)下一一步)確定入基變量量,出基變量量對初始單純形形表進(jìn)行單純純形變換12/31/2022113.1概述一個約束滿足足問題(ConstraintSatisfactionProblem,簡稱CSP)包含一組組變量與一組組變量間的約約束。?變量表示領(lǐng)領(lǐng)域參數(shù)，每每個變量都有有一個固定的的值域。一個變變量的的值域域可能能是有有限的的，例例如一一個布布爾變變量的的值域包含含兩個個值；；也可可能是是離散散無限限的，，如整整數(shù)域域；也也可能是連連續(xù)的的，如如實數(shù)數(shù)域。。{x1,x2,…xn},{D1,D2,…Dn},.{4,5,6,7}red,green,blue}12/31/2022123.1概述?約束束可用用于描描述領(lǐng)領(lǐng)域?qū)ο蟮牡男再|(zhì)質(zhì)、相相互關(guān)關(guān)系、、任務(wù)務(wù)要求、、目標(biāo)標(biāo)等。。約束束滿滿足問問題的的目目標(biāo)就就是找找到所所有變量的的一個個（或或多個個）賦賦值，，使所所有約約束都都得到到滿足足。一元謂謂詞。。序關(guān)系系語言言，只只包含含偏序序關(guān)系系或?qū)崒嵶兞苛可系牡拇笮⌒￡P(guān)系系。形如““x-y>c””的的方程程。單位系系數(shù)的的線性性方程程與不不等式式，即即所有有的系系數(shù)為為-1,0,1。。任意系系數(shù)的的線性性方程程與不不等式式。約束的的布爾爾組合合。代數(shù)與與三角角方程程。12/31/2022133.1概述約束表示示易于理理解、編編碼及有有效實現(xiàn)現(xiàn)，它具具有以下下優(yōu)點:約束表示示允許以以說明性性的方式式來表達(dá)達(dá)領(lǐng)域知知識，表表達(dá)能力較強(qiáng)強(qiáng)，應(yīng)用用程序只只需指定定問題的的目標(biāo)條條件及數(shù)數(shù)據(jù)間的相互關(guān)關(guān)系。因因而具有有邏輯表表示的類類似性質(zhì)質(zhì)。約束表示示允許變變量的域域包含任任意多個個值，而而不像命命題只取真假假二值。。所以它它保存了了問題的的一些結(jié)結(jié)構(gòu)信息息，如變量域的的大小、、變量間間的相關(guān)關(guān)性等，，從而為為問題求求解提供供啟發(fā)式信信息。易于并行行實現(xiàn)。。因為約約束網(wǎng)絡(luò)絡(luò)上的信信息傳播播可以認(rèn)認(rèn)為是同時的。。適合于遞遞增型系系統(tǒng)。約約束可以以遞增式式地加入入到約束束網(wǎng)絡(luò)。。易于與領(lǐng)領(lǐng)域相關(guān)關(guān)的問題題求解模模型相銜銜接。各各種數(shù)學(xué)學(xué)規(guī)劃技技術(shù)，方程程求解技技術(shù)等,都可可以自然然地嵌入入約束系系統(tǒng)。12/31/2022143.1約束推理理約束搜索索約束搜索索主要研研究有限限域上的的約束滿滿足。對對有限域域而言，，約束滿足足問題一一般情況況下是一個個NP問題題。約束語言言12/31/2022153.1約束搜索回溯法。約束傳播。。智能回溯與與真值維護(hù)護(hù)?？勺兇涡蚶尽＞植啃拚ǚ?。12/31/202216約束語言CONSTRAINTSCHIPCOPSILOG12/31/202217CONSTRAINTS約束束語言CONSTRAINTS是一一個面向電電路描述的的約束表示示語言。作為一個約約束表示語語言，它它使用了符符號處理技技術(shù)來求解解數(shù)學(xué)方程程。在CONSTRAITS中，，物理部件件的功能及及器件的結(jié)結(jié)構(gòu)都用約約束表示。。這些約束一一般是線性性方程與不不等式,也也包括條條件表達(dá)式式。約束變變量一般是表示示物理量的的實變量。。也有一些些取離散值值的變量。。如開關(guān)的的狀態(tài)、三極管管的工作狀狀態(tài)等。系系統(tǒng)采用表表達(dá)式推理理與值推理理。并實現(xiàn)現(xiàn)相關(guān)制導(dǎo)的的回溯。12/31/202218CONSTRAINTS約束束語言CONSTRAINTS的的一個優(yōu)點點是在類型型層次中表表示約束，，用約束來表示物理理對象的功功能與結(jié)構(gòu)構(gòu)。其缺點點是該語言言缺乏類似似于面向?qū)ο笳Z言中中的方法那那樣的成分分，不能定定義特定于于某個類的的概念。同時，約束束傳播方法法比較單一一，既缺乏乏實域上的的區(qū)間傳播播機(jī)制，也缺乏有限限域上的域域傳播機(jī)機(jī)制。12/31/202219約束邏輯程程序設(shè)計語語言CHIPCHIP(ConstrainthandlinginProlog)就就是這樣較較有影響一個約束邏邏輯程序設(shè)設(shè)計語言，，其目的是是簡便、靈靈活而有效效地解決一大類組合合問題。它它通過提供供幾種新的的計算域而而增強(qiáng)邏輯輯程序設(shè)計的能力；；有限域、、布爾項及及有理項，，對于每個個計算域，，都提供有效的約束束求解技術(shù)術(shù)，即有限限域上的一一致性技術(shù)術(shù)，布爾域域的布爾合一技術(shù)及及有理數(shù)域域上的單純純型法。除除此以外，，CHIP還包含一一個一般的延遲遲計算機(jī)制制。CHIP主主要應(yīng)用用于兩個領(lǐng)領(lǐng)域:運(yùn)運(yùn)籌學(xué)與硬硬件設(shè)計。。CHIP缺缺乏類型型機(jī)制，而而這種機(jī)制制對于表達(dá)達(dá)領(lǐng)域概念念是極其重重要的。12/31/202220面向?qū)ο蠹s束束語言COPSCOPS系統(tǒng)統(tǒng)利用面向?qū)ο蠹夹g(shù)，將將說明性約束束表達(dá)與類型型層次結(jié)合起來。在在形式上吸收收了常規(guī)語言言，主要是面面向?qū)ο蟮某坛绦蛟O(shè)計語言的基本本形式。內(nèi)部部求解時采用用約束推理機(jī)機(jī)制，使說明明性約束表達(dá)式與類類型層次相結(jié)結(jié)合，實現(xiàn)知知識的結(jié)構(gòu)化化封裝，充分分發(fā)揮兩者的優(yōu)點，，力圖實現(xiàn)一一個具有較強(qiáng)強(qiáng)表達(dá)能力和和較高求解效效率的約束滿足系統(tǒng)統(tǒng)。12/31/202221面向?qū)ο蠹s束束語言COPSCOPS的設(shè)設(shè)計考慮了軟軟件工程的應(yīng)應(yīng)用要求，盡盡量將一個不不確定問題確定化：它它允許條件語語句與循環(huán)語語句，而不是是單純以遞歸的形形式來實現(xiàn)迭迭代計算；通通過類方法法的重栽實現(xiàn)現(xiàn)同一約束的不同實實現(xiàn)，提高了了程序的執(zhí)行行效率。COPS系統(tǒng)同同時是一個漸增式的開放放系統(tǒng)，用戶戶能通過類型型層次定義，，實現(xiàn)新的數(shù)數(shù)據(jù)類型和新的約束束關(guān)系。約束束語言COPS具有許多多人工智能程程序設(shè)計語言的特點，如如約束傳播、、面向目標(biāo)和和數(shù)據(jù)驅(qū)動的的問題求解、、有限步的回溯、對對象分層中的的繼承等。12/31/202222在實際應(yīng)用中中，算法的表表現(xiàn)形式千變變?nèi)f化，但是是算法的情況況也和數(shù)據(jù)結(jié)結(jié)構(gòu)類似，許許多算法的設(shè)設(shè)計思想具有有相似之處，，我們可以對對它們分類進(jìn)進(jìn)行學(xué)習(xí)和研研究。常用的算法大大致有如下一一些：貪心法分治法：如二二分法檢索回溯法動態(tài)規(guī)劃法局部搜索法分支限界法12/31/202223算法法分分析析評價價一一個個程程序序優(yōu)優(yōu)劣劣的的重重要要依依據(jù)據(jù)是是看看這這個個程程序序的的執(zhí)執(zhí)行行需需要要占占用用多多少少機(jī)機(jī)器器資資源源。。人人們們最最關(guān)關(guān)心心的的就就是是程程序序所所用用算算法法運(yùn)運(yùn)行行時時所所要要花花費費的的時間間代代價價和程程序序中中使使用用的的數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)占占有有的的空間間代代價價。算法法的的空空間間代代價價(或或稱稱空間間復(fù)復(fù)雜雜性性)：：當(dāng)當(dāng)被被解解決決問問題題的的規(guī)規(guī)模模(以以某某種種單單位位計計算算)由由1增增至至n時，，解解該該問問題題的的算算法法所所需需占占用用的的空空間間也也以以某某種種單單位位由由f(1)增增至至f(n)，，這這時時我我們們稱稱該該算算法法的的空空間間代代價價是是f(n)。。算法法的的時時間間代代價價(或或稱稱時間間復(fù)復(fù)雜雜性性)：：當(dāng)當(dāng)問問題題規(guī)規(guī)模模以以某某種種單單位位由由1增增至至n時，，對對應(yīng)應(yīng)算算法法所所耗耗費費的的時時間間也也以以某某種種單單位位由由g(1)增增至至g(n)，，這這時時我我們們稱稱算算法法的的時時間間代代價價是是g(n)。。12/31/202224窮盡搜索索方法窮盡搜索索方法即產(chǎn)生所所有可能能的樹，，然后根根據(jù)評價價標(biāo)準(zhǔn)選選擇一棵棵最優(yōu)的的樹。Exhaustive-Search-Top(P){wherePisaCSPoftheform(V,D,C)}1.f:=thenullassignment2.returnExhaustive-Search(f,P)12/31/202225窮盡搜索索方法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.returnanswer12/31/202226貪心法貪心法把構(gòu)造造可行解的工工作分階段來來完成。在各各個階段，選選擇那些在某某些意義下是是局部最優(yōu)的的方案，期望望各階段的局局部最優(yōu)的選選擇帶來整體體最優(yōu)。例：Dijkstra的最短短路徑算法、、Kruskal的求最最小生成樹算算法、信號燈燈問題12/31/202227回溯算法有些問題需要要徹底的搜索索才能解決問問題，然而，，徹底的搜索索要以大量的的運(yùn)算時間為為代價，對于于這種情況可可以通過回溯溯法來去掉一一些分支，從從而大大減少少搜索的次數(shù)數(shù)。八皇后問題迷宮問題深度優(yōu)先周游游樹或圖12/31/202228回溯算法Backtracking-Top(P)1f:=thenullassignment2returnBacktracking(f,P)12/31/202229回溯溯算算法法Backtracking(f,P)1iffisatotalassignmentofthevariablesinP2answer:=f3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6foreachvaluewhileanswer=Umsat7f(v):=x8iffsatisfiestheconstraintsinP9answer:=Backtracking(f,P)10returnanswer12/31/202230回溯溯算算法法盡管管回回溯溯法法好好于于生生成成測測試試法法，，但但對對于于非非平平凡凡問問題題仍仍然然是是低低效效的的。。其其原原因因在在于于搜搜索索空空間間中中不不同同路路徑徑的的搜搜索索重重復(fù)復(fù)相相同同的的失失敗敗子子路路徑徑。。一一些些研研究究者者認(rèn)認(rèn)為為，，造造成成這這種種反反復(fù)復(fù)的的原原因因是是所所謂謂的的局局部部不不一一致致性性。。最最簡簡單單的的情情形形是是所所謂謂的的結(jié)結(jié)點點不不一一致致性性。。對對一一個個變變量量vi的的一一個個一一元元約約束束。。存存在在域域中中一一個個值值vi不不滿滿足足該該約約束束。。這這樣樣，，每每當(dāng)當(dāng)vi取取到到a時時就就會會出出現(xiàn)現(xiàn)不一致性。另一種重復(fù)的的情形是所所謂的弧不一一致性。12/31/2022313.3約約束傳播CONSTRAINTPROPAGATION弧一致性Arcconsistency12/31/202232弧一致性Arcconsistency如果對vi的當(dāng)前前域中的所所有值x，，存在vj的當(dāng)前域域中的某值值y使得vi=x和vj=y是vi與vj之之間的約束束所允許的的，則弧(vi,vj)是是弧一致的的。弧一致性的的概念是有有向的。即即(vi,vj)是弧一致的的并不自動動地意味著著(vj,vi)是一致的的。12/31/2022333.3CONSTRAINTPROPAGATIONAlloftheMackworthalgorithmsmakeuseofaReviseprocedure.LetDvbethecurrentdomainofv,LetDwbethecurrentdomainofw,LetPbetheconstraintpredicatethatholdsbetweenvandw,thenReviseupdatesDvasfollows:12/31/202234CONSTRAINTPROPAGATIONMackworth1977AC-1AC-2AC-312/31/202235約束傳播播修改算算法REVISE(Vi,Vj)1DELETEfalse;2foreachxDido3ifthereisnosuchyjDj4 suchthat(x,yj)isconsistent,5then6deletexfromDi;7DELETEtrue;8endif9endfor10returnDELETE;11endREVISE12/31/202236AC-11Q;2repeat3CHANGEfalse;4foreach(Vi,Vj)Qdo5CHANGEREVISE(Vi,Vj)CHANGE;6endfor;7untilnot(CHANGE);8endAC-112/31/202237AC-31Q;2WhileQnotempty3Selectanddeleteanyarc(Vk,Vm)fromQ;4If(REVISE(Vk,Vm))ThenQ{(Vi,Vk)suchthat(Vi,Vk)arcs(G),ik,im};6endfor;7endwhile;8endAC-312/31/202238BackjumpingBackjumping-Top(P)1f:=thenullassignment2<answer,conflict-set>:=Backjumping(f,P)3returnanswer12/31/202239BackjumpingBackjumping(f,P)1iffisatotalassignmentofthevariablesinP2answer:=<f,>3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6conflict-set:=7foreachvalue8f(v):=x9iffsatisfiestheconstraintsinP10<answer,new-conflicts>:=Backjumping(f,P)12/31/202240Backjumping11else12new-conflicts:=thesetofvariablesinaviolatedconstraint13ifanswerUnsat14return<answer,>15elseifvnew-conflicts16return<Unsat,new-conflicts>17else18conflict-set:=conflict-set(new-conflicts{v})19return<Unsat,conflict-set>12/31/202241COPSConstraint:predicateexpressionP(t1,...,tn)wherePisbuiltinfunction,suchassumtimeseq(equal)neq(notequal)ge(greatthanorequalto)gt(greatthan)alsocanbedefinedbyusers12/31/202242COPSConditionalconstraintcondition1:constraint1;..conditionn:constraintnwherecondition1,...,conditionnarebooleanexpressions.constraint1,...constraintnareconstraintsorcontraintstable.12/31/202243COPSRULERuleisusedtodefinenewfunction,method,predicate,oraddnewconstraintintoobject.RULE[class::]predicate(varibles)(booleanexpression){constraint_1;-constraint_n;CASEbooleanexpression_1:constraint_1;-booleanexpression_m:constraint_m;}12/31/202244COPSForexample:RULEmultiple(INTEGER:*x,INTEGER:y,INTEGER:z)(neq(y,0)){equal(x,divide(z,y));}z=x*y12/31/202245COPSCLASS[class_name][:superclass_name]{//attributesdefinitiondatetype:attribute_name;...//ruledefinitionrule_name;...//functiondefinitionfunction_name;...//methoddefinitionmethod_name;...}12/31/202246COPSImplementationProgramwrittenbyCOPSconsistsofclassesandrules.COPSconstraintprogramminglanguageisadeclarativelanguage,providingclasses,methodswhichareexistinobjectorientedlanguage.ItissimilarwithC++.COPShasthefeatures:constraintobjectorientedlogicprogrammingproductionsystem12/31/202247COPSCOPS_Compiler1{2Callyacctoparsetheprogramand3togenerateinternalstructures.4Initializatiion5CreateCopsConstanttrueNode;6Allocatememoriesforglobalvariables.12/31/202248COPS7Interprtetheprogramwiththeinternalstructures.8ConstraintnetworksarebuiltupforUnsolved9constraintsandvariables.10whilesomeconstraintsintheconstraintnetworksaretriggered,11intepretethetriggeredconstraints.12}12/31/202249COPSInterpreter:1{2switch(constrainttype)3caseConstant:4returnConstant:5caseglobalvariable:6interpreteglobalvariable:7caselocalvariableorargument:8interpretelocalvariableorargument:9caseobject-attributepair;10interpreteobject-attributepair:11casefunctioncall:12/31/202250COPS12interpretefunctioncall:13casemethodcall:14interpretemethodcall:15caseCASEexpression:16interpreteCASEexpression:17...18default:20reporterror21}12/31/202251ILOGSOLVERCombinesobjectorientedprogrammingwithconstraintlogicprogramming,containinglogicvariables,incrementalconstraintsatisfactionandbacktracking.variables:C++objectintegervariableCtIntVarfloatingvariableCtFloatVarbooleanvariableCtBoolVarMemoryManagementnew:delete:12/31/202252ILOGSOLVERConstraintsCtTell(x==(y+z));Basicconstraints:=,,,<,>,+,-,*,/,subset,superset,union,intersection,member,booleanor,booleanand,booleannot,booleanxor,CtTell((x==0)||(y==0));CtIfThen(x<100,x=x+1);Search12/31/202253ILOGSOLVERCTGOALn:howtoexecuteCTGOAL1(CtInstantiate,CtIntVar*x){CtInta=x->chooseValue();CtOr(Constraint(x==a),CtAnd(Constraint(x!=a),CtInstantiate(x)));}12/31/202254ILOGSchedule1.0ScheduleCtScheduleclassGlobalobject:timeoriginal---tineMintimehorizon---timeMax12/31/202255ILOGSchedule1.0ResourcesCtResourceCtDiscreteResourceCtUnaryResourceCtDiscreteEnergyCtStateResource12/31/202256ILOGSchedule1.0ActivitiesCtActivityclassCtIntervalActivityAnactivityisdefinedbyitsstarttime,endtimeanddurationActivitiesrequire,provide,consumeandproduceresources12/31/202257SchedulingProblemPricespaidastasksbegin$1000perdayAvailability:Day0:$20000,Day15:+$900012/31/202258Constraints//Tocreateaschedulewithorigin0andgivenhorizon.CtSchedule*schedule=newCtSchedule(0,horizon);//Tocreateanactivitywiththegivenduration.CtIntervalActivity*act=newCtIntervalActivity(schedule,duration);//Topostaprecedenceconstraintbetweenact1andact2.act2->startsAfterEnd(act1,0);12/31/202259Constraints//Tocreateatotalbudgetoflimitedcapacity(here29000).CtDiscreteResource*res=newCtDiscreteResource(schedule,CtRequiredResource,capacity);//Tostatethatonlycap(here20