chapter3-20xx-在線瀏覽
2024-09-14 10:12本頁面
【正文】 叫做寬度優(yōu)先搜索 (breadthfirst search)。 寬度優(yōu)先搜索 10 寬度優(yōu)先搜索算法 如下： (1) 把起始節(jié)點放到 OPEN表中 (如果該起始節(jié)點為一目標節(jié)點，則求得一個解答 )。 (3) 把第一個節(jié)點 (節(jié)點 n)從 OPEN表移出，并把它放入 CLOSED擴展節(jié)點表中。如果沒有后繼節(jié)點，則轉(zhuǎn)向上述第 (2)步。 (6) 如果 n的任一個后繼節(jié)點是個目標節(jié)點，則找到一個解答，成功退出；否則轉(zhuǎn)向第 (2)步。 寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標節(jié)點的最短途徑；這棵搜索樹提供了所有存在的路徑 (如果沒有路徑存在，那么對有限圖來說，我們就說該法失敗退出；對于無限圖來說，則永遠不會終止 )。 該算法是完備的，即問題有解的話，則一定能找到解，且是最優(yōu)解（路徑最短），這是優(yōu)點，缺點是搜索效率低。下圖是一個深度優(yōu)先搜索示意圖。深度相等的節(jié)點可以任意排列。 (2) 任何其它節(jié)點的深度等于其父輩節(jié)點深度加上 1。為了避免考慮太長的路徑 (防止搜索過程沿著無益的路徑擴展下去 )，往往給出一個節(jié)點擴展的最大深度 ——深度界限。值得說明的是，即使應用了深度界限的規(guī)定，所求得的解答路徑并不一定就是最短的路徑。如果此節(jié)點為一目標節(jié)點，則得到一個解。 (3) 把第一個節(jié)點 (節(jié)點 n)從 OPEN表移到 CLOSED表。 (5) 擴展節(jié)點 n，產(chǎn)生其全部后裔，并把它們放入 OPEN表的前頭。 (6) 如果后繼節(jié)點中有任一個為目標節(jié)點，則求得一個解，成功退出；否則，轉(zhuǎn)向 (2)。 特點：可能誤入歧途找不到解，不是完備的，得到的解不一定是最優(yōu)解（最短路徑）。搜索樹中每條連接弧線上的有關代價以及隨之而求得的具有最小代價的解答路徑，與許多這樣的廣義準則相符合。 22 等代價搜索算法： 等代價搜索方法以 g(i)的遞增順序擴展其節(jié)點，其算法如下： (1) 把起始節(jié)點 S放到未擴展節(jié)點表 OPEN中。否則令 g(S)=0。 (3) 從 OPEN表中選擇一個節(jié)點 i，使其 g(i)為最小。把節(jié)點 i從 OPEN表移至擴展節(jié)點表 CLOSED中。 (5) 擴展節(jié)點 i。 (6) 對于節(jié)點 i的每個后繼節(jié)點 j，計算 g(j)=g(i)+c(i,j)，并把所有后繼節(jié)點 j放進 OPEN表。 (7) 轉(zhuǎn)向第 (2)步。 分析前面介紹的寬度優(yōu)先、深度優(yōu)先搜索，或等代價搜索算法 ,其主要的差別是 OPEN表中待擴展節(jié)點的順序問題。 啟發(fā)信息：進行搜索技術一般需要某些有關具體問題領域的特性的信息，把此種信息叫做啟發(fā)信息。 25 假設初始狀態(tài)、算符和目標狀態(tài)的定義都是完全確定的，然后決定一個搜索空間。 啟發(fā)信息按其用途可分為下列 3種： (1) 用于決定要擴展的下一個節(jié)點，以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地擴展。 (3) 用于決定某些應該從搜索樹中拋棄或修剪的節(jié)點。這種搜索總是選擇 “ 最有希望 ”的節(jié)點作為下一個被擴展的節(jié)點。 ● 啟發(fā)式搜索策略 26 用來估算節(jié)點希望程度的量度，叫做估價函數(shù) (evaluation function)。在狀態(tài)空間問題中，一種方法是估算目標節(jié)點到此節(jié)點的距離；另一種方法認為，解答路徑包括被估價過的節(jié)點，并計算全條路徑的長度或難度。 我們用符號 f來標記估價函數(shù)，用 f(n)表示節(jié)點 n的估價函數(shù)值。 ● 估價函數(shù) 27 我們
職業(yè)教育相關推薦
鄂ICP備17016276號-1