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