chapter3-20xx(編輯修改稿)
2024-08-31 10:12 本頁面
【文章內(nèi)容簡介】 到的解不一定是最優(yōu)解（最短路徑）。 21 ● 等代價搜索 有些問題并不要求有應用算符序列為最少的解，而是要求具有某些特性的解。搜索樹中每條連接弧線上的有關(guān)代價以及隨之而求得的具有最小代價的解答路徑，與許多這樣的廣義準則相符合。寬度優(yōu)先搜索可被推廣用來解決這種尋找從起始狀態(tài)至目標狀態(tài)的具有最小代價的路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做等代價搜索算法 。 22 等代價搜索算法： 等代價搜索方法以 g(i)的遞增順序擴展其節(jié)點，其算法如下： (1) 把起始節(jié)點 S放到未擴展節(jié)點表 OPEN中。如果此起始節(jié)點為一目標節(jié)點，則求得一個解 。否則令 g(S)=0。 (2) 如果 OPEN是個空表，則沒有解而失敗退出。 (3) 從 OPEN表中選擇一個節(jié)點 i，使其 g(i)為最小。如果有幾個節(jié)點都合格，那么就要選擇一個目標節(jié)點作為節(jié)點 i(要是有目標節(jié)點的話 )；否則，就從中選一個作為節(jié)點 i。把節(jié)點 i從 OPEN表移至擴展節(jié)點表 CLOSED中。 (4) 如果節(jié)點 i為目標節(jié)點，則求得一個解。 (5) 擴展節(jié)點 i。如果沒有后繼節(jié)點，則轉(zhuǎn)向第 (2)步。 (6) 對于節(jié)點 i的每個后繼節(jié)點 j，計算 g(j)=g(i)+c(i,j)，并把所有后繼節(jié)點 j放進 OPEN表。提供回到節(jié)點 i的指針。 (7) 轉(zhuǎn)向第 (2)步。 23 24 啟發(fā)式搜索 盲目搜索的不足：效率低，耗費過多的計算空間與時間。 分析前面介紹的寬度優(yōu)先、深度優(yōu)先搜索，或等代價搜索算法 ,其主要的差別是 OPEN表中待擴展節(jié)點的順序問題。人們就試圖找到一種方法用于排列待擴展節(jié)點的順序，即選擇最有希望的節(jié)點加以擴展，那么，搜索效率將會大為提高。 啟發(fā)信息：進行搜索技術(shù)一般需要某些有關(guān)具體問題領(lǐng)域的特性的信息，把此種信息叫做啟發(fā)信息。 把利用啟發(fā)信息的搜索方法叫做啟發(fā)性搜索方法。 25 假設(shè)初始狀態(tài)、算符和目標狀態(tài)的定義都是完全確定的，然后決定一個搜索空間。因此，問題就在于如何有效地搜索這個給定空間。 啟發(fā)信息按其用途可分為下列 3種： (1) 用于決定要擴展的下一個節(jié)點，以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地擴展。 (2) 在擴展一個節(jié)點的過程中，用于決定要生成哪一個或哪幾個后繼節(jié)點，以免盲目地同時生成所有可能的節(jié)點。 (3) 用于決定某些應該從搜索樹中拋棄或修剪的節(jié)點。 在本節(jié)中，我們只討論利用上述第一種啟發(fā)信息的狀態(tài)空間搜索算法，即決定哪個是下一步要擴展的節(jié)點。這種搜索總是選擇 “ 最有希望 ”的節(jié)點作為下一個被擴展的節(jié)點。這種搜索叫做有序搜索 (ordered search)。 ● 啟發(fā)式搜索策略 26 用來估算節(jié)點希望程度的量度，叫做估價函數(shù) (evaluation function)。 一個節(jié)點的 希望 (promise)有幾種不同的定義方法。在狀態(tài)空間問題中，一種方法是估算目標節(jié)點到此節(jié)點的距離；另一種方法認為，解答路徑包括被估價過的節(jié)點，并計算全條路徑的長度或難度。每個不同的衡量標準只能考慮該問題中這個節(jié)點的某些決定性特性，或者對給定節(jié)點與目標節(jié)點進行比較，以決定相關(guān)特性。 我們用符號 f來標記估價函數(shù)，用 f(n)表示節(jié)點 n的估價函數(shù)值。暫時令 f為任意函數(shù)，以后我們將會提出 f是從起始節(jié)點約束地通過節(jié)點 n而到達目標節(jié)點的最小代價路徑上的一個估算代價。 ● 估價
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號-1