人工智能原理-在線瀏覽
2024-08-28 05:54本頁面
【正文】 續(xù)。 (4) 擴展節(jié)點 n。 (5) 把 n的所有后繼節(jié)點放到 OPEN表的 末端 ，并提供從這些后繼節(jié)點回到 n的指針。 17 18 ? 寬度優(yōu)先搜索方法分析： ?寬度優(yōu)先搜索是圖搜索一般過程的 特殊 情況，將圖搜索一般過程中的第 8步具體化為本算法中的第 6步，這實際是將 OPEN表作為“ 先進先出 ”的隊列進行操作。 19 ? 例：把寬度優(yōu)先搜索應用于八數(shù)碼難題時所生成的搜索樹，這個問題就是要把初始棋局變?yōu)槿缦履繕似寰值膯栴}： ? 搜索樹上的所有節(jié)點都標記它們所對應的狀態(tài)描述，每個節(jié)點旁邊的數(shù)字表示節(jié)點擴展的順序 (按順時針方向移動空格 )。 20 圖 八數(shù)碼難題的寬度優(yōu)先搜索樹 21 深度優(yōu)先搜索 ? 另一種盲目 (無信息 )搜索叫做深度優(yōu)先搜索(depthfirst search)。如下圖 22 圖 深度優(yōu)先搜索示意圖 圖 23 ? 分析深度優(yōu)先搜索示意圖可看出，在深度優(yōu)先搜索中，我們首先擴展最新產(chǎn)生的 (即最深的 )節(jié)點。 24 ? 我們定義節(jié)點的深度如下： (1) 起始節(jié)點 (即根節(jié)點 )的深度為 0。 首先，擴展最深的節(jié)點的結(jié)果使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點向下進行下去；只有當搜索到達一個 沒有后裔 的狀態(tài)時，它才考慮另一條替代的路徑。 25 ? 對于許多問題，其狀態(tài)空間搜索樹的深度可能為無限深，或者可能至少要比某個可接受的解答序列的已知深度上限還要深。任何節(jié)點如果達到了深度界限，那么都將把它們作為沒有后繼節(jié)點處理。 26 ? 含有深度界限的深度優(yōu)先搜索算法如下： (1) 把起始節(jié)點 S放到未擴展節(jié)點 OPEN表中。 (2) 如果 OPEN為一空表，則失敗退出。 (4) 如果節(jié)點 n的深度等于最大深度，則轉(zhuǎn)向(2)。如果沒有后裔，則轉(zhuǎn)向 (2)。 27 算法演示圖 28 ? 例：按深度優(yōu)先搜索生成的八數(shù)碼難題搜索樹，我們設置深度界限為 5。從圖可見，深度優(yōu)先搜索過程是沿著一條路徑進行下去，直到深度界限為止，然后再考慮只有最后一步有差別的相同深度或較淺深度可供選擇的路徑，接著再考慮最后兩步有差別的那些路徑，等等。搜索樹中每條連接弧線上的有關(guān)代價以及隨之而求得的具有最小代價的解答路徑，與許多這樣的廣義準則相符合。 31 ? 有如下一些記號： 起始節(jié)點記為 S； 從節(jié)點 i到它的后繼節(jié)點 j的連接弧線代價記為 c(i,j)； 從起始節(jié)點 S到任一節(jié)點 i的路徑代價記為 g(i)。如果此起始節(jié)點為一目標節(jié)點，則求得一個解 。 (2) 如果 OPEN是個空表，則沒有解而失敗退出。如果有幾個節(jié)點都合格，那么就要選擇一個目標節(jié)點作為節(jié)點 i(要是有目標節(jié)點的話 )；否則，就從中選一個作為節(jié)點i。 (4) 如果節(jié)點 i為目標節(jié)點，則求得一個解。如果沒有后繼節(jié)點，則轉(zhuǎn)向第 (2)步。提供回到節(jié)點 i的指針。 33 圖 等代價搜索算法框圖 34 啟發(fā)式搜索 盲目搜索的不足：效率低，耗費過多的計算空間與時間 分析前面介紹的寬度優(yōu)先、深度優(yōu)先搜索，或等代價搜索算法 ,其主要的差別是 OPEN表中待擴展節(jié)點的順序問題。 啟發(fā)信息 ：進行搜索技術(shù)一般需要某些有關(guān)具體問題領域 的特性的，與具體問題求解過程有關(guān)的，并可 指導 搜索過程朝著最有希望方向前進的控制信息，把此種信息叫做 啟發(fā)信息 。 (2) 在擴展一個節(jié)點的過程中，用于決定要 生成 哪一個或哪幾個后繼節(jié)點，以免盲目地同時生成所有可能的節(jié)點。 在本節(jié)中，只討論利用上述第一種啟發(fā)信息的狀態(tài)空間搜索算法，即決定哪個是下一步要擴展的節(jié)點。這種搜索叫做 有序搜索 (ordered search)。 ? 估價函數(shù)的任務就是估計 OPEN表中各節(jié)點的重要程度。在狀態(tài)空間問題中， 一種方法 是估算目標節(jié)點到此節(jié)點的距離； 另一種方法 認為，解答路徑包括被估價過的節(jié)點，并計算全條路徑的長度或難度。 我們用符號 f來標記估價函數(shù)，用 f(n)表示節(jié)點 n的估價函數(shù)值。 一般形式： f(n)=g(n)+h(n)， g(n)是從 s0到 n的實際代價，h(n)是從節(jié)點 n到目標節(jié)點 sg的估計代價。根據(jù)習慣， OPEN表上的節(jié)點按照它們 f函數(shù)值的遞增順序排列。應用某個算法 (例如等代價算法 )選擇 OPEN表上具有最小 f值的節(jié)點作為下一個要擴展的節(jié)點?？梢娝偸沁x擇最有希望的節(jié)點作為下一個要擴展的節(jié)點。 ? 尼爾遜（ Nilsson）曾提出一個有序搜索的基本算法。被選為擴展的節(jié)點，是估價函數(shù)最小的節(jié)點。 (2) 如果 OPEN是
公司管理相關(guān)推薦
鄂ICP備17016276號-1