人工智能原理(編輯修改稿)
2024-08-14 05:54 本頁面
【文章內(nèi)容簡介】 兩步有差別的那些路徑，等等。 29 圖 八數(shù)碼難題的深度優(yōu)先搜索樹 30 等代價搜索 ? 有些問題并不要求有應用算符序列為最少的解，而是要求具有某些特性的解。搜索樹中每條連接弧線上的有關代價以及隨之而求得的具有最小代價的解答路徑，與許多這樣的廣義準則相符合。寬度優(yōu)先搜索可被推廣用來解決這種尋找從起始狀態(tài)至目標狀態(tài)的具有最小代價的路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做 等代價搜索算法。 31 ? 有如下一些記號： 起始節(jié)點記為 S； 從節(jié)點 i到它的后繼節(jié)點 j的連接弧線代價記為 c(i,j)； 從起始節(jié)點 S到任一節(jié)點 i的路徑代價記為 g(i)。在搜索樹上，我們假設 g(i)也是從起始節(jié)點 S到節(jié)點 i的 最少代價 路徑上的代價，因為它是唯一的路徑； 32 等代價搜索算法 ? 等代價搜索方法以 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é)點，則轉向第 (2)步。 (6) 對于節(jié)點 i的每個后繼節(jié)點 j，計算 g(j)=g(i)+c(i,j)，并把所有后繼節(jié)點 j放進 OPEN表。提供回到節(jié)點 i的指針。 (7) 轉向第 (2)步。 33 圖 等代價搜索算法框圖 34 啟發(fā)式搜索 盲目搜索的不足：效率低，耗費過多的計算空間與時間 分析前面介紹的寬度優(yōu)先、深度優(yōu)先搜索，或等代價搜索算法 ,其主要的差別是 OPEN表中待擴展節(jié)點的順序問題。人們就試圖找到一種方法用于排列待擴展節(jié)點的順序，即選擇 最有希望 的節(jié)點加以擴展，那么，搜索效率將會大為提高。 啟發(fā)信息 ：進行搜索技術一般需要某些有關具體問題領域 的特性的，與具體問題求解過程有關的，并可 指導 搜索過程朝著最有希望方向前進的控制信息，把此種信息叫做 啟發(fā)信息 。 把利用啟發(fā)信息的搜索方法叫做 啟發(fā)性搜索方法 35 啟發(fā)式搜索策略 ? 啟發(fā)信息按其用途可分為下列 3種： (1) 用于決定 要擴展 的下一個節(jié)點，以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地擴展。 (2) 在擴展一個節(jié)點的過程中，用于決定要 生成 哪一個或哪幾個后繼節(jié)點，以免盲目地同時生成所有可能的節(jié)點。 (3) 用于決定某些應該從搜索樹中 拋棄 或修剪的節(jié)點。 在本節(jié)中，只討論利用上述第一種啟發(fā)信息的狀態(tài)空間搜索算法，即決定哪個是下一步要擴展的節(jié)點。這種搜索總是選擇“最有希望”的節(jié)點作為下一個被擴展的節(jié)點。這種搜索叫做 有序搜索 (ordered search)。 36 估價函數(shù) ? 用來估算節(jié)點希望程度的量度，叫做 估價函數(shù) (evaluation function)。 ? 估價函數(shù)的任務就是估計 OPEN表中各節(jié)點的重要程度。 ? 一個節(jié)點的“ 希望 ” (promise)有幾種不同的定義方法。在狀態(tài)空間問題中， 一種方法 是估算目標節(jié)點到此節(jié)點的距離； 另一種方法 認為，解答路徑包括被估價過的節(jié)點，并計算全條路徑的長度或難度。每個不同的衡量標準只能考慮該問題中這個節(jié)點的某些決定性特性，或者對給定節(jié)點與目標節(jié)點進行比較，以決定相關特性。 我們用符號 f來標記估價函數(shù)，用 f(n)表示節(jié)點 n的估價函數(shù)值。暫時令 f為任意函數(shù)， 以后我們將會提出 f是從起始節(jié)點約束地通過節(jié)點 n而到達目標節(jié)點的最小代價路徑上的一個估算代價。 一般形式： f(n)=g(n)+h(n)， g(n)是從 s0到 n的實際代價，h(n)是從節(jié)點 n到目標節(jié)點 sg的估計代價。 37 有序搜索 ? 我們用估價函數(shù) f來排列 GRAPHSEARCH第 8步中 OPEN表上的節(jié)點。根據(jù)習慣， OPEN表上的節(jié)點按照它們 f函數(shù)值的遞增順序排列。根據(jù)推測，某個具有低的估價值的節(jié)點較有可能處在最佳路徑上。應用某個算法 (例如等代價算法 )選擇 OPEN表上具有最小 f值的節(jié)點作為下一個要擴展的節(jié)點。這種搜索方法叫做 有序搜索 或 最佳優(yōu)先搜索 ，而其算法就叫做 有序搜索算法 或 最佳優(yōu)先算法 ?？梢娝偸沁x擇最有希望的節(jié)點作為下一個要擴展的節(jié)點。 ? 有序搜索 (ordered search)又稱為 最好優(yōu)先搜索
公司管理相關推薦
鄂ICP備17016276號-1