【正文】 Starting from the initial state, we generate an subgraph(an explicit part of the graph implicitly defined by production system), then we select the node in the subgraph to expand it, if the subgraph does not contain the goal node, we continue to expand it, until the subgraph is large enough to include the goal node , and we find the solution path from the initial node to the goal node. The procedure GRAPHSEARCH input : the production system(the initial nose, production rule, goal node) output: the solution path from the initial node to a goal node 人工智能 吉林大學珠海學院計算機科學與技術系 Procedure GRAPHSEARCH 1 G=s, OPEN=(s)。 mk是出現在 OPEN表中的子節(jié)點 , ml是出現在 CLOSED表中的子節(jié)點 , {Mi}={Mj}∪{Mk}∪{M l} 計算是否需要修改 mi到其后記節(jié)點的指針 . OPEN表中的節(jié)點按某種原則重新排序 . LOOP. 人工智能 吉林大學珠海學院計算機科學與技術系 對 GRAPHSEARCH算法的幾點說明 : 1. 兩個圖 , 2. G: 搜索圖 , 它是記錄算法訪問過的所有節(jié)點的圖 ,初始化為問題的初始狀態(tài) s, 在搜索過程中不斷地擴展 . 3. T: G的有向支撐樹 , 與 G有同樣的節(jié)點 , 由指針定義 . 記錄由該節(jié)點到 s的最短路徑 , 在搜索過程中需要不斷調整 . 4. 2. 兩個表 : OPEN和 CLOSED, OPEN表記錄搜索圖的前沿 , CLOSED表記錄已經擴展過的節(jié)點 . 5. 3. 樹 T的指針的建立和調整 . 6. 樹 T中節(jié)點的指針記錄從該節(jié)點到初始節(jié)點 s的最短路徑 , 隨著算法的進行 , 圖的擴展 , 這些指針需要不斷地調整 . 對新產生的節(jié)點 , 為其建立指針 . 對 OPEN和 CLOSED表中的節(jié)點 , 需要考慮調整其指針 , 對于 CLOSED表中節(jié)點 , 還需要考慮調整其后繼節(jié)點的指針 . 人工智能 吉林大學珠海學院計算機科學與技術系 Notes about the procedure GRAPHSEARCH 1. Two graphs: G: The explicit part of the graph generated by the production system, its initial node is the initial state, it is expanded constantly. T: the directed support tree of G, it has same nodes as the graph G, his arc(only one outgoing arc from a node) direct the shortest path from one node to another node. The arcs are marked by pointers. In order to preserve the character, the procedure need to readjust the arcs of the tree constantly. 人工智能 吉林大學珠海學院計算機科學與技術系 2. Two list: OPEN the frontier nodes of graph G, from which, we select a node to expand. CLOSED the interior nodes of graph G, the node have been expanded. 3. The establishment and readjustment of the pointers of tree T. For the newly generated nodes, we need to establish the pointer for them. For the nodes in the lists on OPEN and CLOSED , we need to consider to readjust their pointers. For the nodes of CLOSED, we need to consider the readjustment of their descendants, for the adjustment of the nodes of CLOSED may influence their descendant’ s pointers 人工智能 吉林大學珠海學院計算機科學與技術系 s 1 2 人工智能 吉林大學珠海學院計算機科學與技術系 1 2 人工智能 吉林大學珠海學院計算機科學與技術系 無信息的圖搜索過程 深度優(yōu)先和寬度優(yōu)先 深度優(yōu)先和寬度優(yōu)先的思想在數據結構中已經講過 , 在數據結構中是作為樹的遍歷的方法講的 , 人工智能中在狀態(tài)空間中搜索解的過程也類似于遍歷 . 所不同的是這里搜索的是圖而不是樹 .所以這里我們只討論與解有關的問題 寬度優(yōu)先在搜索解的過程中總是在探索了層數小于或等于 n的節(jié)點之后才進入到 n+1層節(jié)點的探索 , 所以這中方法獲得的解具有最短的解路徑 .但如果圖的分枝系數很高 , 或者解路徑很長 ,效率會很低 . 深度優(yōu)先可以很快地使實驗解路徑延伸到很長 , 如果剛好在延伸的過程中遇到解 , 這種方法的效率會很高 , 但不能保證找到有最短的解路徑 . 甚至即使在原問題有解的時候 , 也會發(fā)生會在錯誤的方向上無限延伸下去而找不到解的情況 , 人工智能 吉林大學珠海學院計算機科學與技術系 深度優(yōu)先算法 Procedure DEPTHFIRTST SEARCH 1 G=s, OPEN=(s), CLOSED = (). 2 LOOP: IF OPEN=(), THEN EXIT(FAIL) 3 n=FIRST(OPEN)。 7 ADD(mi, OPEN), 并標記 mi到 n的指針 , 把不在 OPEN和 8 CLOSED 中的節(jié)點放在最前面 , 使深度大的節(jié)點可以優(yōu)先擴展 . 9 8 GO LOOP 人工智能 吉林大學珠海學院計算機科學與技術系 使用 DEPTHFIRSTSEARCH搜索的例 D6 C4 B4 A5 H3 G4 F5 E5 O2 J I K P3 T S K K L M N goal 人工智能 吉林大學珠海學院計算機科學與技術系 為保證深度優(yōu)先算法在問題有解的情況下總能找到解 , 需要增加深度限制 , 而且深度限制必須超過解的長度 . 人工智能 吉林大學珠海學院計算機科學與技術系 啟發(fā)式搜索 4。 根據啟發(fā)函數對尚為探索的節(jié)點進行排序， 把最有希望的節(jié)點排再前面， 在擴展節(jié)點時把最有希望的節(jié)點拿出來考慮。 ? 5 REMOVE(n, OPEN), ADD(n, CLOSED)。 closed = [s4] 2. 測試 B4, Open = [D5, E5,A6, C6, F6]。 closed = [s4, B4, D5,E5, I5] 6. 測試 K5, Open = [L5,A6, C6, F6,G6, H7, J7, M7]。 人工智能 吉林大學珠海學院計算機科學與技術系 A*算法是可采納的 若存在從初始節(jié)點 s到目標節(jié)點 t的路徑， 則 A*算法必能找到最佳解路徑。 這個條件就是單調性。 如果 h2(n) 比 h1(n)有更高的信息度， 則算法 2所擴展的節(jié)點一定會被算法 1所擴展， 換句話說， 算法 2所擴展的節(jié)點比算法 1擴展的節(jié)點少。根據前面幾節(jié)的介紹， 我們知道如果啟發(fā)函數滿足 h(n)≦h*(n), 即使用 A*算法， 則只要被搜索的圖有解，算法肯定能找到最佳解路徑。因此， 有時為了增加算法的啟發(fā)能力， 我們采用較大的啟發(fā)函數值， 甚至于不滿足 h(n)≦h*(n) ，這樣做犧牲了算法的可采納性， 但可以使算法擴展的節(jié)點個數大幅度下降，換來了算法的高效率。因此， 在解決實際問題時，我們需要在啟發(fā)函時的計算量和擴展節(jié)點的數量之間作認真