湯 偉，趙 靜，古 嬋

（陜西科技大學(xué)電氣與控制工程學(xué)院，陜西西安 710021）

迷宮問題一直是數(shù)據(jù)結(jié)構(gòu)和圖形學(xué)領(lǐng)域的經(jīng)典問題［1］，其求解的方法是從入口到出口的多條路徑中找尋一條最短路徑，即最優(yōu)路徑。傳統(tǒng)迷宮的求解有深度優(yōu)先搜索、廣度優(yōu)先搜索［2］等算法，該類方法雖應(yīng)用廣泛，但存在著許多不足。如深度優(yōu)先搜索［3－4］是通過堆棧實(shí)現(xiàn)的，雖能找到一條通路，但因其搜索方法的原因，不能保證是最短路徑。廣度優(yōu)先搜索［5］是通過隊(duì)列或列表來實(shí)現(xiàn)的，該方法雖然能找到最短通路，但需層層推進(jìn)且需要的存儲(chǔ)空間大、搜索時(shí)間長(zhǎng)，從而導(dǎo)致效率較低。以上兩種求解方法會(huì)隨著迷宮規(guī)模及復(fù)雜度的增大，計(jì)算量呈指數(shù)性增加。隨后出現(xiàn)了一些仿生智能算法［6］如遺傳算法［7－8］、蟻群算法［9－11］、粒子群算法［12－13］等。遺傳算法是通過設(shè)計(jì)編碼、適應(yīng)值函數(shù)、遺傳操作和在演化過程中對(duì)基因進(jìn)行“改良”［14］來實(shí)現(xiàn)。該算法可以求得迷宮的最短路徑，但是否為最短路徑還有待考證。蟻群算法是多只螞蟻通過不斷的自適應(yīng)調(diào)整信息素協(xié)作完成，采用的是概率搜索的方法，需要較長(zhǎng)的計(jì)算時(shí)間且容易出現(xiàn)停滯現(xiàn)象［15］。粒子群算法是一種基于群體協(xié)作的隨機(jī)搜索算法，是對(duì)鳥類集群覓食以及魚類集群行為的模仿［16］，該算法易陷入局部最優(yōu)。仿生智能算法是用并行處理的方法來解決大規(guī)模問題，該類算法可以得到一個(gè)很好的解，但大多是近似最優(yōu)解且是否為最短路徑還有待理論考證。還有學(xué)者提出了A?算法，它將啟發(fā)式函數(shù) BFS和常規(guī) Dijkstra算法結(jié)合在一起［17－19］，是一種在工作空間中求解最短路徑的全局搜索方法。A?算法相較于傳統(tǒng)算法尋路時(shí)間減少，相較于仿生智能算法，它能找到最優(yōu)路徑，但由于該算法自身的限制，存在冗余點(diǎn)多、內(nèi)存開銷大、尋路時(shí)間長(zhǎng)、僅保留單條最短路徑等的不足。

針對(duì)以上存在的不足，本文提出了一種基于自動(dòng)機(jī)模型的求解方法。首先，在迷宮的可行路徑上用自動(dòng)機(jī)建模，并結(jié)合自動(dòng)機(jī)結(jié)構(gòu)特性進(jìn)行節(jié)點(diǎn)簡(jiǎn)化。其次對(duì)簡(jiǎn)化后的模型求最短。最后通過MATLAB仿真，結(jié)果表明該算法不僅能夠快速有效地求解迷宮最優(yōu)路徑，而且也解決了以往算法存在的不足，如傳統(tǒng)迷宮耗時(shí)過長(zhǎng)、冗余點(diǎn)過多等問題。

1 理論回顧

1.1 迷宮問題的描述

如圖1所示，長(zhǎng)為m寬為n的網(wǎng)格區(qū)域（1≤m≤10，1≤n≤10）表示迷宮，其中黑色網(wǎng)格表示墻，為不可行區(qū)域；白色網(wǎng)格表示通道，為可行區(qū)域。迷宮求解就是在可行區(qū)域的多條路徑中尋找一條通路，移動(dòng)方格最少的通路即最優(yōu)路徑。

圖1 迷宮［20］

1.2 自動(dòng)機(jī)

自動(dòng)機(jī)［21］是描述正規(guī)語言的一種方法，它的特點(diǎn)是采用狀態(tài)子集的可達(dá)性來定義語言。同時(shí)包含的狀態(tài)和事件等基本要素可用來描述離散事件動(dòng)態(tài)系統(tǒng)［22］（DEDS）。

自動(dòng)機(jī)用五元組 G ＝ （Y，Σ，η，y0，Ym） 來表示，其中：Y為有限狀態(tài)集合，y是 G的一個(gè)狀態(tài)，?y∈Y；Σ為有限事件集合；η為狀態(tài)轉(zhuǎn)移函數(shù)η：Y×Σ→Y；y0∈Y為初始狀態(tài)；Ym∈Y為終態(tài)集。自動(dòng)機(jī)G產(chǎn)生的語言L（G）定義為使?fàn)顟B(tài)轉(zhuǎn)移函數(shù)η（σ，y0）有定義的輸入符號(hào)串σ∈Σ的一個(gè)集合，也即

自動(dòng)機(jī)G的標(biāo)識(shí)的語言Lm（G）定義為使?fàn)顟B(tài)轉(zhuǎn)移函數(shù)η（σ，y0）屬于標(biāo)識(shí)狀態(tài)集Ym∈Y的輸入符號(hào)串σ∈Σ的一個(gè)集合，也即

有限自動(dòng)機(jī)G是整齊的，則需滿足以下條件：

（1）有限狀態(tài)集Y的任一狀態(tài)均為從初態(tài)可達(dá)。

（2）有限自動(dòng)機(jī)G產(chǎn)生的語言L（G）的任一符號(hào)串，均可構(gòu)成自動(dòng)機(jī)G的標(biāo)識(shí)語言Lm（G）中某個(gè)符號(hào)串的前綴。

1.3 Dijkstra 算法

Dijkstra算法是一種典型的求單源最短路徑算法，用于計(jì)算有向圖中一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑［23－24］。 該算法在求最短路徑時(shí)，首先需要設(shè)置距離向量 d［］，保存路徑的向量 p［］，d［］用于保存入口到分支節(jié)點(diǎn)的向量，p［］用于保存最短路徑上某一分支點(diǎn)的前驅(qū)節(jié)點(diǎn)。傳統(tǒng)算法通常只能求單條最短路徑，而要求多條最短路徑，則需讓每一個(gè)節(jié)點(diǎn)都維護(hù)自己的前驅(qū)節(jié)點(diǎn)數(shù)組［25］。例如：對(duì)于點(diǎn)yi，在遇到距離相同的路徑時(shí)，把yi在這條路徑的前驅(qū)節(jié)點(diǎn)記錄下來，而非拋棄或覆蓋；在遇到更短的路徑時(shí)，把yi的前驅(qū)點(diǎn)數(shù)組清空，存入新的前驅(qū)點(diǎn)。

求解最短路徑的算法步驟是：

（1）初始化，集合S存放已經(jīng)確定的最短路徑，初始時(shí)只包含源點(diǎn)，即S＝ ｛y0｝，y0的距離為0。集合V包含除y0外的其他頂點(diǎn)。若y0與V中的yi有邊，則頂點(diǎn) yi對(duì)應(yīng)的距離值 d［i］等于〈y0，yi〉 的權(quán)值，若 yi不是 y0的鄰接點(diǎn)，則 〈yi，y0〉權(quán)值為∞。

（2）從集合V中選取一個(gè)距離y0最小的頂點(diǎn)yk，把yk加入集合S中，以yk為新的中間點(diǎn)，修改集合V中各頂點(diǎn)的距離。若從源點(diǎn)y0經(jīng)過yk到頂點(diǎn)yi的距離小于原來y0到y(tǒng)i的距離，則修改y0到y(tǒng)i的距離值為 〈y0，yk〉 ＋ 〈yk，yi〉， 反之，則保持不變。

（3）重復(fù)步驟2直到所有頂點(diǎn)都包含在集合S中，則結(jié)束算法。

該算法是以某一頂點(diǎn)為中心向外層層擴(kuò)展，直至搜索到所有節(jié)點(diǎn)的最短路徑。但該算法存在以下兩個(gè)問題：

（1）搜索時(shí)需遍歷可走路徑中的所有節(jié)點(diǎn)，但這些節(jié)點(diǎn)有很多都是冗余點(diǎn)，這就使得找出的路徑存在很多不必要的拐點(diǎn)；

（2）遍歷可行路徑中的所有節(jié)點(diǎn)也會(huì)導(dǎo)致尋路時(shí)間過長(zhǎng)、效率低等問題。

2 自動(dòng)機(jī)建模

首先，對(duì)迷宮問題建模，若對(duì)所有塊進(jìn)行建模，會(huì)存在狀態(tài)集過大、計(jì)算過于復(fù)雜的問題，因此只在迷宮中的可行塊上建模。自動(dòng)機(jī)為五元組，由Y狀態(tài)集、Σ事件集、η狀態(tài)轉(zhuǎn)移函數(shù)、y0初始狀態(tài)、Ym標(biāo)識(shí)狀態(tài)組成?？尚袎K對(duì)應(yīng)自動(dòng)機(jī)的狀態(tài)，可行塊之間的移動(dòng)對(duì)應(yīng)自動(dòng)機(jī)的事件。所以可使用自動(dòng)機(jī)建模，在計(jì)算迷宮最優(yōu)路徑的長(zhǎng)短時(shí)需要把距離可視化。因此，把權(quán)值w引入自動(dòng)機(jī)模型中，自動(dòng)機(jī)用六元組 G ＝ （Y，Σ，η，w，y0，Ym） 表示。 其中，w 是可加的，w：（yi，yj） → N＋表示驅(qū)動(dòng)狀態(tài)轉(zhuǎn)移所需要的成本。用J（w）表示某一段路徑的權(quán)重，定義如下

本文針對(duì)圖1所示的迷宮用六元組自動(dòng)機(jī)G＝（Y，Σ，η，w，y0，Ym） 建模。 首先找到迷宮的入口和出口，設(shè)置為初始狀態(tài)y0和標(biāo)識(shí)狀態(tài)ym。 剩余的可行塊按照從左到右，從上到下1，2，3…進(jìn)行編號(hào)，每個(gè)塊用相應(yīng)的狀態(tài)y1，y2，y3…表示。狀態(tài)和事件存在著以下的關(guān)系yi×Σ∈Y，若i和j（i≠j）為相鄰狀態(tài)，在兩狀態(tài)之間添加事件和權(quán)值，事件用bi，j表示，權(quán)值 w 為 1。 狀態(tài)集合 Y ＝ ｛y0，y1，y2，…，ym｝， 事件集合 Σ ＝ ｛b0，1，b1，0，b1，2，b2，1，…｝，η：y0×y0，1→y1，y0∈Y為初始狀態(tài)，ym∈Y為終止?fàn)顟B(tài)。建好的自動(dòng)機(jī)模型如圖2所示。

圖2 自動(dòng)機(jī)模型

3 簡(jiǎn)化自動(dòng)機(jī)模型

3.1 無效狀態(tài)的刪除

傳統(tǒng)的迷宮問題求解通常是對(duì)每個(gè)可行塊進(jìn)行依次搜索，在這些可行塊組成的路徑中，有些通道進(jìn)入后需退回到進(jìn)入塊中的某一可行塊進(jìn)行再搜索，這就使得生成的路徑部分重合，路徑過長(zhǎng)且不是最優(yōu)路徑。因此需要?jiǎng)h除多余可行塊，優(yōu)化可行路徑?？尚袎K的刪除對(duì)應(yīng)狀態(tài)節(jié)點(diǎn)的刪除。

定義 1：對(duì) ?yi∈ Y， 必然 ?bi－1，i＆bi，i－1∈ Σ，使 η（yi－1，bi－1，i） ＝ yi＆η（yi，bi，i－1） ＝ yi－1， 若 ?bi，i＋1＆bi＋1，i∈ Σ， 使 η（yi，bi，i＋1） ＝ yi＋1＆η（yi＋1，bi＋1，i） ＝ yi，則yi稱之為有效狀態(tài)。若不滿足則為無效狀態(tài)。

有效狀態(tài)組成有效路徑，無效狀態(tài)類似于死胡同，進(jìn)入無效狀態(tài)后，需退回進(jìn)行再搜索。無效狀態(tài)使得路徑部分重疊，該類狀態(tài)造成了路徑存儲(chǔ)空間及尋路時(shí)間的浪費(fèi)。省略該狀態(tài)也可行至終點(diǎn)，所以刪除無效狀態(tài)即可簡(jiǎn)化路徑。無效狀態(tài)的刪除如算法1所示。

算法1：無效狀態(tài)的刪除

輸入：自動(dòng)機(jī)建好的模型

輸出：有效路徑組成的自動(dòng)機(jī)模型

說明：（1）該算法是迭代算法。刪除一個(gè)無效狀態(tài)后，當(dāng)前無效狀態(tài)相鄰的有效狀態(tài)有可能變?yōu)闊o效狀態(tài)。因此搜索無效狀態(tài)相鄰的狀態(tài)進(jìn)行再判斷，直至路徑中所有的無效狀態(tài)全部刪除。（2）該算法刪除后的路徑為有效路徑。無效狀態(tài)刪除后，重復(fù)率下降，因此權(quán)重J（w）變小，存儲(chǔ)空間變小及尋路時(shí)間變短。（3）無效狀態(tài)即為冗余點(diǎn)。在尋找最優(yōu)路徑時(shí)，冗余點(diǎn)影響判斷，浪費(fèi)時(shí)間。該算法刪除的無效狀態(tài)，使得冗余點(diǎn)多的問題得到改善，尋找最優(yōu)路徑更加高效。

根據(jù)算法1對(duì)圖2進(jìn)行無效狀態(tài)的刪除。如狀態(tài)y33經(jīng)過事件b33，36到達(dá)狀態(tài)y36，而狀態(tài)y36有且只有事件b36，33可以進(jìn)行轉(zhuǎn)移，轉(zhuǎn)移到狀態(tài)y33。y36狀態(tài)不滿足定義1。因此，該狀態(tài)為無效狀態(tài)，對(duì)該狀態(tài)及相連事件 b33，36、b36，33進(jìn)行刪除。 刪除后搜索該狀態(tài)相連的狀態(tài)y33，發(fā)現(xiàn)該狀態(tài)也變?yōu)闊o效狀態(tài)，對(duì)其進(jìn)行刪除操作。無效狀態(tài)全部刪除后的自動(dòng)機(jī)模型如圖3所示。

圖3 無效狀態(tài)刪除后的自動(dòng)機(jī)模型

3.2 可替狀態(tài)的刪除

在無效狀態(tài)刪除后的基礎(chǔ)上發(fā)現(xiàn)，存在一類分支狀態(tài)，可以朝著兩個(gè)方向進(jìn)行搜索，搜索各經(jīng)過一個(gè)不同的狀態(tài)之后，可到達(dá)同一狀態(tài)。組成的兩條路徑中開始狀態(tài)、匯合狀態(tài)及所經(jīng)過的路徑長(zhǎng)度都相同，因此兩條路徑是重復(fù)路徑，可對(duì)其中靈活性較差的路徑進(jìn)行刪除且該路徑的刪除不會(huì)影響最優(yōu)路徑的求解。

定 義 2： 若 （?s1＝ bj，j＋1＆bj＋1，j＋3∈ Σ?） 使η（yj，s1） ＝ yj＋3， （?s2＝ bj，j＋2＆bj＋2，j＋3∈ Σ?） 使η（yj，s2） ＝y(tǒng)j＋3且 yj＋1≠ yj＋2， 則稱 yj＋1，yj＋2為可替狀態(tài)。

yj，yj＋1，yj＋3組成一條路徑， yj，yj＋2，yj＋3組成另一條路徑。這兩條路徑中的起點(diǎn)、終點(diǎn)和J（w）都相同。因此，該兩條路徑為重復(fù)路徑，但經(jīng)過的中間狀態(tài) yj＋1、yj＋2不同，則稱該中間狀態(tài)為可替狀態(tài)。刪除其中一個(gè)可替狀態(tài)，該可替狀態(tài)所在的重復(fù)路徑就會(huì)被刪除。

刪除的條件為 （?s3＝ bj＋1，p∈ Σ?） 使得 η（yj，s3） ＝ yp，（?s4＝ bj＋2，q∈ Σ?） 使得 η（yj，s4） ＝ yq，s3，s4集合中多的保留，少的刪除，留下的路徑靈活性較強(qiáng)。可替狀態(tài)的刪除如算法2所示。

算法2：可替狀態(tài)的刪除

輸入：有效路徑組成的自動(dòng)機(jī)模型

輸出：重復(fù)路徑刪除后的自動(dòng)機(jī)模型

說明：（1）刪除重復(fù)路徑中的可替狀態(tài)，刪除該狀態(tài)對(duì)路徑的長(zhǎng)度無影響，J（w）的值不變。刪除可替狀態(tài)后到終點(diǎn)的多條路徑中冗余點(diǎn)相應(yīng)減少。（2）路徑的重復(fù)問題使得數(shù)據(jù)冗余，導(dǎo)致內(nèi)存開銷大。因此，刪除重復(fù)路徑使得冗余點(diǎn)減少，內(nèi)存開銷相應(yīng)減少。

根據(jù)算法2對(duì)圖3進(jìn)行可替狀態(tài)的刪除。如：狀態(tài)y9經(jīng)過事件b9，1到達(dá)狀態(tài)y1，再由狀態(tài)y1經(jīng)過事件 b1，2轉(zhuǎn)移到狀態(tài) y2；y9也可經(jīng)過事件 b9，10到達(dá)中間狀態(tài)y10，再由狀態(tài)y10經(jīng)過事件b10，2到達(dá)狀態(tài)y2。兩條路徑中起始狀態(tài)為y9，匯合狀態(tài)為y2，可替狀態(tài)為 y1、y10， 中間相連的事件集 s3＝ b1，9，s4＝ b10，2、b10，14。 s3＜ s4，因此保留狀態(tài)y10，刪除狀態(tài)y1及相連的事件。刪除后的自動(dòng)機(jī)模型如圖4所示。

圖4 可替狀態(tài)刪除后的自動(dòng)機(jī)模型

3.3 迭代刪除

做可替狀態(tài)刪除時(shí)，可能出現(xiàn)無效狀態(tài)；做無效狀態(tài)刪除時(shí)，可能出現(xiàn)可替狀態(tài)。因此，需進(jìn)行兩種算法的迭代處理，直至所有冗余點(diǎn)刪除完成。無效狀態(tài)刪除后，路徑變?yōu)橛行窂?；可替狀態(tài)刪除不影響路徑的求解。因此，兩種算法的迭代，不會(huì)影響到最優(yōu)路徑的求解。迭代刪除如算法3所示。

算法3：迭代刪除

輸入：重復(fù)路徑刪除后的自動(dòng)機(jī)模型

輸出：無冗余狀態(tài)的自動(dòng)機(jī)模型

說明：（1）通過算法1、2、3進(jìn)行了冗余點(diǎn)的刪除，使得后續(xù)在尋找最優(yōu)路徑時(shí)，搜索范圍減小，內(nèi)存開銷減少，則搜索效率相應(yīng)地提高。（2）通過以上算法，對(duì)路徑上的冗余點(diǎn)進(jìn)行了刪除，使得任意兩節(jié)點(diǎn)之間路徑最短，權(quán)重最小，則自動(dòng)機(jī)簡(jiǎn)化后的模型全局最優(yōu)。

根據(jù)算法3對(duì)圖4進(jìn)行迭代刪除。如狀態(tài)y2經(jīng)過可替狀態(tài)的刪除后，從有效狀態(tài)變?yōu)闊o效狀態(tài)，刪除該狀態(tài)。所有冗余點(diǎn)刪除后的自動(dòng)機(jī)模型如圖5所示。

圖5 迭代刪除后的自動(dòng)機(jī)模型

3.4 可行狀態(tài)的優(yōu)化

迭代刪除后模型的冗余點(diǎn)都已被刪除，但迷宮較大時(shí)仍存在狀態(tài)和事件過多的問題，因此要對(duì)模型進(jìn)行進(jìn)一步的優(yōu)化。剩下的路徑為可行路徑，在此路徑上對(duì)權(quán)值w及權(quán)重J（w）進(jìn)行狀態(tài)和事件的優(yōu)化可提高計(jì)算效率及節(jié)約存儲(chǔ)空間。

數(shù)組A1存放的是節(jié)點(diǎn)刪除后其中一條路徑上的狀態(tài)節(jié)點(diǎn)，0表示初始狀態(tài)y0，m表示標(biāo)識(shí)狀態(tài)ym，剩余的為通道狀態(tài)。數(shù)組B1存放著初始狀態(tài)、分支狀態(tài)及標(biāo)識(shí)狀態(tài)。

狀態(tài)節(jié)點(diǎn)的優(yōu)化思想如下：

（1）數(shù)組C1中存放分支狀態(tài)節(jié)點(diǎn)之間的權(quán)值，初始值為0。

（2）在數(shù)組A1中搜索數(shù)組B1狀態(tài)之間存在多少個(gè)通道狀態(tài)節(jié)點(diǎn)，因通道狀態(tài)節(jié)點(diǎn)的移動(dòng)路徑是唯一的，所以引入權(quán)值進(jìn)行優(yōu)化。依此類推，找到所有分支狀態(tài)之間的權(quán)值。

（3）搜索剩余路徑進(jìn)行省略并引入權(quán)值。

說明：通過對(duì)可行路徑中的節(jié)點(diǎn)篩選，使一些不必要的節(jié)點(diǎn)被省略，只留下關(guān)鍵節(jié)點(diǎn)進(jìn)行保存。節(jié)點(diǎn)大批量地減少，使得計(jì)算機(jī)的內(nèi)存開銷也大幅減少。

對(duì)迭代后的自動(dòng)機(jī)模型圖5進(jìn)行狀態(tài)優(yōu)化。首先把一條路徑的所有狀態(tài)節(jié)點(diǎn)放入數(shù)組A1；把初始狀態(tài)節(jié)點(diǎn)y0、分支狀態(tài)節(jié)點(diǎn)y7、y24、y41及標(biāo)識(shí)狀態(tài)節(jié)點(diǎn)ym放入數(shù)組B1；其次，選擇相鄰的分支節(jié)點(diǎn)引入權(quán)重進(jìn)行簡(jiǎn)化，如：路線y7→y8→y9→y10→y14→y15→y16→y19→y24，y7經(jīng)過8個(gè)狀態(tài)到達(dá)y24，則y7到y(tǒng)24權(quán)重J（w）為8，把權(quán)重放入數(shù)組C1中。優(yōu)化的數(shù)組存放如圖6所示。

圖6 可行狀態(tài)的優(yōu)化

對(duì)所有路徑進(jìn)行狀態(tài)優(yōu)化，優(yōu)化后的自動(dòng)機(jī)模型如圖7所示。其中狀態(tài)和事件個(gè)數(shù)大大減少，狀態(tài)由原來的43減少到6，事件由96減少到14。通過以上狀態(tài)的刪除及優(yōu)化，不僅減小了計(jì)算機(jī)的存儲(chǔ)量，也提高了路徑求解的效率。

圖7 優(yōu)化后的自動(dòng)機(jī)模型

4 最短路徑求解

本文在自動(dòng)機(jī)模型的基礎(chǔ)上進(jìn)行了簡(jiǎn)化，簡(jiǎn)化分為節(jié)點(diǎn)刪除和節(jié)點(diǎn)優(yōu)化兩個(gè)部分，節(jié)點(diǎn)刪除去除了路徑中的冗余點(diǎn)，節(jié)點(diǎn)優(yōu)化篩選可行路徑的關(guān)鍵節(jié)點(diǎn)保存，使得內(nèi)存開銷減小。因此，在簡(jiǎn)化后的模型上使用Dijkstra算法可以快速、高效地計(jì)算出最短路徑，最短路徑，如表1所示。而傳統(tǒng)Dijkstra算法計(jì)算結(jié)果如表2所示。

表1 優(yōu)化算法求解

表2 傳統(tǒng)Dijkstra算法求解

從表1可知，初始狀態(tài)到標(biāo)識(shí)狀態(tài)的最短距離為14，找到兩條最短路徑為y0→y1→y29→y41→ym或y0→y1→y24→y41→ym。 經(jīng)過此方法不僅能求得多條最短路徑，且路徑的距離及路線都能詳細(xì)給出。

對(duì)比：（1）傳統(tǒng)的Dijkstra算法，同時(shí)也會(huì)計(jì)算多條死胡同路徑的距離，增加了不必要的工作量。而優(yōu)化算法，在一開始就刪除死胡同路徑，只保留到目標(biāo)點(diǎn)的最短距離。（2）傳統(tǒng)的Dijkstra算法雖然有權(quán)值，但在求柵格地圖的迷宮時(shí)，所有權(quán)值都為1，對(duì)后續(xù)求解沒有大的作用。優(yōu)化后的算法對(duì)不必要的節(jié)點(diǎn)進(jìn)行省略，省略的節(jié)點(diǎn)利用權(quán)值表示，發(fā)揮了權(quán)值的作用。（3）傳統(tǒng)的Dijkstra算法通常只能求單條最短路徑，而本文在簡(jiǎn)化后的自動(dòng)機(jī)模型上用文獻(xiàn)［24］的改進(jìn)算法，求出多條最短路徑。（4） 傳統(tǒng)Dijkstra算法的時(shí)間復(fù)雜度為O（n2）。 而優(yōu)化算法的時(shí)間復(fù)雜度等于簡(jiǎn)化模型的時(shí)間復(fù)雜度O（p）及簡(jiǎn)化后節(jié)點(diǎn)的復(fù)雜度O（q2）之和，p＋q＝n。簡(jiǎn)化使得絕大部分節(jié)點(diǎn)被省略，只剩少部分節(jié)點(diǎn)進(jìn)行最短路徑的計(jì)算。根據(jù)公式可知O（p）＋O（q2） ＜O（n2），且隨著迷宮規(guī)模的增大，簡(jiǎn)化模型的時(shí)間復(fù)雜度O（p）可以忽略不計(jì)，則優(yōu)化算法的效率相較于傳統(tǒng)算法顯著提升。

對(duì)圖2中的自動(dòng)機(jī)分別用傳統(tǒng)的Dijkstra算法和優(yōu)化算法求解。由表2可知，時(shí)間復(fù)雜度為432＝1 849。由表1可知，時(shí)間復(fù)雜度為37＋62＝73。用MATLAB仿真求解10×10迷宮時(shí)，傳統(tǒng)的Dijkstra算法用時(shí)為36 ms，優(yōu)化算法用時(shí)0.8 ms，其時(shí)間復(fù)雜度相差較大。隨著迷宮規(guī)模的增大，兩者的時(shí)間復(fù)雜度相差會(huì)更大。

5 仿真及分析

5.1 執(zhí)行命令次數(shù)

表3是A?算法、Dijkstra算法和本文算法找到最優(yōu)路徑的前提下，所要執(zhí)行命令次數(shù)的對(duì)比。從表3可知，Dijkstra算法在找最優(yōu)路徑時(shí)，會(huì)搜索所有的可行狀態(tài)節(jié)點(diǎn)，執(zhí)行命令的次數(shù)等于可行狀態(tài)節(jié)點(diǎn)個(gè)數(shù)；A?算法在障礙物多且復(fù)雜的情況下，其尋找最優(yōu)路徑時(shí)冗余點(diǎn)較多，執(zhí)行命令次數(shù)相應(yīng)也較多；在障礙物較少的情況下，其尋找最優(yōu)路徑冗余點(diǎn)少，執(zhí)行命令次數(shù)相應(yīng)少；A?算法最壞的情況接近Dijkstra算法，最好的情況為最短路徑的距離。本文算法只取路徑中關(guān)鍵節(jié)點(diǎn)進(jìn)行指令的執(zhí)行，其執(zhí)行命令的次數(shù)少于最短路徑的距離，與簡(jiǎn)化后的節(jié)點(diǎn)個(gè)數(shù)有關(guān)。Dijkstra算法執(zhí)行命令的次數(shù)占可行節(jié)點(diǎn)的100%，A?算法執(zhí)行命令的次數(shù)在最優(yōu)路徑節(jié)點(diǎn)個(gè)數(shù)和總節(jié)點(diǎn)個(gè)數(shù)之間，取決于迷宮的復(fù)雜度。而本文算法執(zhí)行命令的次數(shù)往往小于最優(yōu)路徑的節(jié)點(diǎn)個(gè)數(shù)，取決于保留的關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)。

表3 執(zhí)行命令次數(shù)

5.2 路徑圖

圖8給出了10×10迷宮下的一個(gè)特例，黑色塊表示障礙物，白色塊表示可行路徑，綠色塊表示該算法從起始點(diǎn)到目標(biāo)點(diǎn)需要遍歷的節(jié)點(diǎn)。從圖8可知，Dijkstra算法需遍歷所有的可行節(jié)點(diǎn)，占可行節(jié)點(diǎn)的100%；A?算法需要遍歷23個(gè)可行節(jié)點(diǎn)，占可行節(jié)點(diǎn)的53%；而本文算法只需遍歷6個(gè)節(jié)點(diǎn)，占總結(jié)點(diǎn)的12%。Dijkstra算法需要遍歷所有的可行塊才可以找到路徑，A?算法也需要遍歷一些多余的塊，而本文算法所遍歷的可行塊就是最短路徑。

圖8 三種算法遍歷節(jié)點(diǎn)圖

5.3 時(shí)間對(duì)比

前文通過一些具體的小型迷宮來說明本算法的有效性，為了驗(yàn)證本算法在隨機(jī)的復(fù)雜大規(guī)模迷宮中也同樣保持有效性，在Matlab中產(chǎn)生10×10，20×20，40×40，60×60，80×80，100×100，125×125，150×150，200×200，250×250，300×300 規(guī)格的隨機(jī)迷宮矩陣，每個(gè)規(guī)格產(chǎn)生5個(gè)隨機(jī)迷宮矩陣，并用3種算法對(duì)不同規(guī)格下的不同矩陣進(jìn)行仿真。仿真結(jié)果如圖9所示，橫軸代表迷宮的規(guī)格，縱軸代表同一個(gè)規(guī)格下5個(gè)迷宮運(yùn)行時(shí)間的平均值。由圖9可見，Dijkstra算法隨著迷宮規(guī)模的增大，搜索最優(yōu)路徑的時(shí)間呈指數(shù)級(jí)增長(zhǎng)。A?算法的搜索時(shí)間效率高于Dijkstra算法，但低于本文算法。計(jì)算300×300迷宮時(shí)，Dijkstra算法計(jì)算2 h仍沒有結(jié)果，A?算法時(shí)間需要1 723.415 32 s，而本文算法僅需602.541 161 s。通過多個(gè)隨機(jī)產(chǎn)生的迷宮矩陣實(shí)驗(yàn)表明，本文算法總能找到最優(yōu)路徑，其平均時(shí)間優(yōu)于Dijkstra算法及A?算法。

圖9 算法結(jié)果

6 結(jié)束語

本文以迷宮為研究對(duì)象，提出了基于自動(dòng)機(jī)模型的迷宮最優(yōu)路徑求解算法。該算法是用新的工具進(jìn)行建模和簡(jiǎn)化的，與以往最優(yōu)求解思路截然不同。該算法首先建立迷宮的自動(dòng)機(jī)模型，結(jié)合其結(jié)構(gòu)性質(zhì)進(jìn)行節(jié)點(diǎn)簡(jiǎn)化，簡(jiǎn)化分為節(jié)點(diǎn)刪除及節(jié)點(diǎn)優(yōu)化兩部分，簡(jiǎn)化后冗余點(diǎn)被刪除且只留下路徑的關(guān)鍵節(jié)點(diǎn)，使得內(nèi)存開銷、求解時(shí)間相應(yīng)地減少，且優(yōu)于其他算法。其次，用這些關(guān)鍵節(jié)點(diǎn)進(jìn)行路徑長(zhǎng)度的計(jì)算，得到最優(yōu)路徑。仿真結(jié)果表明，求解路徑中的冗余點(diǎn)被消除，內(nèi)存開銷減少且在處理大規(guī)模迷宮時(shí)效率顯著提升。但該類算法針對(duì)的是全局環(huán)境已知且不變的情況。