【正文】 } 2022/5/30 史忠植 高級(jí)人工智能 64 Algorithm Program void SolveProblem(CtSchedule* schedule){ // Solve the problem assuming constraints have been posted. CtActivity* act = SelectActivity(schedule)。 else return CtFalse。 //To post a precedence constraint between act1 and act2. act2startsAfterEnd(act1,0)。 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。 CASE boolean expression_1: constraint_1。 8 end AC1 ? ? ? ?? ?V V G i ji j, ,? ? a r c s 2022/5/30 史忠植 高級(jí)人工智能 38 AC3 1 Q ? 。 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。 對(duì)一個(gè)變量 vi的一個(gè)一元約束 。 2022/5/30 史忠植 高級(jí)人工智能 25 窮盡搜索方法 窮盡搜索方法 即產(chǎn)生所有可能的樹(shù)，然后根據(jù)評(píng)價(jià)標(biāo)準(zhǔn)選擇一棵最優(yōu)的樹(shù)。 2022/5/30 史忠植 高級(jí)人工智能 22 面向?qū)ο蠹s束語(yǔ)言 COPS COPS的設(shè)計(jì)考慮了軟件工程的應(yīng)用要求，盡量將一個(gè)不確定問(wèn) 題確定化：它允許條件語(yǔ)句與循環(huán)語(yǔ)句，而不是單 純以遞歸的形式來(lái)實(shí)現(xiàn)迭代計(jì)算； 通過(guò)類方法的重栽實(shí)現(xiàn)同一 約束的不同實(shí)現(xiàn)，提高了程序的執(zhí)行效率。 2022/5/30 史忠植 高級(jí)人工智能 20 約束邏輯程序設(shè)計(jì)語(yǔ)言 CHIP CHIP(Constraint handling in Prolog) 就是這樣較有影響 一個(gè)約束邏輯程序設(shè)計(jì)語(yǔ)言，其目的是簡(jiǎn)便、靈活而有效地解決 一大類組合問(wèn)題。約束變量 一般是表示物理量的實(shí)變量。 ? 約束傳播。因?yàn)榧s束網(wǎng)絡(luò)上的信息傳播可以認(rèn)為是 同時(shí)的。 ?任意系數(shù)的線性方程與不等式。 ?變量表示領(lǐng)域參數(shù)，每個(gè)變量都有一個(gè)固定的值域。這是一個(gè)尋求“最優(yōu)化”的題目，目標(biāo) 是節(jié)省總的排隊(duì)時(shí)間，達(dá)到最優(yōu)。 ?序關(guān)系語(yǔ)言，只包含偏序關(guān)系或?qū)嵶兞可系拇笮￡P(guān)系。 ? 約束表示允許變量的域包含任意多個(gè)值，而不像命題 只取真假二值。 2022/5/30 史忠植 高級(jí)人工智能 15 約束推理 ? 約束搜索 約束搜索主要研究有限域上的約束滿足。 作為一個(gè)約束表示語(yǔ)言， 它使用了符號(hào)處理技術(shù)來(lái)求解數(shù)學(xué)方程。 2022/5/30 史忠植 高級(jí)人工智能 19 CONSTRAINTS約束語(yǔ)言 CONSTRAINTS 的一個(gè)優(yōu)點(diǎn)是在類型層次中表示約束，用約束 來(lái)表示物理對(duì)象的功能與結(jié)構(gòu)。 2022/5/30 史忠植 高級(jí)人工智能 21 面向?qū)ο蠹s束語(yǔ)言 COPS COPS系統(tǒng)利用面向?qū)ο蠹夹g(shù)，將說(shuō)明性約束表達(dá)與類型層次 結(jié)合起來(lái)。人們最關(guān)心的就是程序所用算法運(yùn)行時(shí)所要花費(fèi)的 時(shí)間代價(jià) 和程序中使用的數(shù)據(jù)結(jié)構(gòu)占有的 空間代價(jià) 。 其原因在于搜索空間中不同路徑的搜索重復(fù)相同的失敗子路徑 。 弧一致性的概念是有向的。 4 for each (Vi, Vj) ? Q do 5 CHANGE ? REVISE(Vi, Vj) ? CHANGE。 8 end AC3 ? ? ? ?? ?V V G i ji j, ,? ? a r c s 2022/5/30 史忠植 高級(jí)人工智能 39 Backjumping BackjumpingTop(P) 1 f := the null assignment 2 answer, conflictset := Backjumping(f,P) 3 return answer 2022/5/30 史忠植 高級(jí)人工智能 40 Backjumping Backjumping(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 conflictset := ? 7 for each value 8 f(v) := x 9 if f satisfies the constraints in P 10 answer, newconflicts := Backjumping(f,P) 2022/5/30 史忠植 高級(jí)人工智能 41 Backjumping 11 else 12 newconflicts := the set of variables in a violated constraint 13 if answer ? Unsat 14 return answer, ? 15 else if v ? newconflicts 16 return Unsat, newconflicts 17 else 18 conflictset := conflictset ? (newconflicts