人工智能及其應(yīng)用chapter3_071101課件

1、3.1 搜索系統(tǒng)的組成 搜索系統(tǒng)由以下三大成分構(gòu)成 ：知識庫：描述當(dāng)前任務(wù)的范圍以及要求解問題的目標(biāo)。規(guī)則 :用于對數(shù)據(jù)庫的加工處理?？刂菩灾R：決定下一步應(yīng)如何做？選擇什么操作？在何處使用此控制？ 人工智能及其應(yīng)用1 3.2 問題表示及求解方法 問題表達(dá)及其變換問題的直接求解法狀態(tài)空間圖搜索算法 人工智能及其應(yīng)用2問題表達(dá)及其變換 同構(gòu)同態(tài)變換問題分解法與圖（樹）描述問題分解?；驁D（樹）描述同構(gòu)同態(tài)變換 。人工智能及其應(yīng)用3問題的直接求解法 狀態(tài)空間求解法用狀態(tài)描述與問題相關(guān)的事實(shí)和事實(shí)間的關(guān)系。狀態(tài)常表示為矢量。問題的狀態(tài)空間可記為三元組(S，F(xiàn)，G)。 問題演繹法 基本思想：分解原問題成

2、若干個(gè)子問題。博弈問題求解法 屬于對策性課題，表示若干個(gè)體開展競爭的過程。 人工智能及其應(yīng)用4狀態(tài)空間圖搜索算法搜索法求解問題的基本思想： 將初始狀態(tài)當(dāng)作當(dāng)前狀態(tài)。 選擇適當(dāng)?shù)乃惴饔糜诋?dāng)前狀態(tài)得到后繼狀態(tài)。檢查這組后繼狀態(tài)中是否有目標(biāo)狀態(tài)。已擴(kuò)展節(jié)點(diǎn)、未擴(kuò)展節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)人工智能及其應(yīng)用5狀態(tài)空間圖搜索算法狀態(tài)空間搜索算法流程： 人工智能及其應(yīng)用6 3.3 基本推理技術(shù) 推理的概念及其類型 推理的控制策略人工智能及其應(yīng)用7推理的概念及其類型定義： 從已有事實(shí)和知識中推出結(jié)論。 在人工智能系統(tǒng)中，推理機(jī)是由程序?qū)崿F(xiàn)的，它利用知識庫中的知識，按一定的控制策略求解問題。 人工智能及其應(yīng)用8推理的概

3、念及其類型推理方法分類：按途徑分： 演繹推理、歸納推理、默認(rèn)推理。按所用知識的確定性分： 確定性推理、不確定推理。 按結(jié)論是否單調(diào)增加分： 單調(diào)推理、非單調(diào)推理。按推理中是否運(yùn)用啟發(fā)性知識分： 啟發(fā)式推理、非啟發(fā)式推理。 人工智能及其應(yīng)用9推理的控制策略推理系統(tǒng)構(gòu)成： 知識庫 、數(shù)據(jù)庫 、推理機(jī) 。推理方向： (1) 正向推理：由已知事實(shí)出發(fā)向結(jié)論方向的推理，也稱事實(shí)驅(qū)動推理。 (2) 反向推理：以某個(gè)假設(shè)目標(biāo)作為出發(fā)點(diǎn)的推理，也稱為目標(biāo)驅(qū)動推理或逆向推理。 (3) 正反向混合推理: 正向和反向推理相結(jié)合的推理。人工智能及其應(yīng)用10推理的控制策略搜索策略： 狀態(tài)空間搜索(廣度優(yōu)先搜索、深度優(yōu)先

4、搜索、有界深度優(yōu)先搜索等 )、啟發(fā)式搜索等。沖突解決策略：(1) 專一性排序 (5) 上下文限制 (2) 規(guī)則排序 (6) 按匹配度排序 (3) 數(shù)據(jù)排序 (7) 按條件個(gè)數(shù)排序 (4) 就近排序人工智能及其應(yīng)用11 3.4 搜索策略的效率 穿透率 有效分支因素 提高搜索效率的一般原則 人工智能及其應(yīng)用12穿透率 定義：反映目標(biāo)搜索時(shí)的搜索范圍。P還和問題的難度相關(guān)，一般是L越大，問題越困難，P值越?。环粗甈則越大。人工智能及其應(yīng)用13有效分支因素 定義：有效節(jié)點(diǎn)平均生成的子節(jié)點(diǎn)總數(shù): 搜索策略的有效分支因素評價(jià): 搜索策略的外顯率評價(jià): 人工智能及其應(yīng)用14提高搜索效率的一般原則 定性策略：

5、 特殊優(yōu)先策略 新知識優(yōu)先策略 差異性優(yōu)先策略 其它策略 人工智能及其應(yīng)用153.5 基本搜索策略特點(diǎn):非啟發(fā)的、解決樹狀結(jié)構(gòu)問題廣度優(yōu)先搜索 深度優(yōu)先搜索 有界深度優(yōu)先搜索代價(jià)推進(jìn)搜索 人工智能及其應(yīng)用16廣度優(yōu)先搜索搜索原則：深度越小、越早生成結(jié)點(diǎn)的優(yōu)先級越高。當(dāng)最低層不止一個(gè)結(jié)點(diǎn)時(shí)，它選擇最先生成的結(jié)點(diǎn)進(jìn)行搜索。 人工智能及其應(yīng)用17廣度優(yōu)先搜索例3-4：八數(shù)碼問題(1)操作規(guī)定: 允許空格四周上、下、左、右的數(shù)碼塊移入空格中，不許斜方向移動，不許返回先輩結(jié)點(diǎn)。初始布局S和目標(biāo)狀態(tài)D如下圖所示： 人工智能及其應(yīng)用18廣度優(yōu)先搜索例3-4的廣度優(yōu)先搜索樹：人工智能及其應(yīng)用19廣度優(yōu)先搜索廣

6、度優(yōu)先算法步驟：(1) 初始結(jié)點(diǎn)S加入到隊(duì)列OPEN的尾部；(2) 若OPEN為空，則搜索失敗，問題無解；(3) 取出OPEN隊(duì)頭的結(jié)點(diǎn)n，并放入CLOSE隊(duì)列中；(4) 若n是目標(biāo)結(jié)點(diǎn)D，則搜索成功，問題有解；(5) 若n是葉結(jié)點(diǎn)，則轉(zhuǎn)(2)；(6) 擴(kuò)展n結(jié)點(diǎn)(即找出它的所有直接后繼)，并把它的諸子結(jié)點(diǎn)依次加入OPEN隊(duì)尾，修改這些子結(jié)點(diǎn)的返回指針，使其指向結(jié)點(diǎn)n。轉(zhuǎn)(2)。人工智能及其應(yīng)用20深度優(yōu)先搜索搜索原則：深度越大、越晚產(chǎn)生結(jié)點(diǎn)的優(yōu)先級越高。深度優(yōu)先搜索是不完備的，屬于非算法的搜索過程。 人工智能及其應(yīng)用21深度優(yōu)先搜索例3-5：八數(shù)碼問題(2)操作規(guī)定已在廣度優(yōu)先搜索算法舉例中

7、介紹過。初始布局S和目標(biāo)狀態(tài)D如下圖所示： 人工智能及其應(yīng)用22深度優(yōu)先搜索例3-5的深度優(yōu)先搜索樹：人工智能及其應(yīng)用23深度優(yōu)先搜索深度優(yōu)先算法步驟：(1) 初始結(jié)點(diǎn)S放入堆棧OPEN中； (2) 若OPEN為空，則搜索失敗，問題無解； (3) 彈出OPEN表中最頂端結(jié)點(diǎn)放到CLOSE表中，并給出順序編號n； (4) 若n為目標(biāo)結(jié)點(diǎn)D，則搜索成功，問題有解； (5) 若n無子結(jié)點(diǎn)，轉(zhuǎn)(2)；(6) 擴(kuò)展n結(jié)點(diǎn)，將其所有子結(jié)點(diǎn)配上返回n的指針，并按次序壓入OPEN堆棧，轉(zhuǎn)(2) 。人工智能及其應(yīng)用24有界深度優(yōu)先搜索特點(diǎn)： 引入搜索深度限制值d，使深度優(yōu)先搜索過程具有完備性 。例3-6：八數(shù)碼

8、問題(2) 設(shè)定搜索深度限制d=5，問題同深度優(yōu)先算法中的八數(shù)碼問題(2)。人工智能及其應(yīng)用25有界深度優(yōu)先搜索例3-6的有界深度優(yōu)先搜索樹：人工智能及其應(yīng)用26有界深度優(yōu)先搜索有界深度優(yōu)先算法步驟：(1)初始結(jié)點(diǎn)S放入堆棧OPEN中；(2)若OPEN為空，則搜索失敗，問題無解；(3)彈出OPEN中棧頂結(jié)點(diǎn)n，放入CLOSE表中，并給出順序編號n；(4)若n為目標(biāo)結(jié)點(diǎn)D，則搜索成功，問題有解；(5)若n的深度d(n)=d，則轉(zhuǎn)(2) ；(6)若n無子結(jié)點(diǎn)，即不可擴(kuò)展，轉(zhuǎn)(2) ；(7)擴(kuò)展結(jié)點(diǎn)n，將其所有子結(jié)點(diǎn)配上返回n的指針，并壓入OPEN堆棧，轉(zhuǎn)(2) 。人工智能及其應(yīng)用27代價(jià)推進(jìn)搜索特

9、點(diǎn)： 節(jié)點(diǎn)間有向邊的代價(jià)不同算法修改：(1)廣度優(yōu)先搜索法：每次從OPEN表中取出具有最小代價(jià)的節(jié)點(diǎn)進(jìn)行擴(kuò)展 。(2)有界深度優(yōu)先搜索法：用代價(jià)限制g代替深度限制d，用代價(jià)g(n)代替節(jié)點(diǎn)深度d(n)。 人工智能及其應(yīng)用28代價(jià)推進(jìn)搜索例3-7 ： 求下圖所示的旅行問題中，費(fèi)用最小的路線，設(shè)出發(fā)地是A城，目的地是E城，圖中各邊上的數(shù)字代表交通費(fèi)用。 人工智能及其應(yīng)用29代價(jià)推進(jìn)搜索例3-7的代價(jià)推進(jìn)搜索樹：人工智能及其應(yīng)用303.6 啟發(fā)式搜索策略啟發(fā)信息和估價(jià)函數(shù) 局部擇優(yōu)搜索 全局擇優(yōu)搜索 A*算法 人工智能及其應(yīng)用31啟發(fā)信息和估價(jià)函數(shù)啟發(fā)信息： 與具體問題解相關(guān)的控制性知識 。估價(jià)函數(shù)

10、： 估計(jì)OPEN表中各擴(kuò)展節(jié)點(diǎn)的重要程度，給它們排定擴(kuò)展次序。 人工智能及其應(yīng)用32局部擇優(yōu)搜索基本思想 ： 選擇一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)，是在它的所有子節(jié)點(diǎn)中，選估價(jià)函數(shù)f(n)最優(yōu)者。因此，亦稱“瞎子爬山法”。特點(diǎn)：可以取消OPEN表，每次擴(kuò)展后只保留一個(gè)最優(yōu)子節(jié)點(diǎn)，直接放入CLOSE表中，丟掉其它子節(jié)點(diǎn)。主要在單因素、單極值情況下使用；在多因素，多極值情況下，找不到最佳解。 人工智能及其應(yīng)用33局部擇優(yōu)搜索例3-8 ： 在深度優(yōu)先搜索算法的八數(shù)碼問題(2)中，如果把估價(jià)函數(shù)定義為f(n)=w(n)，其中，w(n)表示結(jié)點(diǎn)n的格局與目標(biāo)結(jié)點(diǎn)D格局相比位置不符的數(shù)碼個(gè)數(shù)。用局部擇優(yōu)搜索策略求解該問

11、題 。其搜索樹如下頁圖所示：人工智能及其應(yīng)用34例3-8的局部擇優(yōu)搜索樹：人工智能及其應(yīng)用35全局擇優(yōu)搜索特點(diǎn)：在OPEN表中保留所有已生成而未擴(kuò)展的節(jié)點(diǎn)，并用估價(jià)函數(shù)f(n)對它們?nèi)窟M(jìn)行估計(jì)，從中選出最優(yōu)的節(jié)點(diǎn)進(jìn)行擴(kuò)展，因此，亦稱“最好優(yōu)先搜索法” 。得到的不一定是實(shí)際上的最佳解。 人工智能及其應(yīng)用36全局擇優(yōu)搜索例3-9：八數(shù)碼問題(2)如果將廣度優(yōu)先搜索算法中的估計(jì)函數(shù)定義為：f(n) = d(n) + w(n)，其中，d(n)代表結(jié)點(diǎn)n的擴(kuò)展深度，w(n)含義同例3-8。用全局擇優(yōu)搜索法求解此問題。其搜索樹如下頁圖所示。圖中，狀態(tài)結(jié)點(diǎn)右邊圓圈中的數(shù)字表示估價(jià)函數(shù)值。 人工智能及其應(yīng)用37全局擇優(yōu)搜索例3-9的全局擇優(yōu)搜索樹：人工智能及其應(yīng)用38A*算法特點(diǎn)：對狀態(tài)空間搜索算法中的擴(kuò)展節(jié)點(diǎn)選擇原則進(jìn)行了限制。選用了一個(gè)比較特殊的估價(jià)函數(shù)。定義:A*算法A 算法 性質(zhì):采納性單調(diào)性信息性人工智能及其應(yīng)用393.7 基于規(guī)劃的啟發(fā)式搜索原理 基本規(guī)劃 多層規(guī)劃 人工智能及其應(yīng)用40基本規(guī)劃 規(guī)劃解決問題的方法:引入一系列子目標(biāo) 把問題分解成若干子問題 解決子問題產(chǎn)生規(guī)劃的基本方法:差異減小法 人工智能及其應(yīng)用41多層規(guī)劃 多層規(guī)劃解決問題的方法:給出一個(gè)總的粗略設(shè)想 逐步細(xì)化設(shè)想產(chǎn)生詳盡規(guī)劃為止 人工智能及其應(yīng)用42多層規(guī)劃 例3-12: 假設(shè)有A、B