第二章2 啟發(fā)式搜索

1、問(wèn)題求解的基本方法啟發(fā)式搜索 2盲目搜索 3盲目搜索算法的缺點(diǎn)：盲目應(yīng)對(duì)之道：應(yīng)對(duì)之道：引入與應(yīng)用領(lǐng)域相關(guān)的啟發(fā)式知識(shí)來(lái)指導(dǎo)引入與應(yīng)用領(lǐng)域相關(guān)的啟發(fā)式知識(shí)來(lái)指導(dǎo)OPEN表中節(jié)點(diǎn)的排序表中節(jié)點(diǎn)的排序 4 局部排序局部排序-這是對(duì)深度優(yōu)先法的改進(jìn)，僅這是對(duì)深度優(yōu)先法的改進(jìn)，僅對(duì)新擴(kuò)展出來(lái)的子節(jié)點(diǎn)排序，使這些節(jié)點(diǎn)中對(duì)新擴(kuò)展出來(lái)的子節(jié)點(diǎn)排序，使這些節(jié)點(diǎn)中最有希望者能優(yōu)先取出考察和擴(kuò)展最有希望者能優(yōu)先取出考察和擴(kuò)展 全局排序全局排序-對(duì)對(duì)OPEN表中的所有節(jié)點(diǎn)排表中的所有節(jié)點(diǎn)排序，使最有希望的節(jié)點(diǎn)排在表首序，使最有希望的節(jié)點(diǎn)排在表首 5啟發(fā)式搜索啟發(fā)式搜索 概念：在搜索過(guò)程中，引入啟發(fā)式知識(shí)減少搜索的盲

2、概念：在搜索過(guò)程中，引入啟發(fā)式知識(shí)減少搜索的盲目性，提高搜索的效率，稱之為啟發(fā)式搜索目性，提高搜索的效率，稱之為啟發(fā)式搜索啟發(fā)式知識(shí)對(duì)搜索的作用：?jiǎn)l(fā)式知識(shí)對(duì)搜索的作用： 選擇下一個(gè)要被擴(kuò)展的節(jié)點(diǎn)，對(duì)選擇下一個(gè)要被擴(kuò)展的節(jié)點(diǎn)，對(duì)OPEN表進(jìn)行排序表進(jìn)行排序 在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，僅僅有選擇性的生成部分有用的節(jié)在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，僅僅有選擇性的生成部分有用的節(jié)點(diǎn)點(diǎn) 修剪掉某些估計(jì)不可能導(dǎo)致成功的子節(jié)點(diǎn)修剪掉某些估計(jì)不可能導(dǎo)致成功的子節(jié)點(diǎn) 6啟發(fā)式搜索啟發(fā)式搜索-算法算法A應(yīng)用評(píng)價(jià)函數(shù)來(lái)實(shí)現(xiàn)啟發(fā)式搜索的典型是算法應(yīng)用評(píng)價(jià)函數(shù)來(lái)實(shí)現(xiàn)啟發(fā)式搜索的典型是算法A ，評(píng)，評(píng)價(jià)函數(shù)價(jià)函數(shù)f(n)： f(n)= g(

3、n) + h(n)n-搜索圖中的某個(gè)當(dāng)前被擴(kuò)展的節(jié)點(diǎn)；搜索圖中的某個(gè)當(dāng)前被擴(kuò)展的節(jié)點(diǎn)；f(n)-從初始狀態(tài)節(jié)點(diǎn)從初始狀態(tài)節(jié)點(diǎn)s, 經(jīng)由節(jié)點(diǎn)經(jīng)由節(jié)點(diǎn)n到達(dá)目標(biāo)狀態(tài)節(jié)點(diǎn)到達(dá)目標(biāo)狀態(tài)節(jié)點(diǎn)n ng，估計(jì)的最小路徑代價(jià)，估計(jì)的最小路徑代價(jià)g(n)-從從s到到n ,估計(jì)的最小路徑代價(jià)；估計(jì)的最小路徑代價(jià)；h(n)-從從n到到ng,估計(jì)的最小路徑代價(jià)；估計(jì)的最小路徑代價(jià)； 7g(n)是已知的h(n)是未知的，需要采用啟發(fā)式函數(shù)來(lái)估算，稱為啟發(fā)式函數(shù) 8算法算法A搜索算法搜索算法A的一般過(guò)程：的一般過(guò)程：1） G := s； 2） OPEN := (s), CLOSE := ()； 3） 若若OPEN是空表，

4、則算法以失敗結(jié)束；是空表，則算法以失敗結(jié)束； 4） n := MOVE-FIRST(OPEN)；5） 若若n是目標(biāo)狀態(tài)節(jié)點(diǎn)，則搜索成功結(jié)束，并給出解答路是目標(biāo)狀態(tài)節(jié)點(diǎn)，則搜索成功結(jié)束，并給出解答路徑；徑；6） 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n,將非節(jié)點(diǎn)將非節(jié)點(diǎn)n祖先的子節(jié)點(diǎn)置于子節(jié)點(diǎn)集合祖先的子節(jié)點(diǎn)置于子節(jié)點(diǎn)集合SNS中，中， 并插入搜索圖并插入搜索圖G中，對(duì)于中，對(duì)于SNS中每個(gè)子節(jié)點(diǎn)中每個(gè)子節(jié)點(diǎn)n ni,計(jì)算計(jì)算 f(n,n ni) = g(n,ni) + h(ni); 97） 標(biāo)記和修改指針標(biāo)記和修改指針 把把SNS中的子節(jié)點(diǎn)分為三類（同一般圖搜索算法）中的子節(jié)點(diǎn)分為三類（同一般圖搜索算法） 加第加第

5、1類子節(jié)點(diǎn)于類子節(jié)點(diǎn)于OPEN表（同一般圖搜索算法）表（同一般圖搜索算法） 比較第比較第2類子節(jié)點(diǎn)類子節(jié)點(diǎn)ni經(jīng)由新、老父節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值經(jīng)由新、老父節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值f(n,ni)、f(ni);若若f(n,ni) f(ni)點(diǎn)點(diǎn),則令則令f(ni) = f(n,ni),并移動(dòng)子節(jié)點(diǎn)指并移動(dòng)子節(jié)點(diǎn)指向老父節(jié)點(diǎn)的指針，改為指向新父節(jié)點(diǎn)向老父節(jié)點(diǎn)的指針，改為指向新父節(jié)點(diǎn) 對(duì)第對(duì)第3類子節(jié)點(diǎn)作與第類子節(jié)點(diǎn)作與第2類同樣的處理，并把這些子節(jié)點(diǎn)從類同樣的處理，并把這些子節(jié)點(diǎn)從CLOSE表中移出，重新加入表中移出，重新加入OPEN表。表。8）按）按f值從小到大排序值從小到大排序OPEN表中的節(jié)點(diǎn)表中的節(jié)點(diǎn)

6、9) 返回語(yǔ)句返回語(yǔ)句3）；）； 10啟發(fā)式搜索算法啟發(fā)式搜索算法A結(jié)論結(jié)論按按f(n)排序排序OPEN表中的節(jié)點(diǎn)表中的節(jié)點(diǎn) f(n)值最小者排在首位，優(yōu)先加以擴(kuò)展值最小者排在首位，優(yōu)先加以擴(kuò)展 體現(xiàn)了最佳優(yōu)先體現(xiàn)了最佳優(yōu)先(best-first)搜索策略的思想搜索策略的思想 11算法算法A舉例：舉例：8數(shù)碼游戲數(shù)碼游戲f(n) = g(n) + h(n)g(n)=d(n)-當(dāng)前被考察和擴(kuò)展的節(jié)點(diǎn)當(dāng)前被考察和擴(kuò)展的節(jié)點(diǎn)n在搜索圖中的在搜索圖中的節(jié)點(diǎn)深度節(jié)點(diǎn)深度 h(n)=w(n) -節(jié)點(diǎn)節(jié)點(diǎn)n與目標(biāo)狀態(tài)節(jié)點(diǎn)與目標(biāo)狀態(tài)節(jié)點(diǎn)n ng相比較，錯(cuò)位的相比較，錯(cuò)位的棋牌個(gè)數(shù)棋牌個(gè)數(shù) 12初始節(jié)點(diǎn)：初始節(jié)

7、點(diǎn)： f(n) = 0 + 4 = 4 13 14 二二 實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵因素實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵因素（1）搜索算法的可采納性）搜索算法的可采納性(Admissibility) 在搜索圖存在從初始狀態(tài)節(jié)點(diǎn)到目標(biāo)狀態(tài)節(jié)點(diǎn)在搜索圖存在從初始狀態(tài)節(jié)點(diǎn)到目標(biāo)狀態(tài)節(jié)點(diǎn)解答路徑的情況下，若一個(gè)搜索法總能找到解答路徑的情況下，若一個(gè)搜索法總能找到最短最短（代價(jià)最?。┑慕獯鹇窂?，則稱算法具有可采納性（代價(jià)最小）的解答路徑，則稱算法具有可采納性 寬度優(yōu)先的搜索算法就是可采納的寬度優(yōu)先的搜索算法就是可采納的 15引入評(píng)價(jià)函數(shù)引入評(píng)價(jià)函數(shù)f f* *: f f* *(n)=g(n)=g * *(n)+h(n)+

8、h * *(n)(n) f f*(n)(n)、g g*(n)(n)、h h*(n)(n)分別指示當(dāng)經(jīng)由節(jié)點(diǎn)分別指示當(dāng)經(jīng)由節(jié)點(diǎn)n的的最短最短（代價(jià)最?。┙獯鹇窂秸业綍r(shí)（代價(jià)最?。┙獯鹇窂秸业綍r(shí)實(shí)際的實(shí)際的路經(jīng)代價(jià)路經(jīng)代價(jià)（長(zhǎng)度）、該路徑前段（自初始狀態(tài)節(jié)點(diǎn)到節(jié)點(diǎn)（長(zhǎng)度）、該路徑前段（自初始狀態(tài)節(jié)點(diǎn)到節(jié)點(diǎn)n）代價(jià)和后段（自節(jié)點(diǎn)代價(jià)和后段（自節(jié)點(diǎn)n到目標(biāo)狀態(tài)節(jié)點(diǎn)）代價(jià)。到目標(biāo)狀態(tài)節(jié)點(diǎn)）代價(jià)。 將評(píng)價(jià)函數(shù)將評(píng)價(jià)函數(shù)f與與f f*相比較，實(shí)際上，相比較，實(shí)際上，f(n)f(n)、g(n)和和h(n)分別是分別是f f*(n)、g g*(n)(n)和和h h*(n)(n)的近似值。的近似值。 在理想的情況

9、下，設(shè)計(jì)評(píng)價(jià)函數(shù)在理想的情況下，設(shè)計(jì)評(píng)價(jià)函數(shù)f時(shí)可以讓時(shí)可以讓g(n)g(n) = g g*(n)(n),h(n) = h h*(n)(n) 16如何挖掘貼切的啟發(fā)式知識(shí)如何挖掘貼切的啟發(fā)式知識(shí)(h(n)是設(shè)計(jì)評(píng)價(jià)函數(shù)乃是設(shè)計(jì)評(píng)價(jià)函數(shù)乃至算法至算法A的關(guān)鍵的關(guān)鍵 在前述的八數(shù)碼游戲中，在前述的八數(shù)碼游戲中，h(n)采用了采用了w(n)現(xiàn)在采用現(xiàn)在采用p(n)-節(jié)節(jié)點(diǎn)點(diǎn)n與目標(biāo)狀態(tài)節(jié)點(diǎn)相比較，每與目標(biāo)狀態(tài)節(jié)點(diǎn)相比較，每個(gè)錯(cuò)位棋牌在假設(shè)不受阻攔的情況下，移動(dòng)到目標(biāo)個(gè)錯(cuò)位棋牌在假設(shè)不受阻攔的情況下，移動(dòng)到目標(biāo)狀態(tài)相應(yīng)位置所需走步（移動(dòng)次數(shù)）的總和狀態(tài)相應(yīng)位置所需走步（移動(dòng)次數(shù)）的總和 17 18可以

10、證明，若確保對(duì)于搜索圖中的節(jié)點(diǎn)可以證明，若確保對(duì)于搜索圖中的節(jié)點(diǎn)n n，總是，總是有有h(n) h(n) h h* * (n), (n), 則算法則算法A A具有可采納性具有可采納性即總能搜索到最短（代價(jià)最小）的解答路徑即總能搜索到最短（代價(jià)最?。┑慕獯鹇窂轿覀兎Q滿足我們稱滿足h(n) h(n) h h* * (n) (n)的算法的算法A A為為A A* *寬度優(yōu)先算法，是一種特殊的寬度優(yōu)先算法，是一種特殊的A*算法算法h(n) 0 19實(shí)例實(shí)例傳教士和野人問(wèn)題傳教士和野人問(wèn)題N=5,K h(n) h h* * (n), (n),則則h(n)h(n)過(guò)強(qiáng)，使算法過(guò)強(qiáng)，使算法A A失去可采納失去

11、可采納性，從而不能確保找到最短解答路徑性，從而不能確保找到最短解答路徑設(shè)計(jì)接近、又總是設(shè)計(jì)接近、又總是 h h* * (n) (n)的的h(n)h(n)成為應(yīng)用成為應(yīng)用A A* *算法搜索算法搜索問(wèn)題解答的關(guān)鍵，以壓縮搜索圖，提高搜索效率問(wèn)題解答的關(guān)鍵，以壓縮搜索圖，提高搜索效率 23(3) (3) 設(shè)計(jì)設(shè)計(jì)h(n)h(n)的實(shí)用考慮的實(shí)用考慮f(n) = g(n) + h(n)使用評(píng)價(jià)函數(shù)使用評(píng)價(jià)函數(shù)f(n) = g(n) + wh(n)f(n) = g(n) + wh(n)w w用作加權(quán)用作加權(quán) 在搜索圖的淺層（上部），可讓在搜索圖的淺層（上部），可讓w w取較大值，以使取較大值，以使g(

12、n)g(n)所占比例很小，從而突出啟發(fā)式函數(shù)的作用，加速向縱深所占比例很小，從而突出啟發(fā)式函數(shù)的作用，加速向縱深方向搜索；一旦搜索到較深的層次，又讓方向搜索；一旦搜索到較深的層次，又讓w w取較小值，以取較小值，以使使g(n)g(n)所占比例很大，并確保所占比例很大，并確保wh(n)wh(n)h h* * (n), (n),從而引導(dǎo)搜從而引導(dǎo)搜索向橫廣方向發(fā)展，尋找到較短的解答路徑。索向橫廣方向發(fā)展，尋找到較短的解答路徑。 24三三 回溯策略和回溯策略和 爬山法爬山法 在在g(n)0的情況下，若限制只用評(píng)價(jià)函數(shù)的情況下，若限制只用評(píng)價(jià)函數(shù) f(n)= h(n)去去排序新擴(kuò)展出來(lái)的子節(jié)點(diǎn)排序新擴(kuò)

13、展出來(lái)的子節(jié)點(diǎn)，即局部，即局部排序，就可實(shí)現(xiàn)較為簡(jiǎn)單的搜索策略：回溯策排序，就可實(shí)現(xiàn)較為簡(jiǎn)單的搜索策略：回溯策略和爬山法略和爬山法 爬山法適用于能逐步求精的問(wèn)題爬山法適用于能逐步求精的問(wèn)題 25（1）爬山法爬山法 爬山法實(shí)際上就是求函數(shù)極大值問(wèn)題，不過(guò)這爬山法實(shí)際上就是求函數(shù)極大值問(wèn)題，不過(guò)這里不是用數(shù)值解法，而是依賴于啟發(fā)式知識(shí)，試?yán)锊皇怯脭?shù)值解法，而是依賴于啟發(fā)式知識(shí)，試探性地逐步向頂峰逼近（廣義地，逐步求精），探性地逐步向頂峰逼近（廣義地，逐步求精），直到登上頂峰直到登上頂峰 在爬山法中，限制只能向山頂爬去，即向目標(biāo)在爬山法中，限制只能向山頂爬去，即向目標(biāo)狀態(tài)逼近，不準(zhǔn)后退，從而簡(jiǎn)化了搜

14、索算法；即狀態(tài)逼近，不準(zhǔn)后退，從而簡(jiǎn)化了搜索算法；即不需設(shè)置不需設(shè)置OPEN和和CLOSE表，因?yàn)闆](méi)有必要保存表，因?yàn)闆](méi)有必要保存任何待擴(kuò)展節(jié)點(diǎn)任何待擴(kuò)展節(jié)點(diǎn) 26爬山法對(duì)于爬山法對(duì)于單一極值問(wèn)題單一極值問(wèn)題（登單一山峰）十分（登單一山峰）十分有效而又簡(jiǎn)便，但對(duì)于具有多極值的問(wèn)題就無(wú)有效而又簡(jiǎn)便，但對(duì)于具有多極值的問(wèn)題就無(wú)能為力了，因?yàn)楹芸赡軙?huì)因錯(cuò)登上次高峰而失能為力了，因?yàn)楹芸赡軙?huì)因錯(cuò)登上次高峰而失敗敗-不能到達(dá)最高峰不能到達(dá)最高峰 27 28（2）回溯策略）回溯策略 保存了每次擴(kuò)展出的子節(jié)點(diǎn)，并按保存了每次擴(kuò)展出的子節(jié)點(diǎn)，并按h(n)值從值從小到大排列小到大排列 相當(dāng)于爬山的過(guò)程中記住了途

15、經(jīng)的岔路口，相當(dāng)于爬山的過(guò)程中記住了途經(jīng)的岔路口，只要當(dāng)前路徑搜索失敗就回溯（退回）到時(shí)序上只要當(dāng)前路徑搜索失敗就回溯（退回）到時(shí)序上最近的岔路口，向另一路徑方向搜索最近的岔路口，向另一路徑方向搜索 可以確保最后到達(dá)最高峰（即目標(biāo)狀態(tài)）?？梢源_保最后到達(dá)最高峰（即目標(biāo)狀態(tài)）。 29令令PATH、SNL、n、n 為局部變量：為局部變量： P A T H - - 節(jié) 點(diǎn) 列 表 ， 指 示 解 答 路 徑 ；節(jié) 點(diǎn) 列 表 ， 指 示 解 答 路 徑 ； S N L - - 當(dāng) 前 節(jié) 點(diǎn) 擴(kuò) 展 出 的 子 節(jié) 點(diǎn) 列 表 ；當(dāng) 前 節(jié) 點(diǎn) 擴(kuò) 展 出 的 子 節(jié) 點(diǎn) 列 表 ； MOVE-FI

16、RST(SNL)-把把SNL表首的節(jié)點(diǎn)移出，作為下一次表首的節(jié)點(diǎn)移出，作為下一次要加以擴(kuò)展的節(jié)點(diǎn)；要加以擴(kuò)展的節(jié)點(diǎn)； n、 n -分別指示當(dāng)前考察和下一次考察的節(jié)點(diǎn)。分別指示當(dāng)前考察和下一次考察的節(jié)點(diǎn)。該遞歸過(guò)程的算法就取名為該遞歸過(guò)程的算法就取名為BACKTRACK(n),參數(shù)參數(shù)n為當(dāng)前被為當(dāng)前被擴(kuò)展的節(jié)點(diǎn)，算法的初次調(diào)用式是擴(kuò)展的節(jié)點(diǎn)，算法的初次調(diào)用式是BACKTRACK(s),s即為初即為初始狀態(tài)節(jié)點(diǎn)。始狀態(tài)節(jié)點(diǎn)。 30算法的步驟如下：算法的步驟如下：（1） 若若n是目標(biāo)狀態(tài)節(jié)點(diǎn)，則算法的本次調(diào)用成功結(jié)束，是目標(biāo)狀態(tài)節(jié)點(diǎn)，則算法的本次調(diào)用成功結(jié)束，返回空表；返回空表；（2） 若若n是失

17、敗狀態(tài)，則算法的本次調(diào)用失敗結(jié)束，返回是失敗狀態(tài)，則算法的本次調(diào)用失敗結(jié)束，返回FAIL；（3） 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，將生成的子節(jié)點(diǎn)置于列表，將生成的子節(jié)點(diǎn)置于列表SNL，并按評(píng)，并按評(píng)價(jià)函數(shù)價(jià)函數(shù)f(k) = h(k)的值從小到大排序（的值從小到大排序（k指示子節(jié)點(diǎn)）；指示子節(jié)點(diǎn)）；(4） 若若SNL為空，則算法的本次調(diào)用失敗結(jié)束，返回為空，則算法的本次調(diào)用失敗結(jié)束，返回FAIL；（5） n= MOVE-FIRST(SNL)；（6） PATH = BACKTRACK(n)；（7）若）若PATH =FAIL, 返回到語(yǔ)句（返回到語(yǔ)句（4）；）；（8） 將將n加到加到PATH表首，算法的本次調(diào)用

18、成功結(jié)束，返表首，算法的本次調(diào)用成功結(jié)束，返回回PATH。 31失敗狀態(tài)通常意指三種情況：失敗狀態(tài)通常意指三種情況：（1）不合法狀態(tài)（如傳教士和野人問(wèn)題中所述的那）不合法狀態(tài)（如傳教士和野人問(wèn)題中所述的那樣）樣）（2）舊狀態(tài)重現(xiàn)（如八數(shù)碼游戲中某一棋盤布局的）舊狀態(tài)重現(xiàn)（如八數(shù)碼游戲中某一棋盤布局的重現(xiàn)，會(huì)導(dǎo)致搜索算法死循環(huán)）重現(xiàn)，會(huì)導(dǎo)致搜索算法死循環(huán)）（3）狀態(tài)節(jié)點(diǎn)深度超過(guò)預(yù)定限度（例如八數(shù)碼游戲）狀態(tài)節(jié)點(diǎn)深度超過(guò)預(yù)定限度（例如八數(shù)碼游戲中，指示解答路徑不超過(guò)中，指示解答路徑不超過(guò)6步）。步）。 32 皇后問(wèn)題 33 34四四 狀態(tài)空間抽象和生成狀態(tài)空間抽象和生成-測(cè)試法測(cè)試法 狀態(tài)空間抽象

19、策略適合尋找令人滿意的解答狀態(tài)空間抽象策略適合尋找令人滿意的解答 生成生成-測(cè)試法用于最優(yōu)化問(wèn)題測(cè)試法用于最優(yōu)化問(wèn)題 35（1）狀態(tài)空間抽象策略）狀態(tài)空間抽象策略 狀態(tài)空間抽象是減少搜索量的重要技術(shù)。常用的方式是狀態(tài)空間抽象是減少搜索量的重要技術(shù)。常用的方式是將狀態(tài)空間按子問(wèn)題進(jìn)行劃分，子問(wèn)題構(gòu)成抽象空間。顯然，將狀態(tài)空間按子問(wèn)題進(jìn)行劃分，子問(wèn)題構(gòu)成抽象空間。顯然，抽象空間中的一個(gè)搜索與步抽象空間中的一個(gè)搜索與步(一個(gè)子問(wèn)題一個(gè)子問(wèn)題)對(duì)應(yīng)于實(shí)際狀態(tài)空對(duì)應(yīng)于實(shí)際狀態(tài)空間中的許多步，因而抽象空間小得多，使搜索大幅度加快間中的許多步，因而抽象空間小得多，使搜索大幅度加快 36（2）生成）生成-測(cè)試

20、法測(cè)試法 搜索過(guò)程由兩個(gè)部件合作完成：可能解的生成器搜索過(guò)程由兩個(gè)部件合作完成：可能解的生成器和修剪不正確解答的測(cè)試器。和修剪不正確解答的測(cè)試器。 在搜索過(guò)程中，生成器和測(cè)試器的工作往往需交在搜索過(guò)程中，生成器和測(cè)試器的工作往往需交替進(jìn)行。替進(jìn)行。 使用生成使用生成-測(cè)試法應(yīng)考慮的關(guān)鍵問(wèn)題是如何在生成測(cè)試法應(yīng)考慮的關(guān)鍵問(wèn)題是如何在生成器和測(cè)試器之間分配知識(shí)器和測(cè)試器之間分配知識(shí) 經(jīng)驗(yàn)證明，知識(shí)豐富的生成器會(huì)導(dǎo)致較高的搜索經(jīng)驗(yàn)證明，知識(shí)豐富的生成器會(huì)導(dǎo)致較高的搜索效率效率 37 38五五 啟發(fā)式搜索的適用性討論啟發(fā)式搜索在人工智能研究的啟發(fā)式搜索在人工智能研究的早期早期是很重要的議是很重要的議題

21、，甚至有人說(shuō)人工智能就是啟發(fā)式搜索。題，甚至有人說(shuō)人工智能就是啟發(fā)式搜索。但隨著知識(shí)工程的興起，啟發(fā)式搜索已較少用于但隨著知識(shí)工程的興起，啟發(fā)式搜索已較少用于作為人工智能系統(tǒng)的頂層控制結(jié)構(gòu)，尤其是使用作為人工智能系統(tǒng)的頂層控制結(jié)構(gòu)，尤其是使用全局評(píng)價(jià)器的啟發(fā)式搜索方法，因?yàn)槠洳贿m合知全局評(píng)價(jià)器的啟發(fā)式搜索方法，因?yàn)槠洳贿m合知識(shí)密集型的問(wèn)題求解。識(shí)密集型的問(wèn)題求解。 但啟發(fā)式搜索仍不失為重要技術(shù)用于解決某些適但啟發(fā)式搜索仍不失為重要技術(shù)用于解決某些適合于它的子問(wèn)題，且搜索技術(shù)的不少思想方法可合于它的子問(wèn)題，且搜索技術(shù)的不少思想方法可用于用于KB系統(tǒng)的設(shè)計(jì)。系統(tǒng)的設(shè)計(jì)。 39啟發(fā)式搜索技術(shù)面臨啟發(fā)式搜索技術(shù)面臨三個(gè)關(guān)鍵三個(gè)關(guān)鍵選擇：選擇： 確定性或非確定性搜索方式；確定性或非確定性搜索方式； 搜索目標(biāo)狀態(tài)本身還是達(dá)到目標(biāo)狀態(tài)的解搜索目標(biāo)狀態(tài)本身還是達(dá)到目標(biāo)狀態(tài)的解答路徑答路徑(往往表示為狀態(tài)或操作算子序列往往表示為狀態(tài)或操作算子序列)； 搜索一個(gè)還是全部或最優(yōu)解答。搜索一個(gè)還是全部或最優(yōu)解答。 所謂確定性方式，就是利用啟發(fā)式信息選取所謂確定性方式，就是利用啟發(fā)式信息選取最好的分枝，而舍棄所有其余分枝不再予以考慮最好的分枝，而舍棄所有