【正文】 兩者的優(yōu)點，力圖實現(xiàn)一個具有較強表達能力和較高求解效率的 約束滿足系統(tǒng)。 2022/5/30 史忠植 高級人工智能 21 面向對象約束語言 COPS COPS系統(tǒng)利用面向對象技術，將說明性約束表達與類型層次 結合起來。 CHIP 主要應用于兩個領域 : 運籌學與硬件設計。它通過提供幾種新的計算域而增強邏輯程序設 計的能力；有限域、布爾項及有理項，對于每個計算域，都提供 有效的約束求解技術，即有限域上的一致性技術，布爾域的布爾 合一技術及有理數(shù)域上的單純型法。 同時，約束傳播方法比較單一，既缺乏實域上的區(qū)間傳播機制， 也缺乏有限域上的 域傳播機制。 2022/5/30 史忠植 高級人工智能 19 CONSTRAINTS約束語言 CONSTRAINTS 的一個優(yōu)點是在類型層次中表示約束，用約束 來表示物理對象的功能與結構。系統(tǒng)采用表達式推理與值推理。也有一些取離散值的變量。 這些約束一般是線性方程與不等式 , 也包括條件表達式。 作為一個約束表示語言， 它使用了符號處理技術來求解數(shù)學方程。 ? 局部修正法。 ? 智能回溯與真值維護。 ? 約束語言 2022/5/30 史忠植 高級人工智能 16 約束搜索 ? 回溯法。 2022/5/30 史忠植 高級人工智能 15 約束推理 ? 約束搜索 約束搜索主要研究有限域上的約束滿足。 ? 易于與領域相關的問題求解模型相銜接。 ? 適合于遞增型系統(tǒng)。 ? 易于并行實現(xiàn)。 ? 約束表示允許變量的域包含任意多個值，而不像命題 只取真假二值。 2022/5/30 史忠植 高級人工智能 14 概述 約束表示易于理解、編碼及有效實現(xiàn)，它具有以下優(yōu)點 : ? 約束表示允許以說明性的方式來表達領域知識，表達 能力較強，應用程序只需指定問題的目標條件及數(shù)據(jù)間 的相互關系。 ?約束的布爾組合。 ?單位系數(shù)的線性方程與不等式，即所有的系數(shù)為 1,0,1。 ?序關系語言，只包含偏序關系或實變量上的大小關系。約束 滿足問題 的目標就是找到所有 變量的一個（或多個）賦值，使所有約束都得到滿足。 一個變量的值域可能是有限的，例如一個布爾變量的值 域包含兩個值；也可能是離散無限的，如整數(shù)域；也可 能是連續(xù)的，如實數(shù)域。 2022/5/30 史忠植 高級人工智能 6 線性規(guī)劃問題 ? 例 1(廣告方式的選擇 )中華家電公司推銷一種新型洗衣機 ,有關數(shù)據(jù)見下表 .銷售部第一月的廣告預算為 20220元 ,要求至少有8電視商業(yè)節(jié)目 ,15家報紙廣告 /電視廣告費不得超過 12022元 ,電臺廣播至少隔日有一次 .現(xiàn)問該公司銷售部應當采用怎樣的廣告宣傳計劃 ,才能取得最好的效果 ? 2022/5/30 史忠植 高級人工智能 7 表 1 廣告方式 廣告費用 (元 /次 ) 可用最高次數(shù) /月 期望的宣傳效果 /單位 電視臺 a(白天 ,1 分鐘 ) 500 16 50 電視臺 b(晚上 ,30鈔 ) 1000 10 80 每日晨報 /(半版 ) 100 24 30 星期日報 /(半版 ) 300 4 40 廣播電臺 /(1分鐘 ) 80 25 15 2022/5/30 史忠植 高級人工智能 8 解 : 設 54321, xxxxx分別是第一個月內(nèi)電視臺 a, 電視臺b, 每日晨報 , 星期日報 , 廣播電臺進行廣告宣傳的次數(shù) , 則其數(shù)學模型為 : m a x 543211540308050 xxxxx ???? s . t . .0,2515,4,24,10,16,120221000500,15,8,20220803001001000500543215432121432154321??????????????????xxxxxxxxxxxxxxxxxxxxx 2022/5/30 史忠植 高級人工智能 9 線性規(guī)劃問題 ( LP ) 的一般形式為 : m i n (m a x)???2211xcxcz? nnxc? .??212111xaxa? 11),( bxann???? ??222121xaxa? 22),( bxann???? ?? ??2211xaxamm ? mnmnbxa ),( ???? ,2,1,0 ?? jxj?? n 2022/5/30 史忠植 高級人工智能 10 線性規(guī)劃問題的標準形式為 : m i n XCzT? s .t . 0??XbAX( 假定 b 為非負 ) 注 : 任何形式的線性規(guī)劃問題均可化為標準型 2022/5/30 史忠植 高級人工智能 11 求解 單純形法 ? 將所給問題化為標準形 ? 找出一個初始可行基 ,建立初始單純形表 ? 檢查所有檢驗數(shù) (若全為非負 ,則已得到最優(yōu)解 ,計算停止 .否則繼續(xù)下一步 ) ? 考察是否無解 (若是 ,計算停止 ,否則繼續(xù)下一步 ) ? 確定入基變量 ,出基變量 ? 對初始單純形表進行單純形變換 2022/5/30 史忠植 高級人工智能 12 概述 一個約束滿足問題 (Constraint Satisfaction Problem, 簡稱 CSP) 包含一組變量與一組變量間的約束。這是一個尋求“最優(yōu)化”的題目，目標 是節(jié)省總的排隊時間，達到最優(yōu)。2022/5/30 史忠植 高級人工智能 1 高級人工智能 第三章 約束推理 史忠植 中國科學院計算技術所 2022/5/30 史忠植 高級人工智能 2 第三章 約束推理 概述 回溯法 約束傳播 回跳法 約束推理系統(tǒng) COPS ILOG SOLVER 2022/5/30 史忠植 高級人工智能 3 概述 最優(yōu)化問題 經(jīng)濟學所推崇的帕累托最優(yōu) : 幾個人拎著水桶在一個水龍頭前面排隊打水，水 桶有大有小。他們怎樣排隊，才能使得總的排隊 時間最短。 2022/5/30 史忠植 高級人工智能 4 概述 優(yōu)化問題 ? 運籌學 ? 遺傳算法 ? 神經(jīng)網(wǎng)絡 ? 約束推理 2022/5/30 史忠植 高級人工智能 5 運籌學的工作步驟 ?1）提出和形成問題， ?2）建立模型， ?3）求解， ?4）解的檢驗， ?5）解的控制， ?6）解的實施。 ?變量表示領域參數(shù)，每個變量都有一個固定的值域。 {x1,x2,…xn}, {D1,D2,…Dn}, . {4,5,6,7} red, green,blue} 2022/5/30 史忠植 高級人工智能 13 概述 ?約束可用于描述領域對象的性質(zhì)、相互關系、任務 要求、目標等。 ?一元謂詞。 ?形如 “ x y c” 的方程。 ?任意系數(shù)的線性方程與不等式。 ?代數(shù)與三角方程。因而具有邏輯表示的類似性質(zhì)。所以它保存