【正文】 要求、目標(biāo)等。 2022/5/30 史忠植 高級(jí)人工智能 4 概述 優(yōu)化問(wèn)題 ? 運(yùn)籌學(xué) ? 遺傳算法 ? 神經(jīng)網(wǎng)絡(luò) ? 約束推理 2022/5/30 史忠植 高級(jí)人工智能 5 運(yùn)籌學(xué)的工作步驟 ?1）提出和形成問(wèn)題， ?2）建立模型， ?3）求解， ?4）解的檢驗(yàn)， ?5）解的控制， ?6）解的實(shí)施。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ì)打水，水 桶有大有小。 2022/5/30 史忠植 高級(jí)人工智能 6 線性規(guī)劃問(wèn)題 ? 例 1(廣告方式的選擇 )中華家電公司推銷一種新型洗衣機(jī) ,有關(guān)數(shù)據(jù)見(jiàn)下表 .銷售部第一月的廣告預(yù)算為 20220元 ,要求至少有8電視商業(yè)節(jié)目 ,15家報(bào)紙廣告 /電視廣告費(fèi)不得超過(guò) 12022元 ,電臺(tái)廣播至少隔日有一次 .現(xiàn)問(wèn)該公司銷售部應(yīng)當(dāng)采用怎樣的廣告宣傳計(jì)劃 ,才能取得最好的效果 ? 2022/5/30 史忠植 高級(jí)人工智能 7 表 1 廣告方式 廣告費(fèi)用 (元 /次 ) 可用最高次數(shù) /月 期望的宣傳效果 /單位 電視臺(tái) a(白天 ,1 分鐘 ) 500 16 50 電視臺(tái) b(晚上 ,30鈔 ) 1000 10 80 每日晨報(bào) /(半版 ) 100 24 30 星期日?qǐng)?bào) /(半版 ) 300 4 40 廣播電臺(tái) /(1分鐘 ) 80 25 15 2022/5/30 史忠植 高級(jí)人工智能 8 解 : 設(shè) 54321, xxxxx分別是第一個(gè)月內(nèi)電視臺(tái) a, 電視臺(tái)b, 每日晨報(bào) , 星期日?qǐng)?bào) , 廣播電臺(tái)進(jìn)行廣告宣傳的次數(shù) , 則其數(shù)學(xué)模型為 : m a x 543211540308050 xxxxx ???? s . t . .0,2515,4,24,10,16,120221000500,15,8,20220803001001000500543215432121432154321??????????????????xxxxxxxxxxxxxxxxxxxxx 2022/5/30 史忠植 高級(jí)人工智能 9 線性規(guī)劃問(wèn)題 ( 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 史忠植 高級(jí)人工智能 10 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式為 : m i n XCzT? s .t . 0??XbAX( 假定 b 為非負(fù) ) 注 : 任何形式的線性規(guī)劃問(wèn)題均可化為標(biāo)準(zhǔn)型 2022/5/30 史忠植 高級(jí)人工智能 11 求解 單純形法 ? 將所給問(wèn)題化為標(biāo)準(zhǔn)形 ? 找出一個(gè)初始可行基 ,建立初始單純形表 ? 檢查所有檢驗(yàn)數(shù) (若全為非負(fù) ,則已得到最優(yōu)解 ,計(jì)算停止 .否則繼續(xù)下一步 ) ? 考察是否無(wú)解 (若是 ,計(jì)算停止 ,否則繼續(xù)下一步 ) ? 確定入基變量 ,出基變量 ? 對(duì)初始單純形表進(jìn)行單純形變換 2022/5/30 史忠植 高級(jí)人工智能 12 概述 一個(gè)約束滿足問(wèn)題 (Constraint Satisfaction Problem, 簡(jiǎn)稱 CSP) 包含一組變量與一組變量間的約束。約束 滿足問(wèn)題 的目標(biāo)就是找到所有 變量的一個(gè)（或多個(gè)）賦值，使所有約束都得到滿足。 ?單位系數(shù)的線性方程與不等式，即所有的系數(shù)為 1,0,1。 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)系。 ? 易于并行實(shí)現(xiàn)。 ? 易于與領(lǐng)域相關(guān)的問(wèn)題求解模型相銜接。 ? 約束語(yǔ)言 2022/5/30 史忠植 高級(jí)人工智能 16 約束搜索 ? 回溯法。 ? 局部修正法。 這些約束一般是線性方程與不等式 , 也包括條件表達(dá)式。系統(tǒng)采用表達(dá)式推理與值推理。 同時(shí)，約束傳播方法比較單一，既缺乏實(shí)域上的區(qū)間傳播機(jī)制， 也缺乏有限域上的 域傳播機(jī)制。 CHIP 主要應(yīng)用于兩個(gè)領(lǐng)域 : 運(yùn)籌學(xué)與硬件設(shè)計(jì)。內(nèi)部求解時(shí)采用約束推理機(jī)制，使說(shuō)明性約 束表達(dá)式與類型層次相結(jié)合，實(shí)現(xiàn)知識(shí)的結(jié)構(gòu)化封裝，充分發(fā)揮 兩者的優(yōu)點(diǎn)，力圖實(shí)現(xiàn)一個(gè)具有較強(qiáng)表達(dá)能力和較高求解效率的 約束滿足系統(tǒng)。 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í)和研究。 算法的時(shí)間代價(jià) (或稱 時(shí)間復(fù)雜性 )：當(dāng)問(wèn)題規(guī)模以某種單位由 1增至 n時(shí)，對(duì)應(yīng)算法所耗費(fèi)的時(shí)間也以某種單位由 g(1)增至 g(n)，這時(shí)我們稱算法的時(shí)間代價(jià)是 g(n)。 例： Dijkstra的最短路徑算法、 Kruskal的求最小生成樹(shù)算法、信號(hào)燈問(wèn)題 2022/5/30 史忠植 高級(jí)人工智能 28 回溯算法 有些問(wèn)題需要徹底的搜索才能解決問(wèn)題，然而，徹底的搜索要以大量的運(yùn)算時(shí)間為代價(jià)，對(duì)于這種情況可以通過(guò)回溯法來(lái)去掉一些分支，從而大大減少搜索的次數(shù)。 最簡(jiǎn)單的情形是所謂的結(jié)點(diǎn)不一致性 。 另一種重復(fù)的情形 是所謂的弧不一致性 。 2022/5/30 史忠植 高級(jí)人工智能 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 史忠植 高級(jí)人工智能 35 CONSTRAINT PROPAGATION Mackworth 1977 AC1 AC2 AC3 2022/5/30 史忠植