【正文】 ing procedure ? Sometimes, after analyzing we need to reproduce some states again. DB1 DB4 R2 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 DB1 DB2 DB4 R1 R2 DB1 DB2 DB3 DB4 R1 R2 R3 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 問題的狀態(tài)和它們之間的關(guān)系可以用一個(gè)圖隱含地加以描述 . 狀態(tài)用圖的節(jié)點(diǎn)表示 , 狀態(tài)之間的關(guān)系用圖中的弧表示 . the states and their relations are defined by a graph implicitly: states ———————— nodes rule applications —————— arcs 但是 , 我們也應(yīng)該注意到它們之間的區(qū)別 : However, generally the graph is endless , We can not draw the graphsin ordinary way. 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 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 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 Procedure GRAPHSEARCH 1 G=s, OPEN=(s)。 稱n為當(dāng)前節(jié)點(diǎn) . 5. IF GOAL(n) THEN EXIT(SUCCESS)。 mk是出現(xiàn)在 OPEN表中的子節(jié)點(diǎn) , ml是出現(xiàn)在 CLOSED表中的子節(jié)點(diǎn) , {Mi}={Mj}∪{Mk}∪{M l} 計(jì)算是否需要修改 mi到其后記節(jié)點(diǎn)的指針 . OPEN表中的節(jié)點(diǎn)按某種原則重新排序 . LOOP. 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 對(duì) GRAPHSEARCH算法的幾點(diǎn)說明 : 1. 兩個(gè)圖 , 2. G: 搜索圖 , 它是記錄算法訪問過的所有節(jié)點(diǎn)的圖 ,初始化為問題的初始狀態(tài) s, 在搜索過程中不斷地?cái)U(kuò)展 . 3. T: G的有向支撐樹 , 與 G有同樣的節(jié)點(diǎn) , 由指針定義 . 記錄由該節(jié)點(diǎn)到 s的最短路徑 , 在搜索過程中需要不斷調(diào)整 . 4. 2. 兩個(gè)表 : OPEN和 CLOSED, OPEN表記錄搜索圖的前沿 , CLOSED表記錄已經(jīng)擴(kuò)展過的節(jié)點(diǎn) . 5. 3. 樹 T的指針的建立和調(diào)整 . 6. 樹 T中節(jié)點(diǎn)的指針記錄從該節(jié)點(diǎn)到初始節(jié)點(diǎn) s的最短路徑 , 隨著算法的進(jìn)行 , 圖的擴(kuò)展 , 這些指針需要不斷地調(diào)整 . 對(duì)新產(chǎn)生的節(jié)點(diǎn) , 為其建立指針 . 對(duì) OPEN和 CLOSED表中的節(jié)點(diǎn) , 需要考慮調(diào)整其指針 , 對(duì)于 CLOSED表中節(jié)點(diǎn) , 還需要考慮調(diào)整其后繼節(jié)點(diǎn)的指針 . 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 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. 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 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 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 s 1 2 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 1 2 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 無信息的圖搜索過程 深度優(yōu)先和寬度優(yōu)先 深度優(yōu)先和寬度優(yōu)先的思想在數(shù)據(jù)結(jié)構(gòu)中已經(jīng)講過 , 在數(shù)據(jù)結(jié)構(gòu)中是作為樹的遍歷的方法講的 , 人工智能中在狀態(tài)空間中搜索解的過程也類似于遍歷 . 所不同的是這里搜索的是圖而不是樹 .所以這里我們只討論與解有關(guān)的問題 寬度優(yōu)先在搜索解的過程中總是在探索了層數(shù)小于或等于 n的節(jié)點(diǎn)之后才進(jìn)入到 n+1層節(jié)點(diǎn)的探索 , 所以這中方法獲得的解具有最短的解路徑 .但如果圖的分枝系數(shù)很高 , 或者解路徑很長 ,效率會(huì)很低 . 深度優(yōu)先可以很快地使實(shí)驗(yàn)解路徑延伸到很長 , 如果剛好在延伸的過程中遇到解 , 這種方法的效率會(huì)很高 , 但不能保證找到有最短的解路徑 . 甚至即使在原問題有解的時(shí)候 , 也會(huì)發(fā)生會(huì)在錯(cuò)誤的方向上無限延伸下去而找不到解的情況 , 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 深度優(yōu)先算法 Procedure DEPTHFIRTST SEARCH 1 G=s, OPEN=(s), CLOSED = (). 2 LOOP: IF OPEN=(), THEN EXIT(FAIL) 3 n=FIRST(OPEN)。 5 5 REMOVE(n, OPEN), ADD(n, CLOSED)。 7 ADD(mi, OPEN), 并標(biāo)記 mi到 n的指針 , 把不在 OPEN和 8 CLOSED 中的節(jié)點(diǎn)放在最前面 , 使深度大的節(jié)點(diǎn)可以優(yōu)先擴(kuò)展 . 9 8 GO LOOP 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 使用 DEPTHFIRSTSEARCH搜索的例 D6 C4 B4 A5 H3 G4 F5 E5 O2 J I K P3 T S K K L M N goal 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 為保證深度優(yōu)先算法在問題有解的情況下總能找到解 , 需要增加深度限制 , 而且深度限制