【正文】 {v}) 19 return Unsat, conflictset 2022/5/30 史忠植 高級(jí)人工智能 42 COPS Constraint : predicate expression P(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 users 2022/5/30 史忠植 高級(jí)人工智能 43 COPS Conditional constraint condition1: constraint1。 ... //function definition function_name。 CtOr(Constraint(x == a), CtAnd(Constraint(x != a), CtInstantiate(x)))。 else return CtTrue。amp。 } } 2022/5/30 史忠植 高級(jí)人工智能 65 Optimal Solution to the Scheduling Problem 。 CtActivity* newActivity。 // To state that an activity act consumes c units of res. actconsumes(res, c)。 CtIfThen (x 100, x = x+1)。 } z = x * y 2022/5/30 史忠植 高級(jí)人工智能 46 COPS CLASS [class_name][:superclass_name] { // attributes definition date type: attribute_name。 6 endfor。 11 end REVISE 2022/5/30 史忠植 高級(jí)人工智能 37 AC1 1 Q ? 。 另一種重復(fù)的情形 是所謂的弧不一致性 。 例： Dijkstra的最短路徑算法、 Kruskal的求最小生成樹算法、信號(hào)燈問(wèn)題 2022/5/30 史忠植 高級(jí)人工智能 28 回溯算法 有些問(wèn)題需要徹底的搜索才能解決問(wèn)題，然而，徹底的搜索要以大量的運(yùn)算時(shí)間為代價(jià)，對(duì)于這種情況可以通過(guò)回溯法來(lái)去掉一些分支，從而大大減少搜索的次數(shù)。 2022/5/30 史忠植 高級(jí)人工智能 23 在實(shí)際應(yīng)用中，算法的表現(xiàn)形式千變?nèi)f化，但是算法的情況也和數(shù)據(jù)結(jié)構(gòu)類似，許多算法的設(shè)計(jì)思想具有相似之處，我們可以對(duì)它們分類進(jìn)行學(xué)習(xí)和研究。 CHIP 主要應(yīng)用于兩個(gè)領(lǐng)域 : 運(yùn)籌學(xué)與硬件設(shè)計(jì)。系統(tǒng)采用表達(dá)式推理與值推理。 ? 局部修正法。 ? 易于與領(lǐng)域相關(guān)的問(wèn)題求解模型相銜接。 2022/5/30 史忠植 高級(jí)人工智能 14 概述 約束表示易于理解、編碼及有效實(shí)現(xiàn)，它具有以下優(yōu)點(diǎn) : ? 約束表示允許以說(shuō)明性的方式來(lái)表達(dá)領(lǐng)域知識(shí)，表達(dá) 能力較強(qiáng)，應(yīng)用程序只需指定問(wèn)題的目標(biāo)條件及數(shù)據(jù)間 的相互關(guān)系。約束 滿足問(wèn)題 的目標(biāo)就是找到所有 變量的一個(gè)（或多個(gè)）賦值，使所有約束都得到滿足。2022/5/30 史忠植 高級(jí)人工智能 1 高級(jí)人工智能 第三章 約束推理 史忠植 中國(guó)科學(xué)院計(jì)算技術(shù)所 2022/5/30 史忠植 高級(jí)人工智能 2 第三章 約束推理 概述 回溯法 約束傳播 回跳法 約束推理系統(tǒng) COPS ILOG SOLVER 2022/5/30 史忠植 高級(jí)人工智能 3 概述 最優(yōu)化問(wèn)題 經(jīng)濟(jì)學(xué)所推崇的帕累托最優(yōu) : 幾個(gè)人拎著水桶在一個(gè)水龍頭前面排隊(duì)打水，水 桶有大有小。 {x1,x2,…xn}, {D1,D2,…Dn}, . {4,5,6,7} red, green,blue} 2022/5/30 史忠植 高級(jí)人工智能 13 概述 ?約束可用于描述領(lǐng)域?qū)ο蟮男再|(zhì)、相互關(guān)系、任務(wù) 要求、目標(biāo)等。 ?代數(shù)與三角方程。約束可以遞增式地加入到約束網(wǎng)絡(luò)。 ? 可變次序例示。如開關(guān)的狀 態(tài)、三極管的工作狀態(tài)等。除此以外， CHIP還包含一個(gè) 一般的延遲計(jì)算機(jī)制。約束語(yǔ)言 COPS具有許多人工智能程序設(shè)計(jì)語(yǔ) 言的特點(diǎn)，如約束傳播、面向目標(biāo)和數(shù)據(jù)驅(qū)動(dòng)的問(wèn)題求解、有限 步的回溯、對(duì)象分層中的繼承等。在各個(gè)階段，選擇那些在某些意義下是局部最優(yōu)的方案，期望各階段的局部最優(yōu)的選擇帶來(lái)整體最優(yōu)。 這樣 ， 每當(dāng) vi取到 a 時(shí)就會(huì)出現(xiàn) 不一致性 。 8 endif 9 endfor 10 return DELETE。 4 If (REVISE(Vk,Vm)) 5 Then Q ? {(Vi,Vk) such that (Vi,Vk)?arcs(G), 6 i?k, i?m}。 } 2022/5/30 史忠植 高級(jí)人工智能 45 COPS For example: RULE multiple(INTEGER: *x, INTEGER: y, INTEGER: z) (neq(y, 0)) { equal(x, divide(z, y))。 Basic constraints: =, ?, ?, , , +, , *, /, subset, superset, union, intersection, member, boolean or, boolean and, boolean not, boolean xor, CtTell((x==0) || (y==0))。 // To state that only cap (here 20220) is available prior to a // given date (here 15). ressetCapacityMax(0,date,cap)。 //Creates an iterator to iterate on all activities. CtActivityIterator* iterator(schedule)。 act = SelectActivity(schedule)。 (IsMoreUgent(newActivity, bestActivity))) bestactivity = newActivity。 } 2022/5/30 史