【正文】 搜索的不足，提高搜索效率。 思考 ： 試比較各種盲目搜索搜索方法的效率，找出影響算法效率的原因。 22 23 等代價搜索算法 （請同學(xué)們課后認(rèn)真閱讀本算法，指出與寬度優(yōu)先、深度優(yōu)先算法有何特別之處。 思考題 ：有界深度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的最短途徑嗎？ 20 定義 寬度優(yōu)先搜索可被推廣用來解決尋找從起始狀態(tài)至目標(biāo)狀態(tài)的具有最小代價的路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做等代價搜索算法。任何節(jié)點(diǎn)如果達(dá)到了深度界限，那么都將把它們作為沒有后繼節(jié)點(diǎn)處理。 15 特點(diǎn) 首先，擴(kuò)展最深的節(jié)點(diǎn)的結(jié)果使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點(diǎn)向下進(jìn)行下去；只有當(dāng)搜索到達(dá)一個沒有后裔的狀態(tài)時，它才考慮另一條替代的路徑。深度相等的節(jié)點(diǎn)可以任意排列。 寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的最短途徑；這棵搜索樹提供了所有存在的路徑 (如果沒有路徑存在，那么對有限圖來說，我們就說該法失敗退出；對于無限圖來說，則永遠(yuǎn)不會終止 )。 (6) 如果 n的任一個后繼節(jié)點(diǎn)是個目標(biāo)節(jié)點(diǎn)，則找到一個解答，成功退出；否則轉(zhuǎn)向第 (2)步。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第 (2)步。 (3) 把第一個節(jié)點(diǎn) (節(jié)點(diǎn) n)從 OPEN表移出，并把它放入 CLOSED的擴(kuò)展節(jié)點(diǎn)表中。 10 寬度優(yōu)先搜索算法 (1) 把起始節(jié)點(diǎn)放到 OPEN表中 (如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個解答 )。 8 定義 如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索 (breadthfirst search)。 教學(xué)方法：以實例強(qiáng)化內(nèi)容的學(xué)習(xí)，通過提問引導(dǎo)學(xué)生對三種方法的特點(diǎn)進(jìn)行比較。 教學(xué)重點(diǎn)：盲目搜索的特點(diǎn)，寬度優(yōu)先搜索。在失敗終止的情況下，從起始節(jié)點(diǎn)出發(fā)，一定達(dá)不到目標(biāo)節(jié)點(diǎn)。這時，能夠重現(xiàn)從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的這條成功路徑，其辦法是從目標(biāo)節(jié)點(diǎn)按指針向 S返回追溯。這種排序可以是任意的即盲目的 (屬于盲目搜索 )，也可以用以后要討論的各種啟發(fā)思想或其它準(zhǔn)則為依據(jù) (屬于啟發(fā)式搜索 )。 (9) GO LOOP。對已在CLOSED表上的每個 M成員，確定是否需要更改圖G中通向它的每個后裔節(jié)點(diǎn)的指針方向。把 M的這些成員加進(jìn) OPEN表。把 M的這些成員作為 n的后繼節(jié)點(diǎn)添入圖 G中。 (5) 若 n為一目標(biāo)節(jié)點(diǎn)，則有解并成功退出，此解是追蹤圖 G中沿著指針從 n到 S這條路徑而得到的 (指針將在第 7步中設(shè)置 )。 (4) 選擇 OPEN表上的第一個節(jié)點(diǎn)，把它從OPEN表移出并放進(jìn) CLOSED表中。 (2) 建立一個叫做 CLOSED的已擴(kuò)展節(jié)點(diǎn)表，其初始為空表。研究圖搜索的一般策略，能夠給出圖搜索過程的一般步驟。初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別代表初始數(shù)據(jù)庫和滿足終止條件的數(shù)據(jù)庫。第三章 搜索推理技術(shù) 教學(xué)內(nèi)容 ? 早期搜索推理技術(shù)，如圖搜索策略和消解原理； ? 高級搜索推理技術(shù)，如規(guī)則演繹系統(tǒng)、產(chǎn)生式系統(tǒng)、系統(tǒng)組織技術(shù)、不確定性推理和非單調(diào)推理。 1 圖搜索策略 圖搜索策略的定義 圖搜索策略可看作一種在圖中尋找路徑的方法。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價于求得圖中的一條路徑問題。 2 圖搜索算法中的幾個重要名詞術(shù)語 （ 1） OPEN表與 CLOSE表 （ 2）搜索圖與搜索樹 狀態(tài)節(jié)點(diǎn) 父節(jié)點(diǎn) 狀態(tài)節(jié)點(diǎn) 父節(jié)點(diǎn) 編號 OPEN表 CLOSE表 3 4 圖搜索 (GRAPHSEARCH)的一般過程 (1) 建立一個只含有起始節(jié)點(diǎn) S的搜索圖 G，把 S放到一個叫做 OPEN的未擴(kuò)展節(jié)點(diǎn)表中。 (3) LOOP：若 OPEN表是空表，則失敗退出。稱此節(jié)點(diǎn)為節(jié)點(diǎn) n。 5 (6) 擴(kuò)展節(jié)點(diǎn) n，同時生成不是 n的祖先的那些后繼節(jié)點(diǎn)的集合 M。 (7) 對那些未曾在 G中出現(xiàn)過的 (既未曾在OPEN表上或 CLOSED表上出現(xiàn)過的 )M成員設(shè)置一個通向 n的指針。對已經(jīng)在 OPEN或 CLOSED表上的每一個 M成員，確定是否需要更改通到 n的指針方向。 (8) 按某一任意方式或按某個探試值，重排 OPEN表。 6 圖搜索方法分析： 圖搜索過程的第 8步對 OPEN表上的節(jié)點(diǎn)進(jìn)行排序，以便能夠從中選出一個“最好”的節(jié)點(diǎn)作為第 4步擴(kuò)展用。每當(dāng)被選作擴(kuò)展的節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)時，這一過程就宣告成功結(jié)束。當(dāng)搜索樹不再剩有未被擴(kuò)展的端節(jié)點(diǎn)時，過程就以失敗告終(某些節(jié)點(diǎn)最終可能沒有后繼節(jié)點(diǎn)，所以 OPEN表可能最后變成空表 )。 7 教學(xué)內(nèi)容：介紹三種盲目搜索方法，即寬度優(yōu)先搜索、深度優(yōu)先搜索和等代價搜索。 教學(xué)難點(diǎn)：等代價搜索中代價的概念。 教學(xué)要求：掌握盲目搜索的特點(diǎn)，比較三種盲目搜索方法的優(yōu)缺點(diǎn)。 9 特點(diǎn) 這種搜索是逐層進(jìn)行的；在對下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。 (2) 如果 OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。 (4) 擴(kuò)展節(jié)點(diǎn) n。 (5) 把 n的所有后繼節(jié)點(diǎn)放到 OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到 n的指針。 11 寬度優(yōu)先搜索方法分析： 寬度優(yōu)先搜索是圖搜索一般過程的特殊情況，將圖搜索一般過程中的第 8步具體化為本算法中的第 6步，這實際是將 OPEN表作為“先進(jìn)先出”的隊列進(jìn)行操作。 12 例：把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時所生成的搜索樹，這個問題就是要把初始棋局變?yōu)槿缦履繕?biāo)棋局的問題： 13 14 定義 在此搜索中，首先擴(kuò)展最新產(chǎn)生的 (即最深的 )節(jié)點(diǎn)。 這種盲目 (無信息 )搜索叫做深度優(yōu)先搜索 (depthfirst search)。 16 17 深度界限 為了避免考慮太長的路徑 (防止搜索過程沿著無益的路徑擴(kuò)展下去 )，往往給出一個節(jié)點(diǎn)擴(kuò)展的最大深度界限。 18 19 含有深度界限的深度優(yōu)先搜索算法 請同學(xué)們課后自學(xué)，并回答課后思考題。 21 等代價搜索中的幾個記號 起始節(jié)點(diǎn)記為 S； 從節(jié)點(diǎn) i到它的后繼節(jié)點(diǎn) j的連接弧線代價記為 c(i， j)； 從起始節(jié)點(diǎn) S到任一節(jié)點(diǎn) i的路徑代價記為 g(i)。） 24 等代價搜索方法分析 如果所有的連接弧線具有相等的代價，那么等代價算法就簡化為寬度優(yōu)先搜索算法。 25 啟發(fā)式搜索 教學(xué)內(nèi)容：啟發(fā)式搜索策略概述和有序搜索。 教學(xué)重點(diǎn)：啟發(fā)式搜索策略、啟發(fā)信息和有序搜索。 教學(xué)方法：通過實例加深對原理的理解，鼓勵同學(xué)擴(kuò)大閱讀范圍。 26 為什么需要啟發(fā)式搜索 盲目搜索效率低，耗費(fèi)過多的計算空間與時間，這是組合爆炸的一種表現(xiàn)形式。利用啟發(fā)信息的搜索方法叫做啟發(fā)式搜索方法。一個比較靈活 (但代價也較大 )的利用啟發(fā)信息的方法是應(yīng)用某些準(zhǔn)則來重新排列每一步 OPEN表中所有節(jié)點(diǎn)的順序。應(yīng)用這種排序過程，需要某些估算節(jié)點(diǎn)“希望”的量度，這種量度叫做估價函數(shù) (evalution function)。 f(n)—— 表示節(jié)點(diǎn) n的估價函數(shù)值 建立估價函數(shù)的一般方法：試圖確定一個處在最佳路徑上的節(jié)點(diǎn)的概率；提出任意節(jié)點(diǎn)與目標(biāo)集之間的距離量度或差別量度；或者在棋盤式的博弈和難題中根據(jù)棋局的某些特點(diǎn)來決定棋局的得分?jǐn)?shù)。 30 有序搜索 定義 用估價函數(shù) f來排列 GRAPHSEARCH第 8步中OPEN表上的節(jié)點(diǎn)。這種搜索方法叫做有序搜索(ordered search)或最佳優(yōu)先搜索 (bestfirst search)，而其算法就叫做有序搜索算法或最佳優(yōu)先算法。估價函數(shù) f是這樣確定的：一個節(jié)點(diǎn)的希望程序越大，其 f值就越小。 31 實質(zhì) 選擇 OPEN表上具有最小 f值的節(jié)點(diǎn)作為下一個要擴(kuò)展的節(jié)點(diǎn)，即總是選擇最有希望的節(jié)點(diǎn)作為下一個要擴(kuò)展的節(jié)點(diǎn)。 (2) 如果 OPEN是個空表，則失敗退出，無解。結(jié)果有幾個節(jié)點(diǎn)合格，當(dāng)其中有一個為目標(biāo)節(jié)點(diǎn)時，則選擇此目標(biāo)節(jié)點(diǎn)，否則就選擇其中任一個節(jié)點(diǎn)作為節(jié)點(diǎn) i。 (5) 如果