【正文】 AINTS是一個(gè)面向電路描述的約束表示語(yǔ)言。約束變量 一般是表示物理量的實(shí)變量。并實(shí)現(xiàn) 相關(guān)制導(dǎo)的回溯。 2022/5/30 史忠植 高級(jí)人工智能 20 約束邏輯程序設(shè)計(jì)語(yǔ)言 CHIP CHIP(Constraint handling in Prolog) 就是這樣較有影響 一個(gè)約束邏輯程序設(shè)計(jì)語(yǔ)言，其目的是簡(jiǎn)便、靈活而有效地解決 一大類組合問題。 CHIP 缺乏類型機(jī)制，而這種機(jī)制對(duì)于表達(dá)領(lǐng)域概念是極其重 要的。 2022/5/30 史忠植 高級(jí)人工智能 22 面向?qū)ο蠹s束語(yǔ)言 COPS COPS的設(shè)計(jì)考慮了軟件工程的應(yīng)用要求，盡量將一個(gè)不確定問 題確定化：它允許條件語(yǔ)句與循環(huán)語(yǔ)句，而不是單 純以遞歸的形式來(lái)實(shí)現(xiàn)迭代計(jì)算； 通過(guò)類方法的重栽實(shí)現(xiàn)同一 約束的不同實(shí)現(xiàn)，提高了程序的執(zhí)行效率。 常用的算法大致有如下一些： ?貪心法 ?分治法：如二分法檢索 ?回溯法 ?動(dòng)態(tài)規(guī)劃法 ?局部搜索法 ?分支限界法 2022/5/30 史忠植 高級(jí)人工智能 24 算法分析 評(píng)價(jià)一個(gè)程序優(yōu)劣的重要依據(jù)是看這個(gè)程序的執(zhí)行需要占用多少機(jī)器資源。 2022/5/30 史忠植 高級(jí)人工智能 25 窮盡搜索方法 窮盡搜索方法 即產(chǎn)生所有可能的樹，然后根據(jù)評(píng)價(jià)標(biāo)準(zhǔn)選擇一棵最優(yōu)的樹。 ? 八皇后問題 ? 迷宮問題 ? 深度優(yōu)先周游樹或圖 2022/5/30 史忠植 高級(jí)人工智能 29 回溯算法 BacktrackingTop(P) 1 f := the null assignment 2 return Backtracking(f,P) 2022/5/30 史忠植 高級(jí)人工智能 30 回溯算法 Backtracking(f,P) 1 if f is a total assignment of the variables in P 2 answer := f 3 else 4 v := some variable in P that is not yet assigned a value by f 5 answer := Unsat 6 for each value while answer = Umsat 7 f(v) := x 8 if f satisfies the constraints in P 9 answer := Backtracking(f,P) 10 return answer 2022/5/30 史忠植 高級(jí)人工智能 31 回溯算法 盡管回溯法好于生成測(cè)試法 ， 但對(duì)于非平凡問題仍然是低效的 。 對(duì)一個(gè)變量 vi的一個(gè)一元約束 。 2022/5/30 史忠植 高級(jí)人工智能 32 約束傳播 CONSTRAINT PROPAGATION ( r e d , g r e e n )( r e d ,b l u e )( r e d , g r e e n ,b l u e ) 弧一致性 Arc consistency 2022/5/30 史忠植 高級(jí)人工智能 33 弧一致性 Arc consistency 如果對(duì) vi 的當(dāng)前域中的所有值 x，存在 vj的當(dāng)前域中的某值 y使得 vi=x和 vj=y是 vi與 vj之間的約束所允許的，則弧 (vi, vj)是弧一致的。 2 for each x ? Di do 3 if there is no such yj ? Dj 4 such that(x,yj) is consistent, 5 then 6 delete x from Di。 2 repeat 3 CHANGE ? false。 8 end AC1 ? ? ? ?? ?V V G i ji j, ,? ? a r c s 2022/5/30 史忠植 高級(jí)人工智能 38 AC3 1 Q ? 。 7 endwhile。 CASE boolean expression_1: constraint_1。 ... // rule definition rule_name。 6 Allocate memories for global variables. 2022/5/30 史忠植 高級(jí)人工智能 49 COPS 7 Interprte the program with the internal structures. 8 Constraint works are built up for Unsolved 9 constraints and variables. 10 while some constraints in the constraint works are triggered, 11 inteprete the triggered constraints. 12 } 2022/5/30 史忠植 高級(jí)人工智能 50 COPS Interpreter: 1 { 2 switch (constraint type) 3 case Constant: 4 return Constant: 5 case global variable: 6 interprete global variable: 7 case local variable or argument: 8 interprete local variable or argument: 9 case objectattribute pair。 Search 2022/5/30 史忠植 高級(jí)人工智能 54 ILOG SOLVER CTGOALn: how to execute CTGOAL1(CtInstantiate, CtIntVar* x){ CtInt a = xchooseValue()。 //To post a precedence constraint between act1 and act2. act2startsAfterEnd(act1,0)。 2022/5/30 史忠植 高級(jí)人工智能 61 Algorithm Program CtBoolean IsUnScheduled(CtActivity* act){ // Return true if act does not have a fixed start time. if (actgetStartVariable()isBound()) return CtFalse。 else return CtFalse。 while((newactivity)) if((IsUnScheduled(newActivity)) amp。 } 2022/5/30 史忠植 高級(jí)人工智能 64 Algorithm Program void SolveProblem(CtSchedule* schedule){ // Solve the problem assuming constraints have been posted. CtActivity* act = SelectActivity(schedul