【正文】 要求、目標等。 2022/5/30 史忠植 高級人工智能 4 概述 優(yōu)化問題 ? 運籌學 ? 遺傳算法 ? 神經(jīng)網(wǎng)絡(luò) ? 約束推理 2022/5/30 史忠植 高級人工智能 5 運籌學的工作步驟 ?1）提出和形成問題， ?2）建立模型， ?3）求解， ?4）解的檢驗， ?5）解的控制， ?6）解的實施。2022/5/30 史忠植 高級人工智能 1 高級人工智能 第三章 約束推理 史忠植 中國科學院計算技術(shù)所 2022/5/30 史忠植 高級人工智能 2 第三章 約束推理 概述 回溯法 約束傳播 回跳法 約束推理系統(tǒng) COPS ILOG SOLVER 2022/5/30 史忠植 高級人工智能 3 概述 最優(yōu)化問題 經(jīng)濟學所推崇的帕累托最優(yōu) : 幾個人拎著水桶在一個水龍頭前面排隊打水，水 桶有大有小。 2022/5/30 史忠植 高級人工智能 6 線性規(guī)劃問題 ? 例 1(廣告方式的選擇 )中華家電公司推銷一種新型洗衣機 ,有關(guān)數(shù)據(jù)見下表 .銷售部第一月的廣告預(yù)算為 20220元 ,要求至少有8電視商業(yè)節(jié)目 ,15家報紙廣告 /電視廣告費不得超過 12022元 ,電臺廣播至少隔日有一次 .現(xiàn)問該公司銷售部應(yīng)當采用怎樣的廣告宣傳計劃 ,才能取得最好的效果 ? 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 解 : 設(shè) 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) 包含一組變量與一組變量間的約束。約束 滿足問題 的目標就是找到所有 變量的一個（或多個）賦值，使所有約束都得到滿足。 ?單位系數(shù)的線性方程與不等式，即所有的系數(shù)為 1,0,1。 2022/5/30 史忠植 高級人工智能 14 概述 約束表示易于理解、編碼及有效實現(xiàn)，它具有以下優(yōu)點 : ? 約束表示允許以說明性的方式來表達領(lǐng)域知識，表達 能力較強，應(yīng)用程序只需指定問題的目標條件及數(shù)據(jù)間 的相互關(guān)系。 ? 易于并行實現(xiàn)。 ? 易于與領(lǐng)域相關(guān)的問題求解模型相銜接。 ? 約束語言 2022/5/30 史忠植 高級人工智能 16 約束搜索 ? 回溯法。 ? 局部修正法。 這些約束一般是線性方程與不等式 , 也包括條件表達式。系統(tǒng)采用表達式推理與值推理。 同時，約束傳播方法比較單一，既缺乏實域上的區(qū)間傳播機制， 也缺乏有限域上的 域傳播機制。 CHIP 主要應(yīng)用于兩個領(lǐng)域 : 運籌學與硬件設(shè)計。內(nèi)部求解時采用約束推理機制，使說明性約 束表達式與類型層次相結(jié)合，實現(xiàn)知識的結(jié)構(gòu)化封裝，充分發(fā)揮 兩者的優(yōu)點，力圖實現(xiàn)一個具有較強表達能力和較高求解效率的 約束滿足系統(tǒng)。 2022/5/30 史忠植 高級人工智能 23 在實際應(yīng)用中，算法的表現(xiàn)形式千變?nèi)f化，但是算法的情況也和數(shù)據(jù)結(jié)構(gòu)類似，許多算法的設(shè)計思想具有相似之處，我們可以對它們分類進行學習和研究。 算法的時間代價 (或稱 時間復(fù)雜性 )：當問題規(guī)模以某種單位由 1增至 n時，對應(yīng)算法所耗費的時間也以某種單位由 g(1)增至 g(n)，這時我們稱算法的時間代價是 g(n)。 例： Dijkstra的最短路徑算法、 Kruskal的求最小生成樹算法、信號燈問題 2022/5/30 史忠植 高級人工智能 28 回溯算法 有些問題需要徹底的搜索才能解決問題，然而，徹底的搜索要以大量的運算時間為代價，對于這種情況可以通過回溯法來去掉一些分支，從而大大減少搜索的次數(shù)。 最簡單的情形是所謂的結(jié)點不一致性 。 另一種重復(fù)的情形 是所謂的弧不一致性 。 2022/5/30 史忠植 高級人工智能 34 CONSTRAINT PROPAGATION All of the Mackworth algorithms 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: ? ?? ?yxPDDxD wyvv ,s uc h t ha t :: ???? 2022/5/30 史忠植 高級人工智能 35 CONSTRAINT PROPAGATION Mackworth 1977 AC1 AC2 AC3 2022/5/30 史忠植