【導(dǎo)讀】完成，引用他人成果的部分均已列出參考文獻。如論文涉及任何知識產(chǎn)權(quán)糾。紛，本人將承擔一切責任。的解的一種方法。最優(yōu)路徑搜索目前在互聯(lián)網(wǎng)的尋址計算、智能交通系統(tǒng),地理信息系統(tǒng)等領(lǐng)域有著廣。本課題對搜索相關(guān)算法進行詳細分析，并實現(xiàn)一個搜索應(yīng)用實例——基于A*算法的地圖路。徑搜索原型系統(tǒng)。利用A*算法實現(xiàn)地圖路徑搜索，最后以直觀的方式展現(xiàn)搜索結(jié)果。

　　

【正文】 點的指針，然后將這些子節(jié)點放入 Open 表中； (7) 根據(jù)各節(jié)點的估價函數(shù)值，對 Open 表中的全部節(jié)點按從小到大的順序重新進行排序； (8) 轉(zhuǎn)第 (2)步。 由于上述算法的第 (7)步要對 Open 表中的全部節(jié)點按其估價函數(shù)值從小到大重新進行排序，這樣在算法第 (3)步取出的節(jié)點就一定是 Open表的所有節(jié)點中估價函數(shù)值最小的一個節(jié)點。因此，它是一種全局擇優(yōu)的搜索方式。 對上述算法進一步分析還可以發(fā)現(xiàn)：如果取估價函數(shù) f(n)=g(n)，則它將退化為代價樹的廣度優(yōu)先搜索；如果取估價函數(shù) f(n)=d(n)，則它將退化為 廣度優(yōu)先搜索。可見，廣度優(yōu)先搜索和代價樹的廣度優(yōu)先搜索是全局擇優(yōu)搜索的兩個特例。 在局部擇優(yōu)搜索中，每當需要擴展節(jié)點時，總是從剛生成的子節(jié)點中選擇一個估價函數(shù)值最小的節(jié)點進行擴展。其搜索過程可描述如下： (1)把初始節(jié)點 S0 放入 Open 表中， f(S0)=g(S0)+h(S0)； (2)如果 Open 表為空，則問題無解 ，失敗退出； (3)把 Open 表的第一個節(jié)點取出放入 Closed 表，并記該節(jié)點為 n； (4)考察節(jié)點 n 是否為目標節(jié)點。若是，則找到了問題的解，成功退出； (5) 若節(jié)點 n 不可擴 展，則轉(zhuǎn)第 (2)步； (6) 擴展節(jié)點 n，生成其子節(jié)點 ni(i=1, 2, ? )，計算每個子節(jié)點的估價值 f(ni)(i=1, 2, ? )，并按估價值從小到大的順序依次放入 Open 表的首部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針，然后轉(zhuǎn)第 (2)步。 東南大學成賢學院畢業(yè)論文 11 由于上述算法的第 (6)步僅是把剛生成的子節(jié)點按其估價函數(shù)值從小到大放入 Open 表的首部，這樣在算法第 (3)步取出的節(jié)點僅是剛生成的子節(jié)點中估價函數(shù)值最小的一個節(jié)點。因此，它是一種局部擇優(yōu)的搜索方式。 對這一算法進一步分析也可以發(fā)現(xiàn)：如果取估價函數(shù) f(n)=g(n)， 則它將退化為代價樹的深度優(yōu)先搜索；如果取估價函數(shù) f(n)=d(n)，則它將退化為深度優(yōu)先搜索?？梢?，深度優(yōu)先搜索和代價樹的深度優(yōu)先搜索是局部擇優(yōu)搜索的兩個特例 [3]。 A*算法描述 A* 算法的步驟為： (1) 把 S0 放入 OPEN 表 , 記 f = h , 令 CLOSED 為空表。 (2) 若 OPEN 為空表 , 則宣告失敗并退出。 (3) 選取 OPEN 表中未設(shè)置過的具有最小 f 值的節(jié)點為最佳節(jié)點 BESTNODE , 并把它放入CLOSED 表。 (4)若 BESTNODE 為一目標節(jié)點 , 則成功求 得一解并退出。 (5)若 BESTNODE 不是目標節(jié)點 , 則擴展之 , 產(chǎn)生后繼節(jié)點 SUCCSSOR。 (6)對每個 SUCCSSOR 進行下列過程 : a. 建立從 SUCCSSOR 返回 BESTNODE 的指針 。 b. 計算 g (SUC) = g(BES) + g(BES , SUC) 。 c. 如果 SUCCSSOR∈ OPEN, 則稱此節(jié)點為 OLD, 并把它添至 BESTNODE 的后繼節(jié)點表中 。 d. 比較新舊路徑代價。如果 g ( SUC) g ( OLD) , 則重新確定 OLD 的父輩節(jié)點為 BESTNODE, 記下較小代價 g( OLD) , 并修正 f ( OLD)值 。 e. 若至 OLD 節(jié)點的代價較低或一樣 , 則停止擴展節(jié)點 。 f. 若 SUCCSSOR 不在 OPEN 表中 , 則看其是否在 CLOSED 表中 。 g. 若 SUCCSSOR 在 CLOSED 表中 , 則轉(zhuǎn)向 c 步驟 。 h. 若 SUCCSSOR 既不在 OPEN 表中 , 又不在 CLOSED 表中 , 則把它放入 OPEN 表中 ,并添入BESTNODE 后裔表 , 然后轉(zhuǎn)向第 (7)步。 (7) 計算 f 值 , 然后轉(zhuǎn)入第 (2)步 [3]。 算法中 f（ n）規(guī)定為對從初始 節(jié)點 s 出發(fā)，約束通過節(jié)點 n 到達目標點 t，最小耗散值路徑的耗散值 f *(n)的估計值，通常取正值。 f（ n）由兩個分量組成，其中 g（ n）是到目前為止，從 s 到 n 的一條最小耗散值路徑的耗散值，是作為從 s 到 n 最小耗散值路徑的耗散值 g*(n)的估計值， h（ n）是從 n到目標節(jié)點 t，最小耗散值路徑的耗散值 h*(n)的估計值。 設(shè)函數(shù) k（ ni， nj）表示最小耗散路徑的實際耗散值（當 ni到 nj 無通路時則 k（ ni， nj）無意義），則 g*（ n）＝ k（ s， n）， h*（ n）＝ min k（ n， ti），其中 ti是目標節(jié)點集， k（ n， ti） 就是從 n 到每一個目標節(jié)點最小耗散值路徑的耗散值， h*（ n）是其中最小值的那條路徑的耗散值，而具有 h*（ n）值的路徑是 n 到 ti 的最佳路徑。由此可得 f*（ n）＝ g*（ n）＋ h*（ n）就表示 s→ ti 并約束通過節(jié)點 n 的最佳路徑的耗散值。當 n＝ s 時， f*（ s） =h*（ s）則表示 s→ ti無約束的最佳路徑的耗散值，這樣一來，所定義的 f（ n） =g（ n） +h（ n）就是對 f*(n)的一個估計。 g（ n）的值實際上很容易從到目前為止的搜索樹上計算出來，不必專門定義計算公式，也就是根據(jù)搜索歷史情況對 g*(n)作出估計，顯然有 g(n)≥ g*(n)。 h(n)則依賴于啟發(fā)信息，通常稱為啟發(fā)函數(shù)，是要對未來擴展的方向作出估計。算法 A 是按 f(n)遞增的順序來排列 OPEN 表的節(jié)點，因而優(yōu)先擴展 f（ n）值小的節(jié)點，體現(xiàn)了好的優(yōu)先搜索思想，所以算法 A是一個好的優(yōu)先的搜索策略。圖 n 之前的搜索圖，擴展 n 后新生成的子節(jié)點 m1（∈ {mj}）、 m2（∈ {mk}）、 m3（∈ {m1}）要分別計算其評價函數(shù)值： 東南大學成賢學院畢業(yè)論文 12 圖 搜索示意圖 f(m1)=g(m1)+h(m1) f(n， m2)=g(n， m2)+h(m2) f(n， m3)=g(n， m3)+h(m3) 然后按第 6 步條件進行指針設(shè)置和第 7 步重排 OPEN 表節(jié)點順序，以便確定下一次要擴展的節(jié)點[10]。 A* 算法中 h(x)的單調(diào)性限制 在 A* 算法中 , 每當要擴展一個節(jié)點時都要先檢查其子節(jié)點是否已在 OPEN 表或 CLOSED 表中 , 有時還需要調(diào)整 指向父節(jié)點的指針 , 這就增加了搜索的代價。如果對啟發(fā)函數(shù) h (x) 加上單調(diào)性限制 , 就可減少檢查及調(diào)整的工作量 , 從而減少搜索代價。 所謂單調(diào)性限制是指 h (x) 滿足如下兩個條件 : (1) h( Sg ) = 0 。 (2) 設(shè) xj 是節(jié)點 xi 的任意子節(jié)點 , 則有 h ( xi ) h ( xj )≤ c( xi , xj ) 其中 , Sg 是目標節(jié)點 。 c( xi , xj )是節(jié)點 xi 到其子節(jié)點 xj 的邊代價。 若把上述不等式改寫為 h ( xi )≤ h ( xj ) + c( xi , xj ) 那么我們就說 h服從一致性條件。這個條件陳述了順著搜索圖中的任何路徑，到達目標的最優(yōu)（剩余）代價的估價的減少不會大于該路徑弧代價。也就是說，在考慮了一個弧的已知代價后，啟發(fā)式函數(shù)在局部是一致的。這種一致性條件可以表示為如圖 。 一致性函數(shù)也暗示了當搜索樹中結(jié)點的值遠離開始節(jié)點時，它是單調(diào)非遞減的。設(shè) xi 和 xj 是由 A *在搜索樹上產(chǎn)生的兩個節(jié)點， xj是 xi的后繼。如果滿足一致性條件，就有 f(xj)≥ f(xi)。為了證明這個事實，我們從一致性條件開始： h(xj)≥ h (xi)c(xi， xj) 給上式兩邊都加上 g(xj），有： h(xj) + g(xj) ≥ h(xi) + g(xj) － c(xi， xj) 但是 g(xj) = g(xi) + c(xi xj) (我們可能會擔心 g(xj）會比這個值小，因為我們可能會順著其他的比通過 xi點代價更低的路徑到達 xj。但這樣一來，在搜索樹上 xj就不是 xi的后繼了 )。因此， 東南大學成賢學院畢業(yè)論文 13 f(xj) ≥ f(xi) 。因為這個原因，一致性條件（對 h）也常被稱為單調(diào)條件（對 f）。下面是一個涉及到一致性條件的重要定理。 圖 h ( xi ) h ( xj )≤ c( xi , xj ) 定理 1: 如果上的一致性條件被滿足，那么當 A *擴展節(jié)點 n時，它已經(jīng)找到了到達節(jié)點 n的一條最優(yōu)路徑。 證明：假設(shè) A *在隱式圖 G 中正在搜索從開始節(jié)點 n0 到目標節(jié)點的一條最佳路徑，它準備擴展一個打開的節(jié)點 n。設(shè) x =（ n0， n1， . . .， nl， nl+ 1， . . .， n = nk）是圖 G中從 n0到 n的一條最佳路徑的節(jié)點序列， n1 是 x上被 A*擴展的最后一個節(jié)點（參見圖 ）。因為 nl 是 x 上最后一個沒打開的節(jié)點，因此 nl + 1在 O P E N上是一個擴展候選者。 圖 驗證定理的圖 對任何節(jié)點 ni和它的后繼節(jié)點 ni+ 1，在 x中（到達 n的一條最優(yōu)路徑），我們有 g (ni+ 1) + h(ni+ 1) = g (ni) + c(ni， ni+ 1) +h (ni+ 1) ≥ g (ni) + h(ni) 。 當一致性條件滿足時，由≥關(guān)系的傳遞性可以得到 g (nj) +h (nj) ≥ g(ni) +h (ni) （對 x上的任何 ni和 nj (ij)） 在特殊情況下 ， g(n) +h (n) ≥ g (nl+ 1) + h(nl+ 1) ＝ f(nl+ 1) 因為 A*已經(jīng)發(fā)現(xiàn)了到達 nl+ 1的一條最佳路徑，使 g39。(nl+ 1) = g (nl+ 1) 但是由于 A*將要擴展節(jié)點 n而不是 nl+ 1，故必然有 f39。(n) =g39。 (n) + h39。(n) ≤ f39。(nl+ 1) 但是我們已經(jīng)有 f39。(nl+ 1) ≤ g(n) + h39。(n) 。 因此 g39。(n) ≤ g(n) 。 但是由于我們計算的方法暗示了 g39。(n) ≥ g( n )，故必然有 g39。(n) = g(n) 。 這表示了或者 nl+ 1 = n，或者我們必然已經(jīng)找到了到達節(jié)點 n的一些其他最佳路徑。證明完畢。 東南大學成賢學院畢業(yè)論文 14 一致性條件是很重要的，因為當它被滿足時， A*不再需要重定向指針（第 7步），搜索一個圖與搜索一個樹就沒有什么差別了。 滿足一致性條件時，可以為 A*的可接納性給出一個簡單直觀的論證。它是這樣的： 1) 的單調(diào)性暗示了搜索順著值增大的邊緣向外擴展。 2) 因此，被選擇的第一個目標節(jié)點就是有最小值的一個目標節(jié)點。 3) 對任何目標節(jié)點 ng， f39。 (ng) = g39。(ng)（這里，我們用了這樣的事實，如果函數(shù)是一致的，它也將絕不會比真正的 h函數(shù)大）。 4) 因此，第一個被選擇的目標節(jié)點將是有最小值的目標節(jié)點。 5) 作為定理 1的一個結(jié)論，無論何時（特別地）當一個目標節(jié)點 ng被選擇擴展時，我們已找到了到達那個目標節(jié)點的一個最佳路徑。即 g39。( ng) = g (ng)。 6) 這樣，第一個被選擇的目標節(jié)點將是算法發(fā)現(xiàn)的最佳路徑的目標節(jié)點。 很多啟發(fā)式函數(shù)滿足一致性條件。例如， 8 數(shù)碼問題中的“不在正確位置的數(shù)碼個數(shù)”函數(shù)就是一個例子。當一個啟發(fā)式函數(shù)不滿足一致性條件，但其他方面是可以接受的條件時，那么我們能在搜索期間調(diào)整該函數(shù) 使它滿足一致性條件。 假如，在 A *的每一步，我們檢查剛剛擴展的節(jié)點 n 的后繼的值。任何值小于 h39。(n)值的節(jié)點減去從 n到這個節(jié)點的弧代價就會得到它們調(diào)整后（在搜索過程中）的 h39。值，這樣它們就剛好等于 h39。(n)值減去那段弧代價的所得值。 通過上述論證， 就可看出節(jié)點 xi 到目標節(jié)點最優(yōu)費用的估價不會超過從 xi 到其子節(jié)點 xj 的邊代價加上從 xj 到目標節(jié)點最優(yōu)費用的估價。所以 , 對于存在最優(yōu)解的問題 , 在利用 A* 算法時 , 加上 h ( x ) 的單調(diào)性限制 ( 即 h ( x ) ≤ h * ( x) ) , 就可保證 能找到最優(yōu)解 [3][11]。 本章小結(jié) 本章首先介紹了 A算法及 A*算法的定義，然后對 A*算法具體描述，最后，分析 A*算法，對 A*算法的性能做了測評， 并用定理 證明了 A*算法確實能尋得最優(yōu)解。 東南大學成賢學院畢業(yè)論文 15 第四章 游戲 尋徑 系統(tǒng) 設(shè)計與實現(xiàn) 開發(fā)背景 現(xiàn)在，全球電腦游戲產(chǎn)業(yè)已經(jīng)形成了一個巨大市場，游戲產(chǎn)業(yè)有著豐厚的利潤和光輝的前景。在目前已上市的計算機游戲中，已經(jīng)應(yīng)用了很多人工智能技術(shù)。游戲開發(fā)中的人工智能正處于一場革命之中，并將迅速得到發(fā)展并推動整個游戲產(chǎn)業(yè)的飛速 發(fā)展。而游戲路徑搜索是游戲人工智能的基礎(chǔ)和重要組成部分，應(yīng)用該技術(shù)以后，應(yīng)該能夠使非玩家角色在游戲中的運動滿足以下幾個條件： 逼真：移動最重要的方面就是產(chǎn)生像人或者動物那樣的非玩家角色。因為移動是最常見的動作，所以需要特別注意增加其真實感。 高效：一個能夠提供智能移動功能且被廣泛使用的系統(tǒng)在處理器執(zhí)行時間上一定是相當快的。 可靠：非玩家角色在游戲進