【正文】 2022/5/30 史忠植 高級人工智能 1 高級人工智能 第三章 約束推理 史忠植 中國科學院計算技術所 2022/5/30 史忠植 高級人工智能 2 第三章 約束推理 概述 回溯法 約束傳播 回跳法 約束推理系統(tǒng) COPS ILOG SOLVER 2022/5/30 史忠植 高級人工智能 3 概述 最優(yōu)化問題 經(jīng)濟學所推崇的帕累托最優(yōu) : 幾個人拎著水桶在一個水龍頭前面排隊打水，水 桶有大有小。他們怎樣排隊，才能使得總的排隊 時間最短。這是一個尋求“最優(yōu)化”的題目，目標 是節(jié)省總的排隊時間，達到最優(yōu)。 2022/5/30 史忠植 高級人工智能 4 概述 優(yōu)化問題 ? 運籌學 ? 遺傳算法 ? 神經(jīng)網(wǎng)絡 ? 約束推理 2022/5/30 史忠植 高級人工智能 5 運籌學的工作步驟 ?1）提出和形成問題， ?2）建立模型， ?3）求解， ?4）解的檢驗， ?5）解的控制， ?6）解的實施。 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) 包含一組變量與一組變量間的約束。 ?變量表示領域參數(shù)，每個變量都有一個固定的值域。 一個變量的值域可能是有限的，例如一個布爾變量的值 域包含兩個值；也可能是離散無限的，如整數(shù)域；也可 能是連續(xù)的，如實數(shù)域。 {x1,x2,…xn}, {D1,D2,…Dn}, . {4,5,6,7} red, green,blue} 2022/5/30 史忠植 高級人工智能 13 概述 ?約束可用于描述領域?qū)ο蟮男再|(zhì)、相互關系、任務 要求、目標等。約束 滿足問題 的目標就是找到所有 變量的一個（或多個）賦值，使所有約束都得到滿足。 ?一元謂詞。 ?序關系語言，只包含偏序關系或?qū)嵶兞可系拇笮￡P系。 ?形如 “ x y c” 的方程。 ?單位系數(shù)的線性方程與不等式，即所有的系數(shù)為 1,0,1。 ?任意系數(shù)的線性方程與不等式。 ?約束的布爾組合。 ?代數(shù)與三角方程。 2022/5/30 史忠植 高級人工智能 14 概述 約束表示易于理解、編碼及有效實現(xiàn)，它具有以下優(yōu)點 : ? 約束表示允許以說明性的方式來表達領域知識，表達 能力較強，應用程序只需指定問題的目標條件及數(shù)據(jù)間 的相互關系。因而具有邏輯表示的類似性質(zhì)。 ? 約束表示允許變量的域包含任意多個值，而不像命題 只取真假二值。所以它保存了問題的一些結構信息，如 變量域的大小、變量間的相關性等，從而為問題求解提供 啟發(fā)式信息。 ? 易于并行實現(xiàn)。因為約束網(wǎng)絡上的信息傳播可以認為是 同時的。 ? 適合于遞增型系統(tǒng)。約束可以遞增式地加入到約束網(wǎng)絡。 ? 易于與領域相關的問題求解模型相銜接。各種數(shù)學規(guī)劃技 術，方程求解技術等 , 都可以自然地嵌入約束系統(tǒng)。 2022/5/30 史忠植 高級人工智能 15 約束推理 ? 約束搜索 約束搜索主要研究有限域上的約束滿足。對有限域而言， 約束滿足問題一般情況下 是 一個 NP 問題。 ? 約束語言 2022/5/30 史忠植 高級人工智能 16 約束搜索 ? 回溯法。 ? 約束傳播。 ? 智能回溯與真值維護。 ? 可變次序例示。 ? 局部修正法。 2022/5/30 史忠植 高級人工智能 17 約束語言 CONSTRAINTS CHIP COPS ILOG 2022/5/30 史忠植 高級人工智能 18 CONSTRAINTS約束語言 CONSTRAINTS是一個面向電路描述的約束表示語言。 作為一個約束表示語言， 它使用了符號處理技術來求解數(shù)學方程。 在 CONSTRAITS中，物理部件的功能及器件的結構都用約束表示。 這些約束一般是線性方程與不等式 , 也包括條件表達式。約束變量 一般是表示物理量的實變量。也有一些取離散值的變量。如開關的狀 態(tài)、三極管的工作狀態(tài)等。系統(tǒng)采用表達式推理與