【文章內(nèi)容簡(jiǎn)介】 t, 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)。 G為搜索圖 , 初始化為問(wèn)題的初始狀態(tài) s, 建立 OPEN表 ,初始化為只含初始狀態(tài) s. 2. CLOSED = (),建立 CLOSED表 ,初始化為空表 . 3. LOOP: IF OPEN=(), THEN EXIT(FAIL) 4. n=FIRST(OPEN), REMOVE(n, OPEN), ADD(n, CLOSED)。 稱n為當(dāng)前節(jié)點(diǎn) . 5. IF GOAL(n) THEN EXIT(SUCCESS)。 由 n循指針?lè)祷?s, 可以獲得解路徑 . 6. EXPAND(n)→mi, G=ADD(mi, G), 子節(jié)點(diǎn)集 {mi}中不包含 n的父輩節(jié)點(diǎn) . 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 7 標(biāo)記和修改指針 ADD(mj, OPEN), 并標(biāo)記 mj連接到 n的指針 , mj是未在 OPEN和 CLOSED中出現(xiàn)過(guò)的子節(jié)點(diǎn) . 計(jì)算是否需要修改 mk, ml到 n的指針 。 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)說(shuō)明 : 1. 兩個(gè)圖 , G: 搜索圖 , 它是記錄算法訪問(wèn)過(guò)的所有節(jié)點(diǎn)的圖 ,初始化為問(wèn)題的初始狀態(tài) s, 在搜索過(guò)程中不斷地?cái)U(kuò)展 . T: G的有向支撐樹 , 與 G有同樣的節(jié)點(diǎn) , 由指針定義 . 記錄由該節(jié)點(diǎn)到 s的最短路徑 , 在搜索過(guò)程中需要不斷調(diào)整 . 2. 兩個(gè)表 : OPEN和 CLOSED, OPEN表記錄搜索圖的前沿 , CLOSED表記錄已經(jīng)擴(kuò)展過(guò)的節(jié)點(diǎn) . 3. 樹 T的指針的建立和調(diào)整 . 樹 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ù)系 無(wú)信息的圖搜索過(guò)程 深度優(yōu)先和寬度優(yōu)先 深度優(yōu)先和寬度優(yōu)先的思想在數(shù)據(jù)結(jié)構(gòu)中已經(jīng)講過(guò) , 在數(shù)據(jù)結(jié)構(gòu)中是作為樹的遍歷的方法講的 , 人工智能中在狀態(tài)空間中搜索解的過(guò)程也類似于遍歷 . 所不同的是這里搜索的是圖而不是樹 .所以這里我們只討論與解有關(guān)的問(wèn)題 寬度優(yōu)先在搜索解的過(guò)程中總是在探索了層數(shù)小于或等于 n的節(jié)點(diǎn)之后才進(jìn)入到 n+1層節(jié)點(diǎn)的探索 , 所以這中方法獲得的解具有最短的解路徑 .但如果圖的分枝系數(shù)很高 , 或者解路徑很長(zhǎng) ,效率會(huì)很低 . 深度優(yōu)先可以很快地使實(shí)驗(yàn)解路徑延伸到很長(zhǎng) , 如果剛好在延伸的過(guò)程中遇到解 , 這種方法的效率會(huì)很高 , 但不能保證找到有最短的解路徑 . 甚至即使在原問(wèn)題有解的時(shí)候 , 也會(huì)發(fā)生會(huì)在錯(cuò)誤的方向上無(wú)限延伸下去而找不到解的情況 , 人工智能 吉林大學(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)。 4 IF GOAL(n) THEN EXIT(SUCCESS)。 5 REMOVE(n, OPEN), ADD(n, CLOSED)。 6 EXPAND(n)→{mi}, G=ADD(mi, G)。 7 ADD(mi, OPEN), 并標(biāo)記 mi到 n的指針 , 把不在 OPEN和 CLOSED 中的節(jié)點(diǎn)放在最前面 , 使深度大的節(jié)點(diǎn)可以優(yōu)先擴(kuò)展 . 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)先算法在問(wèn)題有解的情況下總能找到解 , 需要增加深度限制 , 而且深度限制必須超過(guò)解的長(zhǎng)度 . 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 啟發(fā)式搜索 4。 0 簡(jiǎn)介 heuristic Of or relating to a usually speculative formulation serving as a guide in the investigation or solution of a problem: 探索的 ,做為調(diào)查或解決問(wèn)題的向?qū)У囊环N通常為推測(cè)性系統(tǒng)闡述 回溯式搜索， 深度優(yōu)先和寬度優(yōu)先都不使用領(lǐng)域知識(shí)， 效率很低。 啟發(fā)式搜索使用關(guān)于領(lǐng)域的信息指導(dǎo)， 使搜索向著有利于獲得解的方向進(jìn)展。如果應(yīng)用得好，可以明顯地縮小搜索空