約束推理課件

1、約束推理史忠植中國科學院計算技術研究所高級人工智能第三章2022/8/1史忠植 約束推理2第三章 約束推理3.1 概述3.2 回溯法 3.3 約束傳播 3.4 回跳法 3.5 約束推理系統(tǒng)COPS 3.6 ILOG SOLVER3.7 約束邏輯程序設計在八皇后問題中，處理過程不是根據(jù)某種確定的計算法則，而是利用試探和回溯的探索技術求解。為了求得合法布局，在計算機中要存儲布局的當前狀態(tài)。從最初的布局狀態(tài)開始，一步步地進行試探， 每試探一步形成一個新的狀態(tài)， 整個試探過程形成了一棵隱含的狀態(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概 述一個約束滿足問題(Constraint Satisfaction Problem, 簡稱CSP) 包含一組變量與一組變量間的約束。 變量表示領域參數(shù)，每個變量都有一個固定的值域。一個變量的值域可能是有限的，例如一個布爾變量的值域包含兩個值；也可能是

3、離散無限的，如整數(shù)域；也可能是連續(xù)的，如實數(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概 述 約束可用于描述領域對象的性質、相互關系、任務要求、目標等。約束 滿足問題 的目標就是找到所有變量的一個（或多個）賦值，使所有約束都得到滿足。 一元謂詞。 序關系語言，只包含偏序關系或實變量上的大小關系。 形如“x - y c” 的方程。 單位系數(shù)的線性方程與不等式，即所有的系數(shù)為 -1,0,1。 任意系數(shù)的線性方程與不等式。 約束的布爾組合。 代數(shù)與三角方程。2022/8/1史忠植 約束推理8概 述約束表示易于理

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

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

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

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

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

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

11、當被解決問題的規(guī)模(以某種單位計算)由1增至n時，解該問題的算法所需占用的空間也以某種單位由f(1) 增至f(n)，這時我們稱該算法的空間代價是f(n)。 算法的時間代價(或稱時間復雜性)：當問題規(guī)模以某種單位由1增至n時，對應算法所耗費的時間也以某種單位由g(1)增至g(n)，這時我們稱算法的時間代價是g(n)。 算法分析2022/8/1史忠植 約束推理19窮盡搜索方法窮盡搜索方法 即產生所有可能的樹，然后根據(jù)評價標準選擇一棵最優(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貪心法貪心法把構造可行解的工作分階段來完成。在各個階段，選擇那些在某些意義下是局部最優(yōu)的方案，期望各階段的局部最優(yōu)的選擇帶來整體最優(yōu)。例：Dijkstra的最短路徑算法、Kruskal的求最小生成樹算法、信號燈問題2022/8/1史忠植 約束推理22回溯算法有些問題需要徹底的搜索才能解決問題，然而，徹底的搜索要以大量的運算時間為代價，對于這種情

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回溯算法 盡管回溯法好于生成測試法，但對于非平凡問題仍然是低效的。其原因在于搜索空間中不同路徑的搜索重復相同的失敗子路徑。一些研究者認為，造成這種反復的原因是所謂的局部不一致性。最簡單的情形是所謂的結點不一致性。對一個變量vi的一個一元約束。存在域中一個值vi不滿足該約束。這樣，每當vi取到 a 時就會出現(xiàn)不一致性。 另一種重復的情形 是所

20、謂的弧不一致性。2022/8/1史忠植 約束推理37 約束傳播CONSTRAINT PROPAGATION弧一致性Arc consistency 2022/8/1史忠植 約束推理38弧一致性 Arc consistency 如果對vi 的當前域中的所有值x，存在vj的當前域中的某值y使得 vi=x和vj=y是vi與vj之間的約束所允許的，則弧(vi, vj)是弧一致的。 弧一致性的概念是有向的。即(vi, vj)是弧一致的并不自動地意味著(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時間復雜性: 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