約束推理課件

1、約束推理史忠植中國科學(xué)院計(jì)算技術(shù)研究所高級人工智能第三章2022/8/1史忠植 約束推理2第三章 約束推理3.1 概述3.2 回溯法 3.3 約束傳播 3.4 回跳法 3.5 約束推理系統(tǒng)COPS 3.6 ILOG SOLVER3.7 約束邏輯程序設(shè)計(jì)在八皇后問題中，處理過程不是根據(jù)某種確定的計(jì)算法則，而是利用試探和回溯的探索技術(shù)求解。為了求得合法布局，在計(jì)算機(jī)中要存儲(chǔ)布局的當(dāng)前狀態(tài)。從最初的布局狀態(tài)開始，一步步地進(jìn)行試探， 每試探一步形成一個(gè)新的狀態(tài)， 整個(gè)試探過程形成了一棵隱含的狀態(tài)樹。八皇后問題7654321001234567采用DFS/BFS搜索策略The DFS/BFS tree w

2、ill enumerate up to 648 combinations (assume limit depth to 8).648 = 248 = 2.8 x 1014Note redundancy: Q1 in (1,3), Q2 in (2,7) vs. Q1 in (2,7), Q2 in (1,3) 2022/8/1史忠植 約束推理5概 述一個(gè)約束滿足問題(Constraint Satisfaction Problem, 簡稱CSP) 包含一組變量與一組變量間的約束。 變量表示領(lǐng)域參數(shù)，每個(gè)變量都有一個(gè)固定的值域。一個(gè)變量的值域可能是有限的，例如一個(gè)布爾變量的值域包含兩個(gè)值；也可能是

3、離散無限的，如整數(shù)域；也可能是連續(xù)的，如實(shí)數(shù)域。 x1,x2,xn, D1,D2,Dn, . 4,5,6,7 red, green,blue 約束滿足問題CSPGiven: (1) set of variables, (2) domains of the variables (3) constraints that the variables have to satisfyFind: An assignment of values to the variables, so that these values satisfy all the given constraints. In optim

4、isation problems, also specify optimisation criterion 2022/8/16史忠植 約束推理2022/8/1史忠植 約束推理7概 述 約束可用于描述領(lǐng)域?qū)ο蟮男再|(zhì)、相互關(guān)系、任務(wù)要求、目標(biāo)等。約束 滿足問題 的目標(biāo)就是找到所有變量的一個(gè)（或多個(gè)）賦值，使所有約束都得到滿足。 一元謂詞。 序關(guān)系語言，只包含偏序關(guān)系或?qū)嵶兞可系拇笮￡P(guān)系。 形如“x - y c” 的方程。 單位系數(shù)的線性方程與不等式，即所有的系數(shù)為 -1,0,1。 任意系數(shù)的線性方程與不等式。 約束的布爾組合。 代數(shù)與三角方程。2022/8/1史忠植 約束推理8概 述約束表示易于理

5、解、編碼及有效實(shí)現(xiàn)，它具有以下優(yōu)點(diǎn): 約束表示允許以說明性的方式來表達(dá)領(lǐng)域知識(shí)，表達(dá)能力較強(qiáng)，應(yīng)用程序只需指定問題的目標(biāo)條件及數(shù)據(jù)間的相互關(guān)系。因而具有邏輯表示的類似性質(zhì)。 約束表示允許變量的域包含任意多個(gè)值，而不像命題 只取真假二值。所以它保存了問題的一些結(jié)構(gòu)信息，如變量域的大小、變量間的相關(guān)性等，從而為問題求解提供啟發(fā)式信息。 易于并行實(shí)現(xiàn)。因?yàn)榧s束網(wǎng)絡(luò)上的信息傳播可以認(rèn)為是同時(shí)的。 適合于遞增型系統(tǒng)。約束可以遞增式地加入到約束網(wǎng)絡(luò)。 易于與領(lǐng)域相關(guān)的問題求解模型相銜接。各種數(shù)學(xué)規(guī)劃技術(shù)，方程求解技術(shù)等, 都可以自然地嵌入約束系統(tǒng)。2022/8/1史忠植 約束推理9約束推理 約束搜索約束搜

6、索主要研究有限域上的約束滿足。對有限域而言，約束滿足問題一般情況下是 一個(gè) NP 問題。 約束語言2022/8/1史忠植 約束推理10約束搜索 回溯法。 約束傳播。 智能回溯與真值維護(hù)。 可變次序例示。 局部修正法。2022/8/1史忠植 約束推理11約束語言CONSTRAINTSCHIPCOPSILOG2022/8/1史忠植 約束推理12CONSTRAINTS約束語言 CONSTRAINTS是一個(gè)面向電路描述的約束表示語言。作為一個(gè)約束表示語言，它使用了符號(hào)處理技術(shù)來求解數(shù)學(xué)方程。在CONSTRAITS中，物理部件的功能及器件的結(jié)構(gòu)都用約束表示。這些約束一般是線性方程與不等式, 也包括條件表

7、達(dá)式。約束變量一般是表示物理量的實(shí)變量。也有一些取離散值的變量。如開關(guān)的狀態(tài)、三極管的工作狀態(tài)等。系統(tǒng)采用表達(dá)式推理與值推理。并實(shí)現(xiàn)相關(guān)制導(dǎo)的回溯。 2022/8/1史忠植 約束推理13CONSTRAINTS約束語言 CONSTRAINTS 的一個(gè)優(yōu)點(diǎn)是在類型層次中表示約束，用約束來表示物理對象的功能與結(jié)構(gòu)。其缺點(diǎn)是該語言缺乏類似于面向?qū)ο笳Z言中的方法那樣的成分，不能定義特定于某個(gè)類的概念。同時(shí)，約束傳播方法比較單一，既缺乏實(shí)域上的區(qū)間傳播機(jī)制，也缺乏有限域上的 域傳播機(jī)制。 2022/8/1史忠植 約束推理14約束邏輯程序設(shè)計(jì)語言CHIP CHIP(Constraint handling i

8、n Prolog) 就是這樣較有影響一個(gè)約束邏輯程序設(shè)計(jì)語言，其目的是簡便、靈活而有效地解決一大類組合問題。它通過提供幾種新的計(jì)算域而增強(qiáng)邏輯程序設(shè)計(jì)的能力；有限域、布爾項(xiàng)及有理項(xiàng)，對于每個(gè)計(jì)算域，都提供有效的約束求解技術(shù)，即有限域上的一致性技術(shù)，布爾域的布爾合一技術(shù)及有理數(shù)域上的單純型法。除此以外，CHIP還包含一個(gè)一般的延遲計(jì)算機(jī)制。 CHIP 主要應(yīng)用于兩個(gè)領(lǐng)域: 運(yùn)籌學(xué)與硬件設(shè)計(jì)。 CHIP 缺乏類型機(jī)制，而這種機(jī)制對于表達(dá)領(lǐng)域概念是極其重要的。2022/8/1史忠植 約束推理15面向?qū)ο蠹s束語言COPS COPS系統(tǒng)利用面向?qū)ο蠹夹g(shù)，將說明性約束表達(dá)與類型層次結(jié)合起來。在形式上吸收了

9、常規(guī)語言，主要是面向?qū)ο蟮某绦蛟O(shè)計(jì)語言的基本形式。內(nèi)部求解時(shí)采用約束推理機(jī)制，使說明性約束表達(dá)式與類型層次相結(jié)合，實(shí)現(xiàn)知識(shí)的結(jié)構(gòu)化封裝，充分發(fā)揮兩者的優(yōu)點(diǎn)，力圖實(shí)現(xiàn)一個(gè)具有較強(qiáng)表達(dá)能力和較高求解效率的約束滿足系統(tǒng)。2022/8/1史忠植 約束推理16面向?qū)ο蠹s束語言COPSCOPS的設(shè)計(jì)考慮了軟件工程的應(yīng)用要求，盡量將一個(gè)不確定問題確定化：它允許條件語句與循環(huán)語句，而不是單純以遞歸的形式來實(shí)現(xiàn)迭代計(jì)算； 通過類方法的重栽實(shí)現(xiàn)同一約束的不同實(shí)現(xiàn)，提高了程序的執(zhí)行效率。COPS系統(tǒng)同時(shí)是一個(gè)漸增式的開放系統(tǒng)，用戶能通過類型層次定義，實(shí)現(xiàn)新的數(shù)據(jù)類型和新的約束關(guān)系。約束語言COPS具有許多人工智能程

10、序設(shè)計(jì)語言的特點(diǎn)，如約束傳播、面向目標(biāo)和數(shù)據(jù)驅(qū)動(dòng)的問題求解、有限步的回溯、對象分層中的繼承等。 2022/8/1史忠植 約束推理17 在實(shí)際應(yīng)用中，算法的表現(xiàn)形式千變?nèi)f化，但是算法的情況也和數(shù)據(jù)結(jié)構(gòu)類似，許多算法的設(shè)計(jì)思想具有相似之處，我們可以對它們分類進(jìn)行學(xué)習(xí)和研究。 常用的算法大致有如下一些：貪心法分治法：如二分法檢索回溯法動(dòng)態(tài)規(guī)劃法局部搜索法分支限界法常用的算法2022/8/1史忠植 約束推理18 評價(jià)一個(gè)程序優(yōu)劣的重要依據(jù)是看這個(gè)程序的執(zhí)行需要占用多少機(jī)器資源。人們最關(guān)心的就是程序所用算法運(yùn)行時(shí)所要花費(fèi)的時(shí)間代價(jià)和程序中使用的數(shù)據(jù)結(jié)構(gòu)占有的空間代價(jià)。 算法的空間代價(jià)(或稱空間復(fù)雜性)：

11、當(dāng)被解決問題的規(guī)模(以某種單位計(jì)算)由1增至n時(shí)，解該問題的算法所需占用的空間也以某種單位由f(1) 增至f(n)，這時(shí)我們稱該算法的空間代價(jià)是f(n)。 算法的時(shí)間代價(jià)(或稱時(shí)間復(fù)雜性)：當(dāng)問題規(guī)模以某種單位由1增至n時(shí)，對應(yīng)算法所耗費(fèi)的時(shí)間也以某種單位由g(1)增至g(n)，這時(shí)我們稱算法的時(shí)間代價(jià)是g(n)。 算法分析2022/8/1史忠植 約束推理19窮盡搜索方法窮盡搜索方法 即產(chǎn)生所有可能的樹，然后根據(jù)評價(jià)標(biāo)準(zhǔn)選擇一棵最優(yōu)的樹。 Exhaustive-Search-Top(P) where P is a CSP of the form(V,D,C)1. f:= the null as

12、signment2. return Exhaustive-Search(f,P)2022/8/1史忠植 約束推理20窮盡搜索方法 Exhaustive-Search(f,P)1. if f is a total assignment of the variables in P2. if f satisfies the constraints in P3. answer := f4. else 5. answer := Unsat6. else 7. v := some variable in P that is not yet assigned a value by f8. answer :=

13、 Unsat9. for each value while answer = Unsat10. f(v) := 11. answer := Exhaustive-Search(f,P)12. return answer2022/8/1史忠植 約束推理21貪心法貪心法把構(gòu)造可行解的工作分階段來完成。在各個(gè)階段，選擇那些在某些意義下是局部最優(yōu)的方案，期望各階段的局部最優(yōu)的選擇帶來整體最優(yōu)。例：Dijkstra的最短路徑算法、Kruskal的求最小生成樹算法、信號(hào)燈問題2022/8/1史忠植 約束推理22回溯算法有些問題需要徹底的搜索才能解決問題，然而，徹底的搜索要以大量的運(yùn)算時(shí)間為代價(jià)，對于這種情

14、況可以通過回溯法來去掉一些分支，從而大大減少搜索的次數(shù)。八皇后問題迷宮問題深度優(yōu)先周游樹或圖約束推理 ppt 四皇后問題中隱含的狀態(tài)樹 四皇后問題2022/8/1史忠植 約束推理244-Queens Puzzle2022/8/1史忠植 約束推理254-Queens Tree回溯算法Backtrack Searchempty assignment1st variable2nd variable3rd variableAssignment = 回溯算法Backtrack Searchempty assignment1st variable2nd variable3rd variableAssign

15、ment = (var1=v11)回溯算法Backtrack Searchempty assignment1st variable2nd variable3rd variableAssignment = (var1=v11),(var2=v21)回溯算法Backtrack Searchempty assignment1st variable2nd variable3rd variableAssignment = (var1=v11),(var2=v21),(var3=v31)回溯算法Backtrack Searchempty assignment1st variable2nd variable

16、3rd variableAssignment = (var1=v11),(var2=v21),(var3=v32)回溯算法Backtrack Searchempty assignment1st variable2nd variable3rd variableAssignment = (var1=v11),(var2=v22)回溯算法Backtrack Searchempty assignment1st variable2nd variable3rd variableAssignment = (var1=v11),(var2=v22),(var3=v31)2022/8/1史忠植 約束推理33回溯

17、算法 Backtracking-Top(P)1 f := the null assignment2 return Backtracking(f,P)2022/8/1史忠植 約束推理34回溯算法 Backtracking(f,P)1 if f is a total assignment of the variables in P2 answer := f3 else 4 v := some variable in P that is not yet assigned a value by f5 answer := Unsat6 for each value while answer = Umsa

18、t7 f(v) := x8 if f satisfies the constraints in P9 answer := Backtracking(f,P)10 return answer2022/8/1史忠植 約束推理35Backtracking AlgorithmBased on depth-first recursive searchApproachTests whether solution has been foundIf found solution, return itElse for each choice that can be madeMake that choiceRec

19、urIf recursion returns a solution, return itIf no choices remain, return failureSome times called “search tree”2022/8/1史忠植 約束推理36回溯算法 盡管回溯法好于生成測試法，但對于非平凡問題仍然是低效的。其原因在于搜索空間中不同路徑的搜索重復(fù)相同的失敗子路徑。一些研究者認(rèn)為，造成這種反復(fù)的原因是所謂的局部不一致性。最簡單的情形是所謂的結(jié)點(diǎn)不一致性。對一個(gè)變量vi的一個(gè)一元約束。存在域中一個(gè)值vi不滿足該約束。這樣，每當(dāng)vi取到 a 時(shí)就會(huì)出現(xiàn)不一致性。 另一種重復(fù)的情形 是所

20、謂的弧不一致性。2022/8/1史忠植 約束推理37 約束傳播CONSTRAINT PROPAGATION弧一致性Arc consistency 2022/8/1史忠植 約束推理38弧一致性 Arc consistency 如果對vi 的當(dāng)前域中的所有值x，存在vj的當(dāng)前域中的某值y使得 vi=x和vj=y是vi與vj之間的約束所允許的，則弧(vi, vj)是弧一致的。 弧一致性的概念是有向的。即(vi, vj)是弧一致的并不自動(dòng)地意味著(vj, vi)是一致的。2022/8/1史忠植 約束推理39 CONSTRAINT PROPAGATIONAll of the Mackworth algo

21、rithms make use of a Revise procedure. Let Dv be the current domain of v, Let Dw be the current domain of w, Let P be the constraint predicate that holds between v and w, then Revise updates Dv as follows:2022/8/1史忠植 約束推理40CONSTRAINT PROPAGATIONMackworth 1977 AC-1 AC-2 AC-32022/8/1史忠植 約束推理41約束傳播修改算法

22、REVISE(Vi,Vj)1 DELETE false;2 for each x Di do 3 if there is no such yj Dj4such that(x,yj) is consistent,5 then 6 delete x from Di;7 DELETE true;8 endif 9 endfor 10 return DELETE; 11 end REVISE2022/8/1史忠植 約束推理42弧一致性算法AC-11 Q ;2 repeat 3 CHANGE false;4 for each (Vi, Vj) Q do5 CHANGE REVISE(Vi, Vj) CH

23、ANGE;6 endfor;7 until not(CHANGE);8 end AC-12022/8/1史忠植 約束推理43弧一致性算法AC-31 Q ;2 While Q not empty 3 Select and delete any arc(Vk,Vm) from Q;4 If (REVISE(Vk,Vm) Then Q (Vi,Vk) such that (Vi,Vk)arcs(G), ik, im;6 endfor;7 endwhile;8 end AC-3弧一致性算法AC-3If Xis domain is filtered all the constraints associa

24、ted with it andother variables are added to the queue Binary constraintXi, Xj弧一致性算法AC-3時(shí)間復(fù)雜性: n2= number of constraints (edges; n is the # of variables)d = number of values per variableREMOVE-ARC-INCONSISTENCY takes O(d2) timeEach variable is inserted in Queue up to d times, since at most d values c

25、an be deletedAC3 takes O(n2d3) time to run2022/8/1史忠植 約束推理46BackjumpingBackjumping-Top(P)1 f := the null assignment2 := Backjumping(f,P)3 return answer2022/8/1史忠植 約束推理47BackjumpingBackjumping(f,P)1 if f is a total assignment of the variables in P2 answer := 3 else 4 v := some variable in P that is n

26、ot yet assigned a value by f5 answer := Unsat6 conflict-set := 7 for each value 8 f(v) := x9 if f satisfies the constraints in P10 := Backjumping(f,P)2022/8/1史忠植 約束推理48Backjumping11 else12 new-conflicts := the set of variables in a violated constraint13 if answer Unsat14 return 15 else if v new-conf

27、licts16 return 17 else 18 conflict-set := conflict-set (new-conflicts v)19 return 2022/8/1史忠植 約束推理49COPS Constraint : predicate expressionP(t1, ., tn) where P is built in function, such as sum times eq(equal) neq(not equal) ge(great than or equal to) gt(great than) also can be defined by users2022/8

28、/1史忠植 約束推理50COPS Conditional constraint condition1: constraint1; . . conditionn: constraintn where condition1, ., conditionn are boolean expressions. constraint1,. constraintn are constraints or contraints table. 2022/8/1史忠植 約束推理51COPS RULE Rule is used to define new function, method, predicate, or

29、add new constraint into object.RULE class: predicate(varibles) (boolean expression)constraint_1;constraint_n; CASEboolean expression_1: constraint_1; boolean expression_m: constraint_m;2022/8/1史忠植 約束推理52COPS For example: RULE multiple(INTEGER: *x, INTEGER: y, INTEGER: z) (neq(y, 0) equal(x, divide(z

30、, y); z = x * y2022/8/1史忠植 約束推理53COPS CLASS class_name:superclass_name / attributes definition date type: attribute_name; . / rule definition rule_name; . /function definition function_name; . / method definition method_name; . 2022/8/1史忠植 約束推理54COPS Implementation Program written by COPS consists o

31、f classes and rules. COPS constraint programming language is a declarative language, providing classes, methods which are exist in object oriented language. It is similar with C+ . COPS has the features: constraint object oriented logic programming production system 2022/8/1史忠植 約束推理55COPS COPS_Compi

32、ler1 2 Call yacc to parse the program and 3 to generate internal structures.4 Initializatiion5 Create Cops Constant trueNode;6 Allocate memories for global variables. 2022/8/1史忠植 約束推理56COPS7 Interprte the program with the internal structures.8 Constraint networks are built up for Unsolved 9 constrai

33、nts and variables.10 while some constraints in the constraint networks are triggered,11 inteprete the triggered constraints.12 2022/8/1史忠植 約束推理57COPSInterpreter:1 2 switch (constraint type)3 case Constant:4 return Constant:5 case global variable:6 interprete global variable:7 case local variable or

34、argument:8 interprete local variable or argument:9 case object-attribute pair;10 interprete object-attribute pair:11 case function call:2022/8/1史忠植 約束推理58COPS12 interprete function call:13 case method call:14 interprete method call:15 case CASE expression:16 interprete CASE expression:17 .18 default

35、:20 report error21 2022/8/1史忠植 約束推理59ILOG SOLVERCombines object oriented programming with constraint logic programming, containing logic variables, incremental constraint satisfaction and backtracking. variables : C+ object integer variable CtIntVar floating variable CtFloatVar boolean variable CtBo

36、olVarMemory Management new: delete:2022/8/1史忠植 約束推理60ILOG SOLVERConstraints CtTell(x = (y + z); Basic constraints: =, , , , +, -, *, /, subset, superset, union, intersection, member, boolean or, boolean and, boolean not, boolean xor, CtTell(x=0) | (y=0); CtIfThen (x chooseValue(); CtOr(Constraint(x

37、= a), CtAnd(Constraint(x != a), CtInstantiate(x); 2022/8/1史忠植 約束推理62 ILOG Schedule 1.0Schedule CtSchedule class Global object: time original -tineMin time horizon -timeMax 2022/8/1史忠植 約束推理63 ILOG Schedule 1.0Resources CtResource CtDiscreteResource CtUnaryResource CtDiscreteEnergy CtStateResource 202

38、2/8/1史忠植 約束推理64 ILOG Schedule 1.0Activities CtActivity class CtIntervalActivity An activity is defined by its start time, end time and duration Activities require, provide, consume and produce resources2022/8/1史忠植 約束推理65 Scheduling Problem Prices paid as tasks begin $1000 per day Availability: Day 0

39、:$20000, Day 15: +$90002022/8/1史忠植 約束推理66Constraints / To create a schedule with origin 0 and given horizon.CtSchedule* schedule = new CtSchedule(0, horizon);/ To create an activity with the given duration.CtIntervalActivity* act = new CtIntervalActivity(schedule, duration);/To post a precedence con

40、straint between act1 and act2.act2-startsAfterEnd(act1,0);2022/8/1史忠植 約束推理67Constraints/To create a total budget of limited capacity (here 29000).CtDiscreteResource* res = new CtDiscreteResource(schedule, CtRequiredResource, capacity);/ To state that only cap (here 20000) is available prior to a / g

41、iven date (here 15).res-setCapacityMax(0,date,cap);/ To state that an activity act consumes c units of res.act-consumes(res, c);2022/8/1史忠植 約束推理68Algorithm ProgramCtBoolean IsUnScheduled(CtActivity* act) / Return true if act does not have a fixed start time. if (act-getStartVariable()-isBound() retu

42、rn CtFalse; else return CtTrue;2022/8/1史忠植 約束推理69Algorithm ProgramCtBoolean IsMoreUrgent(CtActivity* act1, CtActivity* act2) / Returns true if act1 is more urgent than act2. / Returns true if act2 is unbound (=0) if (act2 = 0) return CtTrue; else if (act1-getStartMax() getStartMax() return CtTrue; e

43、lse return CtFalse;2022/8/1史忠植 約束推理70Algorithm ProgramCtActivity* SelectActivity(CtSchedule* schedule) / Returns the unscheduled activity with the smallest latest / statrt time. Returns 0 if all activities are scheduled. CtActivity* bestActivity = 0; /Creates an iterator to iterate on all activities

44、. CtActivityIterator* iterator(schedule); CtActivity* newActivity; while(iterator.next(newactivity) if(IsUnScheduled(newActivity) & (IsMoreUgent(newActivity, bestActivity) bestactivity = newActivity; return bestActivity;2022/8/1史忠植 約束推理71Algorithm Programvoid SolveProblem(CtSchedule* schedule) / Solve the problem assuming constraints have been posted. CtActivity* act = SelectActivity(schedule); while (act !=0) act-setStartTime(act-getStartMin(); act = SelectActivity(schedule); 2022/8/1史忠植 約束推理72Op