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

　　

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