【正文】 ，結(jié)束 。 ? 步 5 若 N的深度 d(N)=dm，或者 N無子節(jié)點(diǎn)，則轉(zhuǎn)步 2。 ? 步 6 擴(kuò)展 N，將其所有子節(jié)點(diǎn) Ni配上指向 N的返回指針后依次放入 OPEN表的前部，置 d(Ni)=d(N)+1，轉(zhuǎn)步 2。 啟發(fā)式搜索 ?問題的提出 ? 窮舉法的局限性 ? 組合爆炸：梵塔問題，博弈：國際象棋 10120，圍棋 10761 ?啟發(fā)性信息 ? （ 1）、用于擴(kuò)展節(jié)點(diǎn)的選擇的信息； ? （ 2）、用于生成節(jié)點(diǎn)的選擇的信息； ? （ 3）、用于刪除節(jié)點(diǎn)的選擇的信息。 ? Eg：八數(shù)碼問題 ?啟發(fā)函數(shù) ? 用來估計搜索樹上節(jié)點(diǎn) X與目標(biāo)節(jié)點(diǎn) Sg接近程度的函數(shù)，記為 h(x). 啟發(fā)式搜索算法 ? (1) 全局擇優(yōu)搜索算法： ? 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中，計算 h(S0)； ? 步 2 若 OPEN表為空，則搜索失敗，退出； ? 步 3 取 OPEN表中前面第一個節(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) x的函數(shù)值 h(x)，并將所有子節(jié)點(diǎn)配上指向 N的返回指針放入 OPEN表中，再對 OPEN表中的 所有子節(jié)點(diǎn) 按其函數(shù)值大小以升序排序，轉(zhuǎn)步 2。 ? Eg: 八數(shù)碼問題 P95 ? (2) 局部擇優(yōu)搜索 ? 擴(kuò)展節(jié)點(diǎn)后僅對 N的子節(jié)點(diǎn)按啟發(fā)函數(shù)值排序后放入 OPEN的首部。 (問題：優(yōu)秀個體的后代未必優(yōu)秀 ) 加權(quán)狀態(tài)圖搜索 ?加權(quán)狀態(tài)圖與代價樹 ? Eg: 交通圖 ? 加權(quán)狀態(tài)圖的搜索要增加權(quán)值的計算與傳播過程，并且要由權(quán)值來確定節(jié)點(diǎn)的擴(kuò)展順序。 ? 代價： g(xj)= g(xi)+c(xi, xj)。 g(S0)=0. ?分支界限法：相當(dāng)于啟發(fā)式搜索中的全局擇優(yōu)搜索，不過用代價函數(shù)代替啟發(fā)函數(shù)。 ?最近擇優(yōu)法：相當(dāng)于啟發(fā)式搜索中的局部擇優(yōu)搜索，不過用代價函數(shù)代替啟發(fā)函數(shù)。 啟發(fā)式搜索的 A算法和 A*算法 ?估價函數(shù) ? f(x)=g(x)+h(x)。 其中 g(x)是代價函數(shù)， h(x)是啟發(fā)函數(shù)。 或定義為： f(x)=d(x)+h(x)。 d(x)是 x的深度 ? g(x),h(x)對搜索的影響 ?最小代價搜索 ? A算法 ? 步 1 把附有 f(S0)的初始節(jié)點(diǎn) S0放入 OPEN表中； ? 步 2 若 OPEN表為空，則搜索失敗，退出； ? 步 3 取 OPEN表中前面第一個節(jié)點(diǎn) N放入 CLOSED表中； ? 步 4 若目標(biāo)節(jié)點(diǎn) Sg =N，則搜索成功，結(jié)束 。 ? 步 5 若 N不可擴(kuò)展，則轉(zhuǎn)步 2。 啟發(fā)式搜索的 A算法和 A*算法 ? 步 6 擴(kuò)展 N，計算每個子節(jié)點(diǎn) x的估價函數(shù)值 f(x)，并對這組子節(jié)點(diǎn)作如下處理： ?（ 1）考察是否有已在 OPEN表或 CLOSED表中存在的節(jié)點(diǎn)；若有，則再考察其中有無 N的先輩節(jié)點(diǎn)，若有則刪除之；對于其余節(jié)點(diǎn)，也刪除之，但由于它們又被第二次生成，因而需考慮是否修改已經(jīng)存在于 OPEN表或CLOSED表中的這些節(jié)點(diǎn)及其后裔的返回指針和 f(x)值，修改原則是“抄 f(x)值小的路走”； ?（ 2）對其余子節(jié)點(diǎn)配上指向 N的返回指針后放入 OPEN表中，并對 OPEN表按 f(x)值以升序排序，轉(zhuǎn)步 2。 ? 可以看出， A算法是樹式搜索算法加估價函數(shù) f(x)的一種啟發(fā)式搜索算法。 啟發(fā)式搜索的 A算法和 A*算法 ? A算法加上限制：對所有節(jié)點(diǎn) x均有 h(x)?h*(x)。其中h*(x)是從節(jié)點(diǎn) x到目標(biāo)節(jié)點(diǎn)的最小代價。 h(x)為啟發(fā)式函數(shù)。 ?由 Nilsson提出 ?定理 1 對有限圖，如果從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t有路徑存在，則算法 A一定成功結(jié)束。 ?定理 2 對無限圖，若從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t有路徑存在，則 A*一定成功結(jié)束。 ?定理 3 (可采納性定理 )：若存在從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t有路徑，則 A*必能找到最佳解結(jié)束。 狀態(tài)圖問題求解 ?問題的狀態(tài)圖表示 ? 狀態(tài)：節(jié)點(diǎn)；記錄、對象、 …… ? 規(guī)則：邊；數(shù)據(jù)對 (x,y)，條件語句 (if x …y…) ， …… ? 一個問題的狀態(tài)圖表示為一個三元組 (S,F,G) ? S:初始狀態(tài)集； G:目標(biāo)狀態(tài)集； F:狀態(tài)轉(zhuǎn)換規(guī)則集合 ?迷宮問題的狀態(tài)圖表示 P99 ?顯式狀態(tài)圖 ?八數(shù)碼問題的狀態(tài)圖表示 P100 ?隱式狀態(tài)圖 ? TSP問題 與或圖 ?與或圖的引入 ?本質(zhì)：復(fù)雜問題分解為簡單問題 ?與或樹 與或圖 ?狀態(tài)圖和與或圖的關(guān)系 目標(biāo) 目標(biāo) 初始節(jié)點(diǎn) 與或圖 ?解樹：問題的求解路徑構(gòu)成的樹。 ?本原問題：直接可解的簡單問題。 ?終止節(jié)點(diǎn)：本原問題對應(yīng)的節(jié)點(diǎn)。 ?端節(jié)點(diǎn)：無子節(jié)點(diǎn)的節(jié)點(diǎn)。終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，反之不成立。 ?與節(jié)點(diǎn)：子節(jié)點(diǎn)之間是“與”關(guān)系的節(jié)點(diǎn)。 ?或節(jié)點(diǎn)：子節(jié)點(diǎn)之間是“或”關(guān)系的節(jié)點(diǎn)。 與或圖搜索 ?搜索特點(diǎn)：邊擴(kuò)展邊判斷 ?可解判斷 ? 終止節(jié)點(diǎn)是可解節(jié)點(diǎn) ? 一個與節(jié)點(diǎn)可解，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全部可解 ? 一個或節(jié)點(diǎn)可解，只要其子節(jié)點(diǎn)中至少一個可解 ?不可解判斷 ? 非終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn) ? 一個與節(jié)點(diǎn)不可解，只要其子節(jié)點(diǎn)中至少一個不可解 ? 一個或節(jié)點(diǎn)可解，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全部不可解 ?盲目搜索 (窮舉 (廣度 /深度 )，盲目碰撞 )，啟發(fā)式搜索 與或樹搜索 ? 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中； ? 步 2 取 OPEN表中第一個節(jié)點(diǎn) N放入 CLOSED表中； ? 步 3 若節(jié)點(diǎn) N可擴(kuò)展，則做下列工作： ? N，將其所有子節(jié)點(diǎn)配上指向父節(jié)點(diǎn) N的指針后放入 OPEN表； ? 。若有，則標(biāo)記它們?yōu)榭山夤?jié)點(diǎn)，并將它們也放入 CLOSED表，然后由它們的可解 返回推斷 其先輩節(jié)點(diǎn)的可解性，并對其中的可解節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始節(jié)點(diǎn)也被標(biāo)記為可解節(jié)點(diǎn)，則搜索成功，結(jié)束。 ? OPEN表中那些具有可解先輩的節(jié)點(diǎn)（因?yàn)槠湎容吂?jié)點(diǎn)已經(jīng)可解，故已無考察節(jié)點(diǎn)的必要），轉(zhuǎn)步 2。 ? 步 4 若 N不可擴(kuò)展，則做下列工作： ? N為不可解節(jié)點(diǎn)，然后由它的不可解返回推斷其先輩節(jié)點(diǎn)的可解性，并對其中的不可解節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始節(jié)點(diǎn)也被標(biāo)記為不可解節(jié)點(diǎn)，則搜索失敗，退出。 ? OPEN表中那些具有不可解先輩的節(jié)點(diǎn)（因?yàn)槠湎容吂?jié)點(diǎn)已不可解，沒必要再考察這些節(jié)點(diǎn)），轉(zhuǎn)步 2。 P112. 例 啟發(fā)式與或樹搜索 ?最優(yōu)解樹 ：代價最小的解樹稱為最優(yōu)解樹。 ?有序搜索 ：每次確定欲擴(kuò)展的節(jié)點(diǎn)時，先往前多看幾步。計算一下擴(kuò)展這個節(jié)點(diǎn)可能要付出的代價，并選擇代價最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。 ?解樹的代價 (樹根的代價 )：自下而上逐層計算 ?代價的計算方法：設(shè) g(x)表示節(jié)點(diǎn) x的代價， c(x,y)表示節(jié)點(diǎn) x到其子節(jié)點(diǎn) y的代價（即邊 xy的代價），則 ? 若 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)： 和代價法 ： g(x)=?{1 ? i ? n}{c(x,yi)+g(yi)} 最大代價法 ： g(x)=max{1 ? i ? n}{c(x,yi)+g(yi)} ? 對非終止端節(jié)點(diǎn) x， g(x)=∞ P113. 例 希望樹 ?定義啟發(fā)函數(shù)來估算子節(jié)點(diǎn)的代價 ?節(jié)點(diǎn)擴(kuò)展后需重新計算 ?希望樹是在不斷變化的，但總是包含初始節(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)}值的那個子節(jié)點(diǎn) yi也應(yīng)在 T中 ?如果 x是與節(jié)點(diǎn)，則它的全部子節(jié)點(diǎn)都應(yīng)在 T中 與或樹的有序搜索過程 ?是一個不斷選擇修正希望樹的過程 ?算法如下： ? 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中 ? 步 2 求出希望樹 T，即根據(jù)當(dāng)前搜索樹中節(jié)點(diǎn)的代價 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表中，并為每一個子節(jié)點(diǎn)配置指向父節(jié)點(diǎn) N的指針 ? g值及其先輩節(jié)點(diǎn)的 g值 ? 步 7 轉(zhuǎn)步 2 P115. 例 博弈樹搜索 ? “二人零和、全信息、非偶然”博弈： ? （ 1）、對壘的 A、 B雙方輪流采取行動。結(jié)局有三種情況： A方勝， B方??； A方敗， B方勝；雙方平局。 ? （ 2）、對壘過程中，任何一方都了解當(dāng)前的格局和過去的歷史。 ? （ 3）、任何一方都要選取對自己最有利而對對方最不利的對策。不存在碰運(yùn)氣的偶然因素。 ? 博弈樹的概念 ? 描述博弈過程的與或樹 ? 博弈樹的特點(diǎn) ? （ 1）、博弈的初始格局是初始節(jié)點(diǎn)。 ? （ 2）、在博弈樹中，“或”節(jié)點(diǎn)和“與”節(jié)點(diǎn)是 逐層交替出現(xiàn) 的。自己一方擴(kuò)展的節(jié)點(diǎn)是“或”的關(guān)系，對方擴(kuò)展的節(jié)點(diǎn)之間是“與”的關(guān)系。 ? （ 3）、所有自己一方獲勝的終局都是本原問題，相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對方獲勝的終局都是不可解節(jié)點(diǎn)。 極小極大分析法 ? （ 1）設(shè)博弈的雙方中一方為 A，另一方為 B。然后為其中一方（例如 A）尋找一個最優(yōu)行動方案。 ? （ 2）為了找到當(dāng)前的最優(yōu)行動方案，需要考慮每一方案實(shí)施后對方可能采取的所有行動，并計算可能的得分。 ? （ 3）為了計算得分，需要根據(jù)問題的特性信息定義一個估價函數(shù)，用來估算 當(dāng)前博弈樹端節(jié)點(diǎn) 的得分。此得分值稱為 靜態(tài)估值 。 ? （ 4）當(dāng)端節(jié)點(diǎn)的估計值計算出來后，再推算父節(jié)點(diǎn)的得分。對“ 或 ”節(jié)點(diǎn)，選取其子節(jié)點(diǎn)中 最大 的得分作為父節(jié)點(diǎn)的得分；對“ 與 ”節(jié)點(diǎn)，取其子節(jié)點(diǎn)中 最小 的一個得分作為父節(jié)點(diǎn)的得分。這樣計算得的父節(jié)點(diǎn)的得分稱為 倒推值 。 ? （ 5）如果一個行動方案能獲得最大的倒推值，它就是當(dāng)前最好的行動方案。 P120. 例 ??剪枝技術(shù) ?極小極大分析法的缺點(diǎn) ?對于一個與節(jié)點(diǎn) MIN，若能估計出其倒推值的上確界?，并且這個 ?值不大于 MIN的父節(jié)點(diǎn)的估計倒推值的下確界 ?，即 ???，則就不必再擴(kuò)展該 MIN節(jié)點(diǎn)的其余子節(jié)點(diǎn)了。這一過程稱為 ?剪枝。 ?對于一個或節(jié)點(diǎn) MAX，若能估計出其倒推值的下確界?，并且這個 ?值不小于 MAX的父節(jié)點(diǎn)的估計倒推值的下確界 ?，即 ???，則就不必再擴(kuò)展該 MAX節(jié)點(diǎn)的其余子節(jié)點(diǎn)了。這一過程稱為 ?剪枝。 第五章 產(chǎn)生式系統(tǒng) ? 1943年 ? 60年代開始，成為專家系統(tǒng)的最基本的結(jié)構(gòu) ?形式上很簡單，但在一定意義上模仿了人類思考的過程 產(chǎn)生式規(guī)則 ?產(chǎn)生式規(guī)則 ? 產(chǎn)生式規(guī)則是表示知識的一種方式，一般形式為： P?Q，或 If P then Q，前件 ? 后件。 ? 產(chǎn)生式的含義是：如果前提 P被滿足，則可推出結(jié)論 Q或執(zhí)行 Q所規(guī)定的動作。 例： 1） IF 動物會飛 AND 會下蛋 THEN 該動物是鳥。 2）如果爐溫超過上限，則關(guān)閉閥門。 3）如果銀行存款利率下調(diào)，那么股票價格上漲。 ? 產(chǎn)生式規(guī)則與邏輯蘊(yùn)含式的區(qū)別與聯(lián)系 ?邏輯蘊(yùn)含式是產(chǎn)生式，反之則不然。 ? 基于產(chǎn)生式的推理模式 ?假言推理、三段論推理 產(chǎn)生式系統(tǒng) ?產(chǎn)生式系統(tǒng)的組成 ? 產(chǎn)生式規(guī)則庫 。用于描述相應(yīng)領(lǐng)域內(nèi)知識的產(chǎn)生式規(guī)則的集合。規(guī)則庫中的知識要求完整、一致、表達(dá)準(zhǔn)確靈活、知識組織合理。以某種動態(tài)數(shù)據(jù)結(jié)構(gòu)來組織； ? 推理機(jī) 。又稱控制系統(tǒng)，是一個程序模塊，負(fù)責(zé)產(chǎn)生式系統(tǒng)的運(yùn)行。如規(guī)則與事實(shí)的匹配、執(zhí)行規(guī)則、停止控制； ? 動態(tài)數(shù)據(jù)庫 。又稱綜合數(shù)據(jù)庫。動態(tài)數(shù)據(jù)結(jié)構(gòu)，存放初始事實(shí)、中間結(jié)果和最后結(jié)果。 產(chǎn)生式規(guī)則庫 動態(tài)數(shù)據(jù)庫 推理機(jī) 產(chǎn)生式系統(tǒng)的運(yùn)行過程 從規(guī)則庫中取一條