【正文】 理想耗散 ? 該值要盡可能地小 第 2章 搜索技術(shù) 75 競(jìng)爭(zhēng)率 (2) ? 影響競(jìng)爭(zhēng)率的因素，使其無(wú)窮大 ? 行動(dòng)不可逆 —進(jìn)入一個(gè)不可到達(dá)目標(biāo)的狀態(tài)又不可回溯 ? 沒(méi)有算法能夠在所有的狀態(tài)空間中避免死路 (p98圖 ) ? 因此，通常需要假設(shè)狀態(tài)空間是可安全探索的 —具有可逆的狀態(tài)空間 / 從每個(gè)可達(dá)狀態(tài)出發(fā)都有可達(dá)的目標(biāo)狀態(tài) ? 不過(guò)，在可逆狀態(tài)空間中，因?yàn)閷?duì)手的存在，也會(huì)出現(xiàn)無(wú)界競(jìng)爭(zhēng)率的情況 (p98圖 ) 第 2章 搜索技術(shù) 76 聯(lián)機(jī)搜索智能體 ? 聯(lián)機(jī)搜索智能體需要行動(dòng)和感知，然后擴(kuò)展當(dāng)前狀態(tài)的環(huán)境地圖 ? 區(qū)別：聯(lián)機(jī) —規(guī)劃與行動(dòng)交叉 / 脫機(jī) —只要規(guī)劃 ? 例子： A*搜索在不同子空間節(jié)點(diǎn)的跳躍式擴(kuò)展，模擬而非實(shí)際行動(dòng) / 聯(lián)機(jī)算法只擴(kuò)展目前實(shí)際占據(jù)的節(jié)點(diǎn) —采用深度優(yōu)先搜索 ? 聯(lián)機(jī)搜索必須維護(hù)一個(gè)回溯表 第 2章 搜索技術(shù) 77 演講完畢，謝謝觀看！ 。人工智能原理 第 2章 搜索技術(shù) （上） 1 本章內(nèi)容 搜索與問(wèn)題求解 無(wú)信息搜索策略 啟發(fā)式搜索策略 局部搜索算法 約束滿足問(wèn)題 博弈搜索 參考書(shū)目 附錄 A*算法可采納性的證明 第 2章 搜索技術(shù) 2 搜索與問(wèn)題求解 問(wèn)題與問(wèn)題的解 問(wèn)題實(shí)例 搜索策略 第 2章 搜索技術(shù) 3 搜索與問(wèn)題求解 ? 問(wèn)題求解過(guò)程是搜索答案 (目標(biāo) )的過(guò)程 / 所以問(wèn)題求解技術(shù)也叫搜索技術(shù) —通過(guò)對(duì)狀態(tài)空間的搜索而求解問(wèn)題的技術(shù) ? 問(wèn)題求解智能體是一種基于目標(biāo)的智能體 ? 在尋找到達(dá)目標(biāo)的過(guò)程中，當(dāng)智能體面對(duì)多個(gè)未知的選項(xiàng)時(shí)，首先檢驗(yàn)各個(gè)不同的導(dǎo)致已知評(píng)價(jià)的狀態(tài)的可能行動(dòng)序列，然后選擇最佳序列 — 這個(gè)過(guò)程就是搜索 第 2章 搜索技術(shù) 4 問(wèn)題與問(wèn)題的解 ? 問(wèn)題可以形式化地定義為 4個(gè)組成部分 ? 智能體的初始狀態(tài) (即搜索的開(kāi)始 ) ? 后繼函數(shù) — 智能體采取的可能行動(dòng)的描述，通常為 行動(dòng)，后繼狀態(tài) / 初始狀態(tài)和后繼函數(shù)隱含地定義了問(wèn)題的狀態(tài)空間 / 狀態(tài)空間中的一條路徑是通過(guò)行動(dòng)序列連接起來(lái)的一個(gè)狀態(tài)序列 ? 目標(biāo)測(cè)試 — 檢查給定的狀態(tài)是不是目標(biāo) ? 路徑耗散函數(shù) — 每條路徑都有一個(gè)數(shù)值化的耗散值，反映了性能度量 / 求解問(wèn)題的代價(jià) 第 2章 搜索技術(shù) 5 問(wèn)題的解 ? 問(wèn)題的解就是初始狀態(tài)到目標(biāo)狀態(tài)的路徑 ? 解的優(yōu)劣由路徑耗散函數(shù)量度 (代價(jià) ) ? 最優(yōu)解就是路徑耗散函數(shù)值最小的路徑 ? 上述解題過(guò)程把解決一個(gè)問(wèn)題的過(guò)程描述出來(lái)，稱之為解題知識(shí)的過(guò)程性表示 ? 過(guò)程性知識(shí)與陳述性知識(shí)相對(duì) ? 搜索過(guò)程解題的特點(diǎn) — 沒(méi)有直接的方法(公式 )可以求解，而是一步一步的探索 第 2章 搜索技術(shù) 6 狀態(tài)空間 ? 數(shù)據(jù)基：代表了所要解決的問(wèn)題 ， 有初始狀態(tài) ， 可能有目標(biāo)狀態(tài)也可能沒(méi)有 ? 狀態(tài)空間：在解題過(guò)程中的每一時(shí)刻 ，數(shù)據(jù)基都處于一定的狀態(tài) ， 數(shù)據(jù)基所有可能狀態(tài)的集合稱為狀態(tài)空間 ? 有向圖：若把每個(gè)狀態(tài)看成一個(gè)節(jié)點(diǎn) ，則整個(gè)狀態(tài)空間是一個(gè)有向圖 / 該圖不一定全連通 ， 即從某些狀態(tài)不一定能到達(dá)另外一些狀態(tài) 第 2章 搜索技術(shù) 7 問(wèn)題的可解性 ? 可解的：在每個(gè)連通部分，每個(gè)弧代表一個(gè)運(yùn)算符，將狀態(tài)改變 / 如果從代表初始狀態(tài)的節(jié)點(diǎn)出發(fā)，有一條路徑通向目標(biāo)狀態(tài)，則稱此目標(biāo)狀態(tài)所代表的問(wèn)題在當(dāng)前初始狀態(tài)下是可解的 ? 搜索空間：在解題過(guò)程中達(dá)到過(guò)的所有狀態(tài)的集合，稱為搜索空間 ? 不同于狀態(tài)空間， 搜索空間 只是其中一部分 ? 狀態(tài)空間和搜索空間都屬于過(guò)程性知識(shí)表示 第 2章 搜索技術(shù) 8 問(wèn)題實(shí)例 ? 玩具問(wèn)題 ? 八數(shù)碼游戲 (九宮圖 ) ? 河內(nèi)塔 ? 八皇后問(wèn)題 ? 真空吸塵器世界 ? 現(xiàn)實(shí)問(wèn)題 ? 旅行商問(wèn)題 ? 超大規(guī)模集成電路的布局 ? 自動(dòng)裝配排序 / 蛋白質(zhì)設(shè)計(jì) ? 互聯(lián)網(wǎng)搜索 第 2章 搜索技術(shù) 9 八數(shù)碼游戲 ? 八數(shù)碼游戲： 18數(shù)字 (棋子 )/9個(gè)方格 (棋盤格 )/1個(gè)空格 ? 可用如下形式的規(guī)則來(lái)表示數(shù)字通過(guò)空格進(jìn)行移動(dòng)：a1,a2,a3,a4,a5,a6,a7,a8,a9→b1,b2,b3,b4,b5,b6,b7,b8,b9 ? 共 24條規(guī)則 =4角 *2+4邊 *3+1中間 *4 ? 搜索順序舉例： (1)優(yōu)先移動(dòng)行數(shù)小的棋子 (數(shù)字 ) (2)同一行中優(yōu)先移動(dòng)列數(shù)大的棋子 ? 約束規(guī)則：不使離開(kāi)既定位置的數(shù)字?jǐn)?shù)增加 第 2章 搜索技術(shù) 10 八數(shù)碼游戲的搜索樹(shù) 第 2章 搜索技術(shù) B e g i n * * * * * * E nd *1 5 24 36 7 81 24 5 36 7 81 5 24 36 7 81 5 24 7 36 81 5 24 36 7 81 24 5 36 7 81 24 5 36 7 81 54 3 26 7 81 5 24 3 86 71 2 34 56 7 84 1 25 36 7 81 54 3 26 7 81 5 24 3 86 71 2 34 56 7 84 1 25 36 7 84 1 26 5 37 81 3 54 26 7 8既定位置 =終態(tài) 11 八數(shù)碼問(wèn)題形式化 ? 初始狀態(tài) ? 初始狀態(tài)向量 — 規(guī)定向量中各分量對(duì)應(yīng)的位置，各位置上的初始數(shù)字 ? 后繼函數(shù) ? 移動(dòng)規(guī)則 — 按照某條規(guī)則移動(dòng)數(shù)字，將得到的新向量 ? 目標(biāo)測(cè)試 ? 新向量是否是目標(biāo)狀態(tài) (也是向量形式 ) ? 路徑耗散函數(shù) ? 每次移動(dòng)代價(jià)為 1 第 2章 搜索技術(shù) 12 河內(nèi)塔 (1) ? 河內(nèi)塔問(wèn)題： n個(gè)大小不等的圓盤從一個(gè)柱子移到另一個(gè)柱子，共有 3個(gè)柱子 (n階河內(nèi)塔問(wèn)題 ) ? 約束：從第 1根柱子移動(dòng)到第 3根柱子上去，利用第 2根柱子 / 每次移動(dòng) 1個(gè)盤子，且移動(dòng)過(guò)程必須是小盤落大盤 ? 描述：設(shè)每個(gè)狀態(tài)為 (a1, a2, a3, …, a n), ai=1, 2, 3—表示第 i個(gè)盤子在第 1/2/3根柱子上 第 2章 搜索技術(shù) 13 河內(nèi)塔 (2) ? 遞歸定義： {(a1, a2, a3, …, a n)}為 n階河內(nèi)塔的狀態(tài)集合，則 {(a1, a2, a3, …, a n, 1), (a1, a2, a3, …, a n, 2), (a1, a2, a3, …, a n, 3)}是 n+1階河內(nèi)塔的狀態(tài)集合 ? 1階河內(nèi)塔有 3個(gè)狀態(tài)， 2階河內(nèi)塔有 9個(gè)狀態(tài)， n階河內(nèi)塔有 3n個(gè)狀態(tài)，給出1/2/3階河內(nèi)塔的狀態(tài)圖 第 2章 搜索技術(shù) 14 河內(nèi)塔問(wèn)題圖解 第 2章 搜索技術(shù) ( 3 , 3 , 2 ) ( 2,3,2 ) ( 1,3, 2) ( 2,1,2 ) ( 2 ,3,2) ( 1,1,2 ) ( 3,1, 2) ( 3,2,2 ) ( 2,2, 2) ( 1,1,1 ) ( 3 , 1 , 1 ) ( 3 , 2 , 1 ) ( 2 , 2 , 1 ) ( 1 , 2 , 1 ) ( 2,2,3 ) ( 1,2,3 ) ( 1,3,3 )( 3,3,3 ) ( 2, 3,3) ( 2,1,3 ) ( 1,1, 3) ( 3,3,1 )( 1,3,1 ) ( 2,1,1 ) ( 2,3,1 ) ( 3,1) ( 2,1