基于自動機(jī)的迷宮路徑規(guī)劃求解算法優(yōu)化

湯 偉，趙 靜，古 嬋

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

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

1 理論回顧

1.1 迷宮問題的描述

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

圖1 迷宮［20］

1.2 自動機(jī)

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

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

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

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

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

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

1.3 Dijkstra 算法

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

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

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

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

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

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

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

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

2 自動機(jī)建模

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

本文針對圖1所示的迷宮用六元組自動機(jī)G＝（Y，Σ，η，w，y0，Ym） 建模。 首先找到迷宮的入口和出口，設(shè)置為初始狀態(tài)y0和標(biāo)識狀態(tài)ym。 剩余的可行塊按照從左到右，從上到下1，2，3…進(jìn)行編號，每個塊用相應(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)。建好的自動機(jī)模型如圖2所示。

圖2 自動機(jī)模型

3 簡化自動機(jī)模型

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

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

定義 1：對 ?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)造成了路徑存儲空間及尋路時間的浪費(fèi)。省略該狀態(tài)也可行至終點，所以刪除無效狀態(tài)即可簡化路徑。無效狀態(tài)的刪除如算法1所示。

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

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

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

說明：（1）該算法是迭代算法。刪除一個無效狀態(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）變小，存儲空間變小及尋路時間變短。（3）無效狀態(tài)即為冗余點。在尋找最優(yōu)路徑時，冗余點影響判斷，浪費(fèi)時間。該算法刪除的無效狀態(tài)，使得冗余點多的問題得到改善，尋找最優(yōu)路徑更加高效。

根據(jù)算法1對圖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)，對該狀態(tài)及相連事件 b33，36、b36，33進(jìn)行刪除。 刪除后搜索該狀態(tài)相連的狀態(tài)y33，發(fā)現(xiàn)該狀態(tài)也變?yōu)闊o效狀態(tài)，對其進(jìn)行刪除操作。無效狀態(tài)全部刪除后的自動機(jī)模型如圖3所示。

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

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

在無效狀態(tài)刪除后的基礎(chǔ)上發(fā)現(xiàn)，存在一類分支狀態(tài)，可以朝著兩個方向進(jìn)行搜索，搜索各經(jīng)過一個不同的狀態(tài)之后，可到達(dá)同一狀態(tài)。組成的兩條路徑中開始狀態(tài)、匯合狀態(tài)及所經(jīng)過的路徑長度都相同，因此兩條路徑是重復(fù)路徑，可對其中靈活性較差的路徑進(jìn)行刪除且該路徑的刪除不會影響最優(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組成另一條路徑。這兩條路徑中的起點、終點和J（w）都相同。因此，該兩條路徑為重復(fù)路徑，但經(jīng)過的中間狀態(tài) yj＋1、yj＋2不同，則稱該中間狀態(tài)為可替狀態(tài)。刪除其中一個可替狀態(tài)，該可替狀態(tài)所在的重復(fù)路徑就會被刪除。

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

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

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

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

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

根據(jù)算法2對圖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及相連的事件。刪除后的自動機(jī)模型如圖4所示。

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

3.3 迭代刪除

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

算法3：迭代刪除

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

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

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

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

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

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

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

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

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

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

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

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

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

對迭代后的自動機(jī)模型圖5進(jìn)行狀態(tài)優(yōu)化。首先把一條路徑的所有狀態(tài)節(jié)點放入數(shù)組A1；把初始狀態(tài)節(jié)點y0、分支狀態(tài)節(jié)點y7、y24、y41及標(biāo)識狀態(tài)節(jié)點ym放入數(shù)組B1；其次，選擇相鄰的分支節(jié)點引入權(quán)重進(jìn)行簡化，如：路線y7→y8→y9→y10→y14→y15→y16→y19→y24，y7經(jīng)過8個狀態(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)化

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

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

4 最短路徑求解

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

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

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

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

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

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

5 仿真及分析

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

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

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

5.2 路徑圖

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

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

5.3 時間對比

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

圖9 算法結(jié)果

6 結(jié)束語

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