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