【正文】 1 把初始節(jié)點(diǎn) S0放入 CLOSED表中； ? 步 2 令 N= S0 ； ? 步 3 若 N是目標(biāo)節(jié)點(diǎn)，則搜索成功，結(jié)束 。 ?廣度優(yōu)先搜索算法： ? 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中； ? 步 2 若 OPEN表為空，則搜索失敗，退出； ? 步 3 取 OPEN表中前面第一個(gè)節(jié)點(diǎn) N放入 CLOSED表中； ? 步 4 若目標(biāo)節(jié)點(diǎn) Sg =N，則搜索成功，結(jié)束 。初始狀態(tài) (2， 3， 1， 8， 4， 7， 6，5)，目標(biāo)狀態(tài) (1， 2， 3， 8， 4， 7， 6， 5) 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 1 2 5 6 7 3 1 2 3 8 4 7 6 5 目標(biāo) 8 2 3 4 1 8 7 6 5 4 窮舉式搜索 ?深度優(yōu)先搜索：在搜索的每一層，始終只擴(kuò)展一個(gè)節(jié)點(diǎn)，不斷地向縱深前進(jìn)，直到不能再前進(jìn)時(shí)，才從當(dāng)前節(jié)點(diǎn)返回到上一級(jí)節(jié)點(diǎn)，延另一節(jié)點(diǎn)又繼續(xù)前進(jìn)。 (OPEN表為一個(gè)堆棧 ) 窮舉式搜索 ?廣度優(yōu)先搜索的性質(zhì) ? 當(dāng)問題有解時(shí)，一定能找到解 ? 當(dāng)問題為單位耗散值，且問題有解時(shí)，一定能找到最優(yōu)解 ? 方法與問題無關(guān)，具有通用性 ? 效率較低 ?深度優(yōu)先搜索的性質(zhì) ? 一般不能保證找到最優(yōu)解 ? 當(dāng)深度限制不合理時(shí)，可能找不到解 ? 最壞情況時(shí)，搜索空間等同于窮舉 ? 是一個(gè)通用的與問題無關(guān)的方法 窮舉式搜索 ?有界深度優(yōu)先搜索：搜索深度限制。 ? 步 6 擴(kuò)展 N，將其所有子節(jié)點(diǎn) Ni配上指向 N的返回指針后依次放入 OPEN表的前部，置 d(Ni)=d(N)+1，轉(zhuǎn)步 2。 ? 步 6 擴(kuò)展 N，計(jì)算每個(gè)子節(jié)點(diǎn) x的函數(shù)值 h(x)，并將所有子節(jié)點(diǎn)配上指向 N的返回指針放入 OPEN表中，再對(duì) OPEN表中的 所有子節(jié)點(diǎn) 按其函數(shù)值大小以升序排序，轉(zhuǎn)步 2。 g(S0)=0. ?分支界限法：相當(dāng)于啟發(fā)式搜索中的全局擇優(yōu)搜索，不過用代價(jià)函數(shù)代替啟發(fā)函數(shù)。 或定義為： f(x)=d(x)+h(x)。 ? 可以看出， A算法是樹式搜索算法加估價(jià)函數(shù) f(x)的一種啟發(fā)式搜索算法。 ?由 Nilsson提出 ?定理 1 對(duì)有限圖，如果從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t有路徑存在，則算法 A一定成功結(jié)束。 ?本原問題：直接可解的簡(jiǎn)單問題。 ?與節(jié)點(diǎn)：子節(jié)點(diǎn)之間是“與”關(guān)系的節(jié)點(diǎn)。如果初始節(jié)點(diǎn)也被標(biāo)記為可解節(jié)點(diǎn)，則搜索成功，結(jié)束。 ? OPEN表中那些具有不可解先輩的節(jié)點(diǎn)（因?yàn)槠湎容吂?jié)點(diǎn)已不可解，沒必要再考察這些節(jié)點(diǎn)），轉(zhuǎn)步 2。 ?解樹的代價(jià) (樹根的代價(jià) )：自下而上逐層計(jì)算 ?代價(jià)的計(jì)算方法：設(shè) g(x)表示節(jié)點(diǎn) x的代價(jià)， c(x,y)表示節(jié)點(diǎn) x到其子節(jié)點(diǎn) y的代價(jià)（即邊 xy的代價(jià)），則 ? 若 x是終止節(jié)點(diǎn)， g(x)=0； ? 若 x是或節(jié)點(diǎn)， g(x)=min{1 ? i ? n}{c(x,yi)+g(yi)} ? 若 x是與節(jié)點(diǎn)： 和代價(jià)法 ： g(x)=?{1 ? i ? n}{c(x,yi)+g(yi)} 最大代價(jià)法 ： g(x)=max{1 ? i ? n}{c(x,yi)+g(yi)} ? 對(duì)非終止端節(jié)點(diǎn) x， g(x)=∞ P113. 例 希望樹 ?定義啟發(fā)函數(shù)來估算子節(jié)點(diǎn)的代價(jià) ?節(jié)點(diǎn)擴(kuò)展后需重新計(jì)算 ?希望樹是在不斷變化的，但總是包含初始節(jié)點(diǎn) ?希望樹的定義 ? 初始節(jié)點(diǎn) S0在希望樹 T中 ? 如果節(jié)點(diǎn) x在希望樹 T中，則一定有 ?如果 x是具有子節(jié)點(diǎn) y1 ， y2 ， … ， yn的“或”節(jié)點(diǎn)，則具有 min{1 ? i ? n}{c(x,yi)+g(yi)}值的那個(gè)子節(jié)點(diǎn) yi也應(yīng)在 T中 ?如果 x是與節(jié)點(diǎn)，則它的全部子節(jié)點(diǎn)都應(yīng)在 T中 與或樹的有序搜索過程 ?是一個(gè)不斷選擇修正希望樹的過程 ?算法如下： ? 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中 ? 步 2 求出希望樹 T，即根據(jù)當(dāng)前搜索樹中節(jié)點(diǎn)的代價(jià) g求出以 S0為根的希望樹 T ? 步 3 依次把 OPEN表中 T的端節(jié)點(diǎn) N選出放入 CLOSED表中 ? 步 4 若節(jié)點(diǎn) N是終止節(jié)點(diǎn)，則做下列工作 ? N為可解節(jié)點(diǎn) ? T應(yīng)用可解標(biāo)記過程，把 N的先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)都標(biāo)記為可解節(jié)點(diǎn) ? S0能被標(biāo)記為可解節(jié)點(diǎn)，則 T就是最優(yōu)解樹，成功退出 ?，從 OPEN表中刪去具有可解先輩的所有節(jié)點(diǎn) 與或樹的有序搜索過程 ? 步 5 若 N不是終止節(jié)點(diǎn)且不可擴(kuò)展 (不可解 )，則做下列工作 ? N為不可解節(jié)點(diǎn) ? T應(yīng)用不可解標(biāo)記過程，把 N的先輩節(jié)點(diǎn)中的不可解節(jié)點(diǎn)都標(biāo)記為不可解節(jié)點(diǎn) ? S0也被標(biāo)記為不可解節(jié)點(diǎn)，則失敗退出 ?，從 OPEN表中刪去具有不可解先輩的所有節(jié)點(diǎn) ? 步 6 若 N不是終止節(jié)點(diǎn)，但它可擴(kuò)展，則做下列工作 ? N，產(chǎn)生 N的所有子節(jié)點(diǎn) ? OPEN表中，并為每一個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn) N的指針 ? g值及其先輩節(jié)點(diǎn)的 g值 ? 步 7 轉(zhuǎn)步 2 P115. 例 博弈樹搜索 ? “二人零和、全信息、非偶然”博弈： ? （ 1）、對(duì)壘的 A、 B雙方輪流采取行動(dòng)。不存在碰運(yùn)氣的偶然因素。 ? （ 3）、所有自己一方獲勝的終局都是本原問題，相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對(duì)方獲勝的終局都是不可解節(jié)點(diǎn)。 ? （ 3）為了計(jì)算得分，需要根據(jù)問題的特性信息定義一個(gè)估價(jià)函數(shù)，用來估算 當(dāng)前博弈樹端節(jié)點(diǎn) 的得分。這樣計(jì)算得的父節(jié)點(diǎn)的得分稱為 倒推值 。 ?對(duì)于一個(gè)或節(jié)點(diǎn) MAX，若能估計(jì)出其倒推值的下確界?，并且這個(gè) ?值不小于 MAX的父節(jié)點(diǎn)的估計(jì)倒推值的下確界 ?，即 ???，則就不必再擴(kuò)展該 MAX節(jié)點(diǎn)的其余子節(jié)點(diǎn)了。 例： 1） IF 動(dòng)物會(huì)飛 AND 會(huì)下蛋 THEN 該動(dòng)物是鳥。 ? 基于產(chǎn)生式的推理模式 ?假言推理、三段論推理 產(chǎn)生式系統(tǒng) ?產(chǎn)生式系統(tǒng)的組成 ? 產(chǎn)生式規(guī)則庫(kù) 。又稱控制系統(tǒng)，是一個(gè)程序模塊，負(fù)責(zé)產(chǎn)生式系統(tǒng)的運(yùn)行。 產(chǎn)生式規(guī)則庫(kù) 動(dòng)態(tài)數(shù)據(jù)庫(kù) 推理機(jī) 產(chǎn)生式系統(tǒng)的運(yùn)行過程 從規(guī)則庫(kù)中取一條規(guī)則，將。又稱綜合數(shù)據(jù)庫(kù)。規(guī)則庫(kù)中的知識(shí)要求完整、一致、表達(dá)準(zhǔn)確靈活、知識(shí)組織合理。 3）如果銀行存款利率下調(diào)，那么股票價(jià)格上漲。 第五章 產(chǎn)生式系統(tǒng) ? 1943年 ? 60年代開始，成為專家系統(tǒng)的最基本的結(jié)構(gòu) ?形式上很簡(jiǎn)單，但在一定意義上模仿了人類思考的過程 產(chǎn)生式規(guī)則 ?產(chǎn)生式規(guī)則 ? 產(chǎn)生式規(guī)則是表示知識(shí)的一種方式，一般形式為： P?Q，或 If P then Q，前件 ? 后件。 P120. 例 ??剪枝技術(shù) ?極小極大分析法的缺點(diǎn) ?對(duì)于一個(gè)與節(jié)點(diǎn) MIN，若能估計(jì)出其倒推值的上確界?，并且這個(gè) ?值不大于 MIN的父節(jié)點(diǎn)的估計(jì)倒推值的下確界 ?，即 ???，則就不必再擴(kuò)展該 MIN節(jié)點(diǎn)的其余子節(jié)點(diǎn)了。 ? （ 4）當(dāng)端節(jié)點(diǎn)的估計(jì)值計(jì)算出來后，再推算父節(jié)點(diǎn)的得分。然后為其中一方（例如 A）尋找一個(gè)最優(yōu)行動(dòng)方案。 ? （ 2）、在博弈樹中，“或”節(jié)點(diǎn)和“與”節(jié)點(diǎn)是 逐層交替出現(xiàn) 的。 ? （ 2）、對(duì)壘過程中，任何一方都了解當(dāng)前的格局和過去的歷史。 ?有序搜索 ：每次確定欲擴(kuò)展的節(jié)點(diǎn)時(shí)，先往前多看幾步。 ? 步 4 若 N不可擴(kuò)展，則做下列工作： ? N為不可解節(jié)點(diǎn)，然后由它的不可解返回推斷其先輩節(jié)點(diǎn)的可解性，并對(duì)其中的不可解節(jié)點(diǎn)進(jìn)行標(biāo)記。 與或圖搜索 ?搜索特點(diǎn)：邊擴(kuò)展邊判斷 ?可解判斷 ? 終止節(jié)點(diǎn)是可解節(jié)點(diǎn) ? 一個(gè)與節(jié)點(diǎn)可解，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全部可解 ? 一個(gè)或節(jié)點(diǎn)可解，只要其子節(jié)點(diǎn)中至少一個(gè)可解 ?不可解判斷 ? 非終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn) ? 一個(gè)與節(jié)點(diǎn)不可解，只要其子節(jié)點(diǎn)中至少一個(gè)不可解 ? 一個(gè)或節(jié)點(diǎn)可解，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全部不可解 ?盲目搜索 (窮舉 (廣度 /深度 )，盲目碰撞 )，啟發(fā)式搜索 與或樹搜索 ? 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中； ? 步 2 取 OPEN表中第一個(gè)節(jié)點(diǎn) N放入 CLOSED表中； ? 步 3 若節(jié)點(diǎn) N可擴(kuò)展，則做下列工作： ? N，將其所有子節(jié)點(diǎn)配上指向父節(jié)點(diǎn) N的指針后放入 OPEN表； ? 。 ?端節(jié)點(diǎn)：無子節(jié)點(diǎn)的節(jié)點(diǎn)。 ?定理 3 (可采納性定理 )：若存在從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t有路徑，則 A*必能找到最佳解結(jié)束。其中h*(x)是從節(jié)點(diǎn) x到目標(biāo)節(jié)點(diǎn)的最小代價(jià)。 ? 步 5 若 N不可擴(kuò)展，則轉(zhuǎn)步 2。 啟發(fā)式搜索的 A算法和 A*算法 ?估價(jià)函數(shù) ? f(x)=g(x)+h(x)。 (問題：優(yōu)秀個(gè)體的后代未必優(yōu)秀 ) 加權(quán)狀態(tài)圖搜索 ?加權(quán)狀態(tài)圖與代價(jià)樹 ? Eg: 交通圖 ? 加權(quán)狀態(tài)圖的搜索要增加權(quán)值的計(jì)算與傳播過程，并且要由權(quán)值來確定節(jié)點(diǎn)的擴(kuò)展順序。 ? Eg：八數(shù)碼問題 ?啟發(fā)函數(shù) ? 用來估計(jì)搜索樹上節(jié)點(diǎn) X與目標(biāo)節(jié)點(diǎn) Sg接近程度的函數(shù)，記為 h(x). 啟發(fā)式搜索算法 ? (1) 全局擇優(yōu)搜索算法： ? 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中，計(jì)算 h(S0)； ? 步 2 若 OPEN表為空，則搜索失敗，退出； ? 步 3 取 OPEN表中前面第一個(gè)節(jié)點(diǎn) N放入 CLOSED表中； ? 步 4 若目標(biāo)節(jié)點(diǎn) Sg =N，則搜索成功，結(jié)束 。 ?有界深度搜索算法 ? 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中，置 S0的深度 d(S0)=0； ? 步 2 若 OPEN表為空，則搜索失敗，退出； ? 步 3 取 OPEN表中前面第一個(gè)節(jié)點(diǎn) N放入 CLOSED表中； ? 步 4 若目標(biāo)節(jié)點(diǎn) Sg =N，則搜索成功，結(jié)束 。 ? 步 5 若 N不可擴(kuò)展，則轉(zhuǎn)步 2。 ? 步 6 擴(kuò)展 N，將其所有子節(jié)點(diǎn)配上指向 N的指針依次放入 OPEN表的 尾部 ，轉(zhuǎn)步 2。否則，以 CLOSED表新的末端節(jié)點(diǎn) Ne作為 N,即令 N= Ne ，轉(zhuǎn)步 4 ? 步 5 擴(kuò)展 N，選取一個(gè)未在 CLOSED表中出現(xiàn)的子節(jié)點(diǎn) N1放入 CLOSED表中，令 N=N1，轉(zhuǎn)步 3。 ? 步 4 若 N不可擴(kuò)展，則搜索失敗，退出。 ?按搜索范圍的擴(kuò)展順序不同 ? 廣度優(yōu)先搜索 ? 深度優(yōu)先搜索 搜索算法 ? CLOSED表和 OPEN表 ? 樹式搜索算法 ? 步 1 把初始節(jié)點(diǎn)放入 OPEN表； ? 步 2 檢查 OPEN表，若為空，則問題無解，退出； ? 步 3 移出 OPEN表中第一個(gè)節(jié)點(diǎn) N并放入 CLOSED表中，并編號(hào)為 n。問題求解過程可描述為一個(gè)有向圖，其中的 節(jié)點(diǎn)代表狀態(tài)， 邊 表示狀態(tài)轉(zhuǎn)換之間的算符。 ?應(yīng)用：結(jié)構(gòu)不良問題，無成熟算法；或有算法 ，但問題復(fù)雜，如博弈 ?圖：由節(jié)點(diǎn)和有向邊組成的網(wǎng)絡(luò) ?圖的分類： ? 或圖 (狀態(tài)圖、直接圖 ) ? 與或圖 狀態(tài)圖 ?狀態(tài)圖的概念 ? 迷宮問題 ? 八數(shù)碼難題 /華容道問題 ?以上問題的本質(zhì)：在某個(gè)有向圖中尋找目標(biāo)或路徑，該有向圖稱為 狀態(tài)空間圖 或 狀態(tài)圖 。 歸結(jié)策略 ? 歸結(jié)策略的類型 ? 簡(jiǎn)化性策略 ?思想：盡量簡(jiǎn)化子句和子句集，以減少和避免無效歸結(jié)。 ? 支持集策略的特點(diǎn)： ?支持集策略實(shí)際是一種 目標(biāo)制導(dǎo) 的 反向 推理。 ?解釋： C=P(x)替換后得 C=P(a)， D=P(a) ? Q(y) 歸結(jié)策略 ?使用刪除策略，例 1可簡(jiǎn)化為： （ 1） P?Q （ 7） ? P