人工智能原理-文庫吧資料
2024-07-31 05:54本頁面
【正文】 其算法就叫做 有序搜索算法 或 最佳優(yōu)先算法 。根據(jù)推測，某個具有低的估價值的節(jié)點較有可能處在最佳路徑上。 37 有序搜索 ? 我們用估價函數(shù) f來排列 GRAPHSEARCH第 8步中 OPEN表上的節(jié)點。暫時令 f為任意函數(shù)， 以后我們將會提出 f是從起始節(jié)點約束地通過節(jié)點 n而到達目標節(jié)點的最小代價路徑上的一個估算代價。每個不同的衡量標準只能考慮該問題中這個節(jié)點的某些決定性特性，或者對給定節(jié)點與目標節(jié)點進行比較，以決定相關(guān)特性。 ? 一個節(jié)點的“ 希望 ” (promise)有幾種不同的定義方法。 36 估價函數(shù) ? 用來估算節(jié)點希望程度的量度，叫做 估價函數(shù) (evaluation function)。這種搜索總是選擇“最有希望”的節(jié)點作為下一個被擴展的節(jié)點。 (3) 用于決定某些應(yīng)該從搜索樹中 拋棄 或修剪的節(jié)點。 把利用啟發(fā)信息的搜索方法叫做 啟發(fā)性搜索方法 35 啟發(fā)式搜索策略 ? 啟發(fā)信息按其用途可分為下列 3種： (1) 用于決定 要擴展 的下一個節(jié)點，以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地擴展。人們就試圖找到一種方法用于排列待擴展節(jié)點的順序，即選擇 最有希望 的節(jié)點加以擴展，那么，搜索效率將會大為提高。 (7) 轉(zhuǎn)向第 (2)步。 (6) 對于節(jié)點 i的每個后繼節(jié)點 j，計算 g(j)=g(i)+c(i,j)，并把所有后繼節(jié)點 j放進 OPEN表。 (5) 擴展節(jié)點 i。把節(jié)點 i從 OPEN表移至擴展節(jié)點表 CLOSED中。 (3) 從 OPEN表中選擇一個節(jié)點 i，使其 g(i)為最小。否則令 g(S)=0。在搜索樹上，我們假設(shè) g(i)也是從起始節(jié)點 S到節(jié)點 i的 最少代價 路徑上的代價，因為它是唯一的路徑； 32 等代價搜索算法 ? 等代價搜索方法以 g(i)的遞增順序擴展其節(jié)點，其算法： (1) 把起始節(jié)點 S放到未擴展節(jié)點表 OPEN中。寬度優(yōu)先搜索可被推廣用來解決這種尋找從起始狀態(tài)至目標狀態(tài)的具有最小代價的路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做 等代價搜索算法。 29 圖 八數(shù)碼難題的深度優(yōu)先搜索樹 30 等代價搜索 ? 有些問題并不要求有應(yīng)用算符序列為最少的解，而是要求具有某些特性的解。 圖 ，粗線條的路徑表明含有 5條應(yīng)用規(guī)則的一個解。 (6) 如果后繼節(jié)點中有任一個為目標節(jié)點，則求得一個解，成功退出；否則，轉(zhuǎn)向 (2)。 (5) 擴展節(jié)點 n，產(chǎn)生其全部后裔，并把它們放入 OPEN表的 前頭 。 (3) 把第一個節(jié)點 (節(jié)點 n)從 OPEN表移到CLOSED表。如果此節(jié)點為一目標節(jié)點，則得到一個解。值得說明的是，即使應(yīng)用了深度界限的規(guī)定，所求得的解答路徑并不一定就是最短的路徑。為了避免考慮太長的路徑 (防止搜索過程沿著無益的路徑擴展下去 )，往往給出一個節(jié)點擴展的最大深度 —— 深度界限 。替代路徑與前面已經(jīng)試過的路徑不同之處僅僅在于改變最后 n步，而且保持 n盡可能小。 (2) 任何其它節(jié)點的深度等于其父輩節(jié)點深度加上 1。深度相等的節(jié)點可以 任意 排列。 ? 首先擴展最新產(chǎn)生的節(jié)點。圖中最后一個節(jié)點是目標節(jié)點。 ?寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標節(jié)點的 最短途徑 ；這棵搜索樹提供了所有存在的路徑 (如果沒有路徑存在，那么對有限圖來說，我們就說該法失敗退出；對于無限圖來說，則永遠不會終止 )。（隊列模式） (6) 如果 n的任一個后繼節(jié)點是個目標節(jié)點，則找到一個解答，成功退出；否則轉(zhuǎn)向第 (2)步。如果沒有后繼節(jié)點，則轉(zhuǎn)向上述第 (2)步。 (3) 把第一個節(jié)點 (節(jié)點 n)從 OPEN表移出，并把它放入 CLOSED擴展節(jié)點表中。 15 16 ? 寬度優(yōu)先搜索算法如下： (1) 把起始節(jié)點放到 OPEN表中 (如果該起始節(jié)點為一目標節(jié)點，則求得一個解答 )。 寬度優(yōu)先搜索 (breadthfirst search)的定義：如果搜索是以 接近 起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索 (breadthfirst search)，如圖 。 ?寬度優(yōu)先搜索 ?深度優(yōu)先搜索 ?等代價搜索 13 寬度優(yōu)先搜索 ? 回顧上一節(jié)的尋找壽命為 X的人的例子，如果搜索時，從節(jié)點 A開始，對他的三個兒子按從左至右搜索，然后對他的所有孫子按從左至右搜索，依此下去。在失敗終止的情況下，從起始節(jié)點出發(fā)，一定達不到目標節(jié)點。這時，能夠重現(xiàn)從起始節(jié)點到目標節(jié)點的這條成功路徑，其辦法是從目標節(jié)點按指針向 S返回追溯。這種排序可以是 任意 的即盲目的 (屬于盲目搜索 )，也可以用以后要討論的各種 啟發(fā)
公司管理相關(guān)推薦
鄂ICP備17016276號-1