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

2、概念：在搜索過程中，引入啟發(fā)式知識減少搜索的盲目性，提高搜索的效率，稱之為啟發(fā)式搜索目性，提高搜索的效率，稱之為啟發(fā)式搜索啟發(fā)式知識對搜索的作用：啟發(fā)式知識對搜索的作用： 選擇下一個(gè)要被擴(kuò)展的節(jié)點(diǎn)，對選擇下一個(gè)要被擴(kuò)展的節(jié)點(diǎn)，對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)用評價(jià)函數(shù)來實(shí)現(xiàn)啟發(fā)式搜索的典型是算法應(yīng)用評價(jià)函數(shù)來實(shí)現(xiàn)啟發(fā)式搜索的典型是算法A ，評，評價(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ù)來估算，稱為啟發(fā)式函數(shù) 8算法算法A搜索算法搜索算法A的一般過程：的一般過程：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中，對于中，對于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)的評價(jià)函數(shù)值經(jīng)由新、老父節(jié)點(diǎn)的評價(jià)函數(shù)值f(n,ni)、f(ni);若若f(n,ni) f(ni)點(diǎn)點(diǎn),則令則令f(ni) = f(n,ni),并移動子節(jié)點(diǎn)指并移動子節(jié)點(diǎn)指向老父節(jié)點(diǎn)的指針，改為指向新父節(jié)點(diǎn)向老父節(jié)點(diǎn)的指針，改為指向新父節(jié)點(diǎn) 對第對第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) 返回語句返回語句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à)最?。┑慕獯鹇窂剑瑒t稱算法具有可采納性 寬度優(yōu)先的搜索算法就是可采納的寬度優(yōu)先的搜索算法就是可采納的 15引入評價(jià)函數(shù)引入評價(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à)（長度）、該路徑前段（自初始狀態(tài)節(jié)點(diǎn)到節(jié)點(diǎn)（長度）、該路徑前段（自初始狀態(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à)。 將評價(jià)函數(shù)將評價(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ì)評價(jià)函數(shù)在理想的情況下，設(shè)計(jì)評價(jià)函數(shù)f時(shí)可以讓時(shí)可以讓g(n)g(n) = g g*(n)(n),h(n) = h h*(n)(n) 16如何挖掘貼切的啟發(fā)式知識如何挖掘貼切的啟發(fā)式知識(h(n)是設(shè)計(jì)評價(jià)函數(shù)乃是設(shè)計(jì)評價(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è)不受阻攔的情況下，移動到目標(biāo)個(gè)錯(cuò)位棋牌在假設(shè)不受阻攔的情況下，移動到目標(biāo)狀態(tài)相應(yīng)位置所需走步（移動次數(shù)）的總和狀態(tài)相應(yīng)位置所需走步（移動次數(shù)）的總和 17 18可以

10、證明，若確保對于搜索圖中的節(jié)點(diǎn)可以證明，若確保對于搜索圖中的節(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í)例傳教士和野人問題傳教士和野人問題N=5,K h(n) h h* * (n), (n),則則h(n)h(n)過強(qiáng)，使算法過強(qiáng)，使算法A A失去可采納失去

11、可采納性，從而不能確保找到最短解答路徑性，從而不能確保找到最短解答路徑設(shè)計(jì)接近、又總是設(shè)計(jì)接近、又總是 h h* * (n) (n)的的h(n)h(n)成為應(yīng)用成為應(yīng)用A A* *算法搜索算法搜索問題解答的關(guān)鍵，以壓縮搜索圖，提高搜索效率問題解答的關(guān)鍵，以壓縮搜索圖，提高搜索效率 23(3) (3) 設(shè)計(jì)設(shè)計(jì)h(n)h(n)的實(shí)用考慮的實(shí)用考慮f(n) = g(n) + h(n)使用評價(jià)函數(shù)使用評價(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的情況下，若限制只用評價(jià)函數(shù)的情況下，若限制只用評價(jià)函數(shù) f(n)= h(n)去去排序新擴(kuò)展出來的子節(jié)點(diǎn)排序新擴(kuò)

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

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

15、經(jīng)的岔路口，相當(dāng)于爬山的過程中記住了途經(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)。該遞歸過程的算法就取名為該遞歸過程的算法就取名為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，并按評，并按評價(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, 返回到語句（返回到語句（4）；）；（8） 將將n加到加到PATH表首，算法的本次調(diào)用

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

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

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

21、，甚至有人說人工智能就是啟發(fā)式搜索。題，甚至有人說人工智能就是啟發(fā)式搜索。但隨著知識工程的興起，啟發(fā)式搜索已較少用于但隨著知識工程的興起，啟發(fā)式搜索已較少用于作為人工智能系統(tǒng)的頂層控制結(jié)構(gòu)，尤其是使用作為人工智能系統(tǒng)的頂層控制結(jié)構(gòu)，尤其是使用全局評價(jià)器的啟發(fā)式搜索方法，因?yàn)槠洳贿m合知全局評價(jià)器的啟發(fā)式搜索方法，因?yàn)槠洳贿m合知識密集型的問題求解。識密集型的問題求解。 但啟發(fā)式搜索仍不失為重要技術(shù)用于解決某些適但啟發(fā)式搜索仍不失為重要技術(shù)用于解決某些適合于它的子問題，且搜索技術(shù)的不少思想方法可合于它的子問題，且搜索技術(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ā)式信息選取最好的分枝，而舍棄所有其余分枝不再予以考慮最好的分枝，而舍棄所有