余博文 華北電力大學(xué)

1 引言

目前，有很多搜索圖的最短路徑，包括：迪克斯特拉算法、廣度優(yōu)先搜索、深度優(yōu)先搜索、回溯法等方法。在這些算法中，迪克斯特拉算法可以找到最短的路徑，但其搜索單源最短路徑的效率為O（n2）；廣度優(yōu)先搜索可以找到到達(dá)終點(diǎn)的最短步數(shù)，不一定為最短的路徑；深度優(yōu)先搜索為遞歸求解算法的非遞歸改進(jìn)；而回溯法方法和深度優(yōu)先搜索在短時(shí)間之內(nèi)是無法實(shí)現(xiàn)的。

上述算法可歸為盲目搜索和啟發(fā)式搜索。啟發(fā)式搜索一般要優(yōu)于盲目搜索，但不可過于追求更多的甚至完整的啟發(fā)信息。此次設(shè)計(jì)所采用的啟發(fā)式搜索，其啟發(fā)信息基于廣度優(yōu)先搜索，恰到好處，搜索在迪克斯特拉算法的基礎(chǔ)上進(jìn)行剪枝。

本文的意義在于完善一些關(guān)于基于矩陣（二維數(shù)組）存儲(chǔ)的圖類型的數(shù)據(jù)結(jié)構(gòu)，進(jìn)行最短路徑的搜索，使得針對(duì)于該圖類型數(shù)據(jù)結(jié)構(gòu)的算法在構(gòu)造、遍歷、修改等方面的操作實(shí)現(xiàn)達(dá)到了高時(shí)間效率和高空間效率，這是跟傳統(tǒng)圖類型數(shù)據(jù)結(jié)構(gòu)相比較而言最大的區(qū)別。針對(duì)于無向圖最短路徑的搜索，突破了“在遞歸搜索、深度優(yōu)先搜索、廣度優(yōu)先搜索時(shí)對(duì)整個(gè)圖各個(gè)結(jié)點(diǎn)之間的邊要保持長(zhǎng)度相同”的限制，比起在傳統(tǒng)的迪克斯特拉算法上，運(yùn)用A*算法搜索圖的最短路徑，找到了最佳的啟發(fā)函數(shù)，進(jìn)而找到了最佳的評(píng)估函數(shù)，并結(jié)合迪克斯特拉算法，實(shí)現(xiàn)了對(duì)迪克斯特拉算法時(shí)間效率上的優(yōu)化。

例如，在電腦鼠迷宮搜索的位置過程中，最好的方法就是要用A*算法去搜索圖的最短路徑。因此，又快又能正確的找到最短路徑則是本次設(shè)計(jì)的關(guān)鍵。

通過本文所提供的啟發(fā)函數(shù)，展示最短路徑的準(zhǔn)確搜索，即利用A*算法探究最短路徑過程的一個(gè)生動(dòng)實(shí)例。本文與其他版本的最主要的區(qū)別，就是在電腦鼠移動(dòng)到期望的位置之時(shí)，所走的路徑不是其他版本的只有向上移（↑）、向下移（↓）、向左移（←）、向右移（→）四個(gè)方向的走法，而且還包括了向左上移）、向右上移）、向左下移）和向右下移（）四個(gè)方向。

但是，在進(jìn)行迷宮搜索的過程中，還需考慮以下情況。

(1)當(dāng)上（↑）、下（↓）、左（←）、右（→）四個(gè)相鄰的格子位置可以到達(dá)時(shí)，電腦鼠可直接移動(dòng)到此時(shí)的目標(biāo)位置，否則電腦鼠不可到達(dá)相應(yīng)的目標(biāo)位置。）、向左下移和向右下移）四個(gè)方向〕時(shí)，如果斜方向的左右

圖1 .1 相鄰四格子可達(dá)

圖1 .2 目標(biāo)位置不可達(dá)

圖1 .3 斜方向可達(dá)，左右方向均可達(dá)

圖1 .4 斜方向可達(dá)，左右有一方不可達(dá)

(3)左右均不可達(dá)，則電腦鼠需繞道移動(dòng)，不可穿過兩個(gè)不可達(dá)位置而移動(dòng)。

圖1 .5 斜方向可達(dá)，左右方向均不可達(dá)，需繞道移動(dòng)

2 A*算法與啟發(fā)式的設(shè)計(jì)

2.1 啟發(fā)式搜索

在搜索最短路徑時(shí)，如果把當(dāng)前地圖的每一個(gè)格子及起點(diǎn)和終點(diǎn)都作為一個(gè)結(jié)點(diǎn)，把通道作為邊，則該地圖可以由一個(gè)有向圖來表示。那么，搜索最短路徑其實(shí)就是從該有向圖的初始結(jié)點(diǎn)（起點(diǎn)）出發(fā)，尋找目標(biāo)結(jié)點(diǎn)（終點(diǎn)）的問題。抽象地來看，上述問題都是在某個(gè)有向圖中尋找目標(biāo)或路徑的問題。通常，把這種描述問題的有向圖稱為狀態(tài)空間圖（簡(jiǎn)稱狀態(tài)圖），用圖的概念來描述狀態(tài)空間。

狀態(tài)圖中的結(jié)點(diǎn)代表問題中的一種格局，稱問題中的一個(gè)狀態(tài)。邊表示結(jié)點(diǎn)之間的某種聯(lián)系。在狀態(tài)圖中，從初始結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的一條路徑，或者所找的目標(biāo)結(jié)點(diǎn)，就是相應(yīng)問題的一個(gè)解。根據(jù)解題需要，路徑解可以表示為邊的序列或結(jié)點(diǎn)的序列。搜索最短路徑的解就是結(jié)點(diǎn)序列。

狀態(tài)空間可用有向圖來描述，圖的結(jié)點(diǎn)表示問題的狀態(tài)，圖的弧表示狀態(tài)之間的關(guān)系有向圖就是求解問題的步驟。初始狀態(tài)對(duì)應(yīng)于實(shí)際問題的已知信息，是圖中的根結(jié)點(diǎn)。圖還可以定義目標(biāo)條件，目標(biāo)可以描述成一種狀態(tài)。在問題的狀態(tài)空間描述中，尋找從一種狀態(tài)轉(zhuǎn)換為另一種狀態(tài)的某個(gè)操作序列就等價(jià)于在一個(gè)圖中尋找某一路徑。各種操作的執(zhí)行費(fèi)用是不同的。

搜索策略有兩種基本方式：盲目搜索和啟發(fā)式搜索。所謂盲目搜索是指在不具有對(duì)特定問題的任何有關(guān)信息的條件下，按固定的步驟進(jìn)行的搜索。所謂啟發(fā)式搜索則是考慮特定問題領(lǐng)域可應(yīng)用的知識(shí)，動(dòng)態(tài)地確定操作步驟。優(yōu)秀選取較合適的操作，盡量減少不必要的搜索，以求盡快地到達(dá)結(jié)束狀態(tài)，提高搜索效率。在盲目搜索中，由于沒有可參考的信息，因此只要能匹配的操作都需運(yùn)用，這會(huì)搜索出更多的狀態(tài)，生成較大的狀態(tài)空間顯式圖；而啟發(fā)式搜索中，如具有較多甚至完整的啟發(fā)信息，雖然只需運(yùn)用少量的操作，只生成較小的狀態(tài)空間顯式圖，能將搜索引向一個(gè)解答，但是，每使用一個(gè)操作便需做更多的計(jì)算與判斷。

A*啟發(fā)式搜索法的基本特點(diǎn)是，如何尋找并設(shè)計(jì)一個(gè)與問題有關(guān)的g(n)（從初始結(jié)點(diǎn)到n 結(jié)點(diǎn)的實(shí)際代價(jià)）、h(n)（從n 結(jié)點(diǎn)到目的結(jié)點(diǎn)的最佳路徑的估計(jì)代價(jià)）及構(gòu)造出估價(jià)函數(shù)f(n)=g(n)＋h(n)，然后以f(n)的大小來排列待擴(kuò)展?fàn)顟B(tài)的次序，每次選擇f(n)值最小者進(jìn)行擴(kuò)展。算法中有一步是根據(jù)某些啟發(fā)信息來排列open 表，它既不同于寬度優(yōu)先所使用的“隊(duì)列”，也不同于深度優(yōu)先所使用的“堆棧”，而是一個(gè)按狀態(tài)的啟發(fā)估價(jià)函數(shù)值的大小排列的一個(gè)“表”。進(jìn)入open 表的狀態(tài)不是簡(jiǎn)單地排在隊(duì)尾（或隊(duì)首），而是根據(jù)其估價(jià)的大小插入到表中合適的位置，每次從表中優(yōu)先取出啟發(fā)估價(jià)函數(shù)值最小的狀態(tài)加以擴(kuò)展。如果將寬度優(yōu)先（或深度優(yōu)先）看作特殊的A*算法，則可視“隊(duì)列”（或“堆棧”）為特殊的優(yōu)先隊(duì)列，其啟發(fā)信息比較函數(shù)返回為固定值（如果隊(duì)列為false，則棧為true；反之亦然）。由是觀之，open 表必須保證在啟發(fā)信息相同的情況下，保證表內(nèi)元素的穩(wěn)定性；啟發(fā)信息不同，則自小向大排列。例如，根據(jù)字符串長(zhǎng)度，對(duì)數(shù)組中的字符串元素進(jìn)行排序。字符串?dāng)?shù)組為：['London', 'Berlin', 'Paris', 'Washington', 'Tokyo', 'Peking', 'Detroit', 'Texas', 'Orleans', 'New York']。

關(guān)于排序的方法有很多種。但這里提及該例是通過將字符串放入一個(gè)優(yōu)先隊(duì)列性質(zhì)的集合中，然后依次取出優(yōu)先隊(duì)列中的各元素，直到優(yōu)先隊(duì)列為空。顯然，排序的關(guān)鍵碼是字符串的長(zhǎng)度，不同于以往的按字典序列排序。則將該字符串的關(guān)鍵碼提取出來，則可以表示為：[6, 6, 5, 10, 5, 6, 7, 5, 6, 8]。通過該例是為了說明上文提到的排序的穩(wěn)定性。如果根據(jù)字符串的長(zhǎng)度排序，為了保證穩(wěn)定性，則該字符串?dāng)?shù)組排序完的結(jié)果只有唯一的一種：Paris、Tokyo、Texas、Lond on、Berlin、Peking、Detroit、Orleans、New York、Washington。提取出其關(guān)鍵碼，則為：[5, 5, 5, 6, 6, 6, 7, 7, 8, 10]。同樣關(guān)鍵碼為5 的“Paris”和“Tokyo”，如果順序顛倒，結(jié)果便成 為：['Tokyo', 'Paris', 'Texas', 'London', ……]，則 所 得 的 排序結(jié)果有違排序的穩(wěn)定性。

這里之所以強(qiáng)調(diào)排序的穩(wěn)定性，是因?yàn)槿绻捎昧嘶诓环€(wěn)定排序的優(yōu)先隊(duì)列進(jìn)行數(shù)據(jù)的存儲(chǔ)，那么所搜索出來的路徑雖然可以保證步數(shù)最少，但是所經(jīng)過的距離卻不一定最短，所行走的路徑出現(xiàn)了“毛刺”。即在該拐彎的地方卻沒有拐彎，而在不必拐彎的地方卻出現(xiàn)了拐彎。這一現(xiàn)象尤其在只用寬度優(yōu)先搜索時(shí)體現(xiàn)得更加明顯。此外，選擇不當(dāng)?shù)膯l(fā)信息亦會(huì)出現(xiàn)“毛刺”。圖2.1、2.2 為(1, 0)到(1, 4)的步數(shù)演示：

圖2.1 正確的最短路徑

圖2.2 出現(xiàn)“毛刺”的路徑

本文實(shí)驗(yàn)為了保證優(yōu)先隊(duì)列的穩(wěn)定性，因而采用了可插入元素和僅可以每次取出一個(gè)元素，而該元素位于二叉樹中序遍歷的第一個(gè)輸出的元素，而所有元素的順序是已經(jīng)排好順序的二叉排序樹作為實(shí)現(xiàn)A*算法中的open 表。

2.2 啟發(fā)式信息的設(shè)計(jì)

常見的獲取啟發(fā)信息的方法有計(jì)算“歐幾里得”距離、“曼哈頓”距離、“切比雪夫”距離。

“歐幾里得”(x1,y1)到(x2,y2)的距離計(jì)算公式：√(x1-y1)2＋(x2-y2)2；“曼哈頓”(x1,y1)到(x2,y2)的距離計(jì)算公式：|x1-x2|＋|y1-y2|；“切比雪夫”(x1,y1）到(x2,y2)的距離計(jì)算公式：max{|x1-x2|,|y1-y2|}；然而，本文使用的啟發(fā)信息，從(x1,y1)到(x2,y2)的距離 計(jì) 算 公 式 為：BFS((x1,y1),(x2,y2))；其 中，BFS((x1,y1),(x2,y2)) 表 示在圖中，(x1,y1)通過寬度優(yōu)先搜索到(x2,y2)所經(jīng)過的結(jié)點(diǎn)的最少個(gè)數(shù)，即從(x1,y1)到(x2,y2)的最少步數(shù)。

證明啟發(fā)式函數(shù)的精準(zhǔn)度：以沒有任何障礙物的圖為例，假設(shè)從圖中的某一點(diǎn)進(jìn)行遍歷，計(jì)算“歐幾里得”距離、“曼哈頓”距離、“切比雪夫”距離分別如圖2.3、圖2.4 和圖2.5。為了方便描述，可以將圖2.3簡(jiǎn)記為矩陣M、將圖2.4 簡(jiǎn)記為矩陣C、將圖2.5 簡(jiǎn)記為矩陣E。

圖2.3 以“曼哈頓”距離為啟發(fā)信息（記“М”）

圖2.4 以“切比雪夫”距離為啟發(fā)信息（記“С”）

圖2.5 以“歐幾里得”距離為啟發(fā)信息（記“Е”）

比較各種啟發(fā)信息的準(zhǔn)確度是根據(jù)以某一點(diǎn)為中心進(jìn)行寬度優(yōu)先搜索，各個(gè)結(jié)點(diǎn)記錄距出發(fā)點(diǎn)已走的步數(shù)。此時(shí)，將通過寬度優(yōu)先遍歷所得到的矩陣記為В。所以，在八個(gè)方向的走法規(guī)則下，可以得到一個(gè)啟發(fā)信息如圖2.4 的矩陣С，則В-С=Ф，矩陣(В-Е)較矩陣(В-М)有更多取絕對(duì)值的元素接近于0。那么得出結(jié)論：精準(zhǔn)度(В)≥精準(zhǔn)度(С)＞精準(zhǔn)度(Е)＞精準(zhǔn)度(М)。

同理，如果是四個(gè)方向的走法，可以得到一個(gè)啟發(fā)信息如圖2.3的矩陣М，

則В-М=Ф。那么矩陣В 與其他矩陣做差，則矩陣(В-Е)較矩陣(В-С)有更多取絕對(duì)值的元素接近于0。那么得出結(jié)論：精準(zhǔn)度(В)≥精準(zhǔn)度(М)＞精準(zhǔn)度(Е)＞精準(zhǔn)度(С)。

不同的距離計(jì)算方法，適用于在不同的走法規(guī)則。假設(shè)只允許有向上移（↑）、向下移（↓）、向左移（←）、向右移（→）四個(gè)方向的走法，那么“曼哈頓”距離作為啟發(fā)信息的精準(zhǔn)度將比“切比雪夫”距離和“歐幾里得”距離更完美；但如果走法規(guī)則如本作一樣允許八個(gè)方向的移動(dòng)，那么“切比雪夫”距離作為啟發(fā)信息的精準(zhǔn)度將比“曼哈頓”距離和“歐幾里得”距離更完美。

2.3 核心數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)

2.3.1 鄰接表的設(shè)計(jì)

此次采用的鄰接表，并非傳統(tǒng)意義上用鏈表實(shí)現(xiàn)，而是僅用一個(gè)字節(jié)就表示一個(gè)結(jié)點(diǎn)的鄰接結(jié)點(diǎn)。

圖2.6 比特位表示的鄰接表

該鄰接表的設(shè)計(jì)思想，是將每一個(gè)結(jié)點(diǎn)抽象為表示分支節(jié)點(diǎn)前進(jìn)方向的各位字節(jié)。當(dāng)某個(gè)結(jié)點(diǎn)的某一邊與其他結(jié)點(diǎn)連接時(shí)，則對(duì)應(yīng)的位為1，否則該邊不與其他結(jié)點(diǎn)相連，則對(duì)應(yīng)的位為0。這里，首先要定義一個(gè)方向列表，分別（例如）此順序存儲(chǔ)方向坐標(biāo){向右（0, 1）, 向 右 下（1,1）, 向 下（1,0）, 向 左 下（1,-1）, 向 左（0,-1）, 向 左 上（-1,-1）,向上（-1,0）, 向右上（-1,1）}。于是，字節(jié)的某一位（如第0 位）如果為1，則表示該結(jié)點(diǎn)右方向有結(jié)點(diǎn)；為0 則右方向無鄰接結(jié)點(diǎn)。如果所有結(jié)點(diǎn)均可達(dá)，且呈網(wǎng)格狀分布，則鄰接表（掩碼）如下：

圖2 .7 特殊的“鄰接表”(掩碼)

2.3.2 closed 表

這里所謂的closed 表指代關(guān)于某一結(jié)點(diǎn)在遍歷之時(shí)是否被訪問的標(biāo)記，相對(duì)應(yīng)于所有的結(jié)點(diǎn)，將是否被標(biāo)記的屬性專門提取出來的布爾類型變量所構(gòu)成的表稱為“closed”表。

在本文A*算法路徑規(guī)劃中，對(duì)于結(jié)點(diǎn)是否被訪問，每個(gè)結(jié)點(diǎn)有專門標(biāo)記訪問情況的變量（屬性）。之所以這樣做，是因?yàn)橥ㄟ^標(biāo)記結(jié)點(diǎn)是否被訪問的動(dòng)作，來觀察整張圖的遍歷狀態(tài)，通過界面顯示結(jié)點(diǎn)是否被標(biāo)記。

和一般得求最短路徑方法不同的是，這里的所有結(jié)點(diǎn)訪問標(biāo)記先初始化為“true”。然后通過從某一結(jié)點(diǎn)開始進(jìn)行寬度優(yōu)先搜索，在記錄啟發(fā)信息的同時(shí)，也要把已經(jīng)記錄啟發(fā)信息的結(jié)點(diǎn)訪問狀態(tài)改為“false”。寬度優(yōu)先搜索在遇到目標(biāo)結(jié)點(diǎn)之時(shí)則會(huì)停止遍歷，從而使一些啟發(fā)信息相同，但真正的最短路徑不需要經(jīng)過的結(jié)點(diǎn)排除在外，達(dá)到“剪枝”的效果。這樣，在進(jìn)行最短路徑搜索的時(shí)候，一些沒有經(jīng)過寬度優(yōu)先遍歷的結(jié)點(diǎn)便也會(huì)標(biāo)記為“true”，以免不可能出現(xiàn)的狀態(tài)空間進(jìn)入優(yōu)先隊(duì)列，從而增加了搜索量。

圖2.8 從(1, 1)到(1, 2)的closed 表訪問情況 圖2.9 從(1, 1)到(0, 2)的closed 表訪問情況

假設(shè)求(1,1)到(1,2)，從右方向開始遍歷，則只有一個(gè)結(jié)點(diǎn)訪問，周圍七個(gè)均未訪問，表示只有(1,1)和(1,2)兩個(gè)結(jié)點(diǎn)需要進(jìn)入優(yōu)先隊(duì)列；從(1,1)到(0,2)，同樣從右方向開始遍歷，則周圍的八個(gè)結(jié)點(diǎn)均被訪問，那么，則需要讓(1,1)及其周圍的八個(gè)結(jié)點(diǎn)一并進(jìn)入優(yōu)先隊(duì)列。

3 A*搜尋最短路徑算法

3.1 A*搜尋算法

A*搜尋最短路徑算法流程圖如圖3.1。

圖2.10 A*搜尋最短路徑算法流程圖

A*搜尋算法的代碼如下：

算法1：A*搜尋算法

1.unsigned char search Path(int src X, int srcY, int d st X, int dstY) {

2.int i, curX, curY, surX, surY;

3. float surG;

4.BinarySortTree open; //優(yōu)先隊(duì)列（Open 表）

5.Close *p;

6.bst_Initial(&open); //優(yōu)先隊(duì)列初始化

7.closeInitial(dst X, dstY, src X, srcY); // 地 圖Close 表 初始化配置

8.close[dstX][dstY].visited = 1;

9.bst_Add Item(&open, close, dstX, dstY, 0); // 初 始 節(jié) 點(diǎn)入隊(duì)

10.while (!bst_IsEmpty(&open)) { //優(yōu)先隊(duì)列為空？

11.p = bst_GetItem(&open); //取出估價(jià)函數(shù)最小節(jié)點(diǎn)

12.curX = p-＞currentNode-＞X;

13.curY = p-＞currentNode-＞Y;

14.if (p-＞H == 0) { //啟發(fā)信息為0？

15.bst_Destroy(&open);

16.return 1;

17.}

18.for (i = 0; i ＜ 8; i++) { //遍歷鄰接節(jié)點(diǎn)

19.if (! (p-＞currentNode-＞sur & (1 ＜＜ i))) continue;

20.surX = curX + direction[i].X;

21.surY = curY + direction[i].Y;

22.if (!close[sur X][sur Y].visited && close[surX][sur Y].H == close[curX][curY].H - 1) {

23.close[surX][surY].visited = 1;

24.close[surX][surY].from = p;

25.close[surX][surY].orientation = (i + 4) % 8;

26.sur G = p-＞G + (f loat)(i & 1 ? sqrt(2.0f) ： 1); // 記錄代價(jià)信息

27.bst_Add Item(&op en, close, surX, sur Y, sur G); // 將啟發(fā)信息比當(dāng)前節(jié)點(diǎn)小的鄰接節(jié)點(diǎn)入隊(duì)

28.} // end if

29.} // end for

30.} // end while

31.bst_Destroy(&open);

32.return 0;33. }

特別的，第22步是根據(jù)啟發(fā)式信息特點(diǎn)，若當(dāng)前啟發(fā)信息為n（≥1），則下一步的啟發(fā)信息必為n-1，這樣才做到對(duì)傳統(tǒng)的迪克斯特拉算法優(yōu)化。這是與其他啟發(fā)信息相比，而所具有的不同之處。在找到是否存在最短路徑后，可以通過起始結(jié)點(diǎn)如鏈表索引般來搜索出整個(gè)路徑。

算法2：路徑索引

1. int symbolize Map(int src X, int src Y, int dst X, int dstY) {

2.Close *p;

3.int step = 0;

4.p = getPath(src X, srcY, dstX, dstY); // 獲取最短路徑的終止節(jié)點(diǎn)

5.if (p == NULL) return 0;

6.while (p-＞from != NULL) { //轉(zhuǎn)置路徑

7.w orld Terrain[p-＞current Nod e-＞X][p-＞current Nod e-＞Y].value =

8.S T E P + 1 + c l o s e[p-＞c u r r e n t N o d e-＞X][p-＞currentNode-＞Y].orientation;

9.p rin t f("（%d，%d） → ", p-＞cu r ren t Nod e-＞X, p-＞currentNode-＞Y);

10.p = p-＞from;

11.step++;

12.}

13.p r i n t f("（%d，%d） ", p-＞c u r r e n t N o d e-＞X, p-＞currentNode-＞Y);

14.world Terrain[srcX][srcY].value = SOURCE;

15. world Terrain[dst X][dstY].value = DESTINATION;

16.return step;17. }

例如，搜索在圖上從（0,0）點(diǎn)到（2,2）點(diǎn)上的最短路徑。圖為（1表示障礙物，0 表示可到達(dá)結(jié)點(diǎn)）：

圖2.11 搜索樹所用的地圖

圖2.12 以當(dāng)前位置到達(dá)目標(biāo)結(jié)點(diǎn)所需步數(shù)作為啟發(fā)信息的狀態(tài)空間示意圖

圖2.13 傳統(tǒng)的曼哈頓距離作為啟發(fā)信息的狀態(tài)空間示意圖

3.2 實(shí)驗(yàn)比較

為了比較啟發(fā)信息對(duì)最終最短路徑搜索結(jié)果的影響，這里分別演示了以“曼哈頓”距離作為啟發(fā)信息，和基于寬度優(yōu)先確立步數(shù)的啟發(fā)信息進(jìn)行對(duì)比。其中，最短距離是以“迪克斯特拉”算法作為標(biāo)準(zhǔn)的。通過基于各種啟發(fā)信息搜索出來的路徑與迪克斯特拉算法計(jì)算出得到的最短距離進(jìn)行比較，來判別出比較啟發(fā)信息的精準(zhǔn)度（迪克斯特拉算法所得到的代價(jià)誤差小于10-6）。

例如，求(0,0)到(14,19)的最短路徑，如果以“曼哈頓”距離為啟發(fā)信息，則可以求得。而求從(14,19)到(0,0)的最短路徑，“曼哈頓”距離所用的最短步數(shù)為22 步。實(shí)驗(yàn)結(jié)果的詳細(xì)記錄如表3.1。

圖3.1 以寬度優(yōu)先為啟發(fā)式求出的從（0,0）到（14,19）點(diǎn)最短路徑

圖3.2 以寬度優(yōu)先為啟發(fā)式求出的從（14,19）到（0,0）點(diǎn)最短路徑

表3 .1 路徑結(jié)果比較

由于該圖為無向圖，所以從起點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度與從終點(diǎn)到起點(diǎn)的最短路徑長(zhǎng)度是相同的。但最短路徑可以不同。而實(shí)際上，最少步數(shù)可以通過寬度優(yōu)先求得，此時(shí)應(yīng)為21步。最短路徑不一定唯一，但最短路徑的最少步數(shù)和最短路徑長(zhǎng)度一定是唯一的。如果一條路徑的最少步數(shù)與正確路徑的所用最少步數(shù)不同，則該路徑所經(jīng)過的最短路徑長(zhǎng)度必為錯(cuò)誤的。

而使用本文以寬度優(yōu)先確立步數(shù)的啟發(fā)信息進(jìn)行最短路徑搜索，則不會(huì)出現(xiàn)像“曼哈頓”距離那樣路徑的長(zhǎng)度不相同的現(xiàn)象。這是由于：當(dāng)圖的所有邊的權(quán)重均相同之時(shí)，可以利用寬度優(yōu)先搜索求取兩個(gè)結(jié)點(diǎn)之間的最短路徑。這一原理廣泛地應(yīng)用于四方向走法規(guī)則的情況，典型的例子就是迷宮求解。如果如本文允許八個(gè)方向的走法，向左上移（）、向右上移（）、向左下移和向右下移四個(gè)方向與向上移（↑）、向下移（↓）、向左移（←）、向右移（→）四個(gè)方向所花費(fèi)的代價(jià)是不同的（前者為√2，后者為1）。

此外，有時(shí)候以“曼哈頓”距離為啟發(fā)信息根本搜索不到最短路徑，如表3.1 從(14,0)到(14,19)的結(jié)果。

如果想利用兩次以“曼哈頓”距離為啟發(fā)信息的搜索的結(jié)果取最小值長(zhǎng)度的路徑作為最終結(jié)果返回，即將其起點(diǎn)與終點(diǎn)顛倒之后再進(jìn)行搜索，以“曼哈頓”距離為啟發(fā)信息的搜索依然搜索不到最短路徑，如表3.1 從(14,19)到(14,0)的結(jié)果。

有時(shí)，即使以“曼哈頓”距離為啟發(fā)信息的路徑可以找到最少步數(shù)，但也不一定是最短距離，如表3.1 從(0,0)到(12,19)的結(jié)果。

4 結(jié)論

綜上所述，本文介紹的A*算法所求的啟發(fā)式信息方法其精準(zhǔn)度要高于“曼哈頓”距離。但具體要使用哪種啟發(fā)式信息，還要看具體情況而定。如果圖的初始化過程比較簡(jiǎn)單，則搜索的過程將會(huì)耗時(shí)較長(zhǎng)；而圖的初始化過程，例如啟發(fā)信息的確立做的比較徹底的話，那么在搜索過程中，可以以接近于依次訪問最短路徑結(jié)點(diǎn)的效率搜索出正確結(jié)果。