迷宮最短路徑問(wèn)題新算法

1、迷宮最短路徑問(wèn)題新算法摘 要：提出了求解迷宮最短路徑問(wèn)題的新算法 該算法拋棄了經(jīng)典算法（深度優(yōu)先搜索和廣度優(yōu)先搜索 中繁雜低效的遞歸、回溯思想。通過(guò)合理的變換，將原問(wèn)題轉(zhuǎn)化為迷宮路徑深度圖的生成問(wèn)題。最后對(duì)算法進(jìn)行了嚴(yán)謹(jǐn)?shù)姆治龊蛯?shí)例測(cè)試，顯示出該算法易于理解、易于編程、時(shí)間空間復(fù)雜度低等優(yōu)點(diǎn)。關(guān)鍵詞：最短路徑；時(shí)間復(fù)雜度；深度優(yōu)先搜索；廣度優(yōu)先搜索New Algorithm for Solving Shortest Path of Maze ProblemZHANG Lin- feng, LV Hui, QU Jun- feng(The Missile Institute, Air Force

2、 Engineering University, Sanyuan, Shannxi 713800, China)Abstract: A new algorithm is presented for solving the shortest path of maze problem, which is not based on the inefficient recursive backtracking theory of classical algorithm (DFS- Depth First Search and BFS- Breadth First Search).Byappropria

3、te conversion, the algorithm changes the original problem into the creation of the maze graph problem.At last,an example is given, which shows that the new algorithm is easy to be understood and programmed as well as its lowtime and space complexity.Key words: shortest path; time complexity; Depth F

4、irst Search; Breadth First Search1問(wèn)題描述迷宮最短路徑(the shortest path of maze)問(wèn)題是一個(gè)典型的搜索、遍歷問(wèn)題其程序設(shè)計(jì)思想在人工智能設(shè)計(jì)、機(jī)器人設(shè)計(jì)等事務(wù)中均有應(yīng)用。如圖1所示，一個(gè)NXM的大方塊迷宮，帶斜線的單元格表 示墻壁（障礙），空白的單元格表示通道。迷宮問(wèn)題可以表述為 尋找從某一個(gè)給定的起始單元格（迷宮入口）出發(fā)，經(jīng)由行相鄰 或列相鄰的通道單元格 最終可以到達(dá)目標(biāo)單元格（迷宮出 口）,所走過(guò)的單元格序列。行進(jìn)中 只能沿上下左右四個(gè)方向 刖進(jìn)。而迷宮最短路徑問(wèn)題就是找出從迷宮入口到出口所經(jīng)過(guò) 單元格個(gè)數(shù)最少的路徑。2經(jīng)典算法

5、求解迷宮問(wèn)題，經(jīng)典算法有深度優(yōu)先搜索和廣度優(yōu)先搜索 兩種深度優(yōu)先搜索（DFS）:從入口出發(fā)，順著某一方向向前探 索，若能走通則繼續(xù)彳主前走；否則沿原路退回（回溯）,換一個(gè) 方向再繼續(xù)探索，直至所有可能的通路都探索到為止。如果恰 好某一步探索到出口，則就找到了從入口到出口的路徑。為了 保證在任何位置上都能沿原路退回防止死循環(huán)，需要使用堆 棧來(lái)保存大量記錄。而要求解迷宮最短路徑則必須用深度優(yōu) 先搜索出所有到達(dá)出口的路徑 通過(guò)比較得到最短距離的路 徑，這樣也必然要求增加數(shù)據(jù)空間來(lái)保存搜索過(guò)程中當(dāng)前最短 路徑，增加了空間復(fù)雜度。廣度優(yōu)先搜索（BFS）:從入口出發(fā)，離開(kāi)入口后依次訪問(wèn) 與當(dāng)前位置鄰接的單

6、元格（上下左右方向），然后分別從這些相 鄰單元格出發(fā)依次訪問(wèn)它們的鄰接格 并使“先被訪問(wèn)的單元 格的鄰接格先于后被訪問(wèn)的單元格的鄰接格”被訪問(wèn)直至 訪問(wèn)到迷宮出口，則找到了迷宮問(wèn)題的最優(yōu)解即迷宮最短路 徑。該算法的顯著特點(diǎn)是“層層推進(jìn)”，探索點(diǎn)會(huì)隨著探索的深 入急劇增加，相應(yīng)地，需要大量的空間用來(lái)保存探索過(guò)程的記 錄，空間復(fù)雜度大。與此同時(shí)，上述兩種算法都比較抽象復(fù)雜 編程實(shí)現(xiàn)容易 出現(xiàn)問(wèn)題，調(diào)試比較困難 因此在本篇論文中提出了一種新的 容易理解和調(diào)試的算法，該算法復(fù)雜度較彳氐 求解較大規(guī)模的 迷宮問(wèn)題也有不俗的表現(xiàn)。3本文算法3.1本文算法基本思想描述首先與其他算法一樣，將NXM的圖形迷宮表

7、示為一個(gè)二維矩陣，用二維數(shù)組aNM來(lái)存儲(chǔ)信息，N和M分別代表迷宮 的行數(shù)和列數(shù)，迷宮中的每個(gè)位置都可用矩陣數(shù)組的行號(hào)和列 號(hào)來(lái)指定。在矩陣中，當(dāng)且僅當(dāng)在位置（i，j）處有一個(gè)障礙時(shí)其 值aij為1，否則其值為0。圖2給出了與圖1迷宮對(duì)應(yīng)的矩 陣描述。其次在本算法中引入了 “路徑深度”及“路徑深度圖”的 概念。路徑深度：從某位置走到出口的最短路徑的長(zhǎng)度 記為 depth。，設(shè)每一方塊為單位路徑長(zhǎng)度。假定出口處路徑深度為 0，障礙處路徑深度為-1。路徑深度圖：與迷宮對(duì)應(yīng)的圖，每一個(gè)節(jié)點(diǎn)值為與該節(jié)點(diǎn)對(duì)應(yīng)的迷宮單元格的路徑深度 即該單元格與迷宮出口的最短距離。顯然路徑深度圖有且唯一(因?yàn)槊總€(gè)單元格與迷

8、宮出口的最短距離有且唯一)。如圖1所示的迷宮入口處的路徑深度為12,最短路徑為圖2中箭頭所指出的道路。即：(1, 1)- (1, 2)- (2, 2)- (3, 2)- (3, 1) - (4, 1) -(5, 1) - (5,2)-(5, 3)- (4, 3)- (4, 4)- (4, 5)- (5, 5)。迷宮單元格的路徑深度如圖3所示。從圖3中，可以看出：迷宮最短路徑是一條從入口處開(kāi)始的路徑深度逐次遞減1的序列。因此如果能求出整個(gè)迷宮每個(gè)單元格的路徑深度從而形成迷宮的路徑深度圖則求解最短路徑就很簡(jiǎn)單。本論文的關(guān)鍵算法在求解迷宮的路徑深度圖上。3.2迷宮路徑深度圖算法定理 形成迷宮路徑深度

9、圖的必要條件是 圖中每一個(gè)節(jié)點(diǎn)值不大于周?chē)?上下左右四個(gè)可行進(jìn)方向)最小節(jié)點(diǎn)值+1。證明：設(shè)點(diǎn)A(x, y)為迷宮中任意一點(diǎn)(非障礙),而點(diǎn)B為與點(diǎn)A鄰接點(diǎn)(上下左右四個(gè)方向)中節(jié)點(diǎn)值最小的點(diǎn)(非障礙)。必要性：假設(shè)從點(diǎn)B出發(fā)，存在一條到達(dá)迷宮出口的最短 路徑。則從點(diǎn)A出發(fā)，可以先到達(dá)B點(diǎn)，然后順著從點(diǎn)B到出 口的最短路徑，就能到達(dá)出口。而由本文路徑深度的定義 顯然 有 depth(A)Wdepth(A- B- 出口)=1+depth(B)。必要性得證。 下面給出求解迷宮路徑圖的算法：步驟 1 置初值，depth(障礙)=-1, depth(出口)=0, depth(通 道)NXM;步驟2交換

10、標(biāo)記tag置為0;步驟3指針指向某一通道單元格A;步驟4如果當(dāng)前單元格是迷宮障礙 轉(zhuǎn)步驟7;步驟5找出周?chē)尚蟹较騿卧?非障礙)的最小路徑深度min (depth();步驟 6 如果 depth(A) min(depth() ) +1,則調(diào)整 depth(A) =min (depth( ) )+1,并記交換標(biāo)記tag=1;步驟7如果已遍歷完所有單元格轉(zhuǎn)步驟9;步驟8指針以某一遍歷規(guī)則(比如順序訪問(wèn))后移，轉(zhuǎn)步驟3;步驟9如果tag=1,轉(zhuǎn)步驟2;步驟10如果tag=0,說(shuō)明所有單元格路徑深度depth()經(jīng)過(guò)動(dòng) 態(tài) 調(diào)整后達(dá)到穩(wěn)定平衡(定理所述狀態(tài))，即形成路徑深度圖，算法 結(jié)束。現(xiàn)在證明該

11、算法最終形成了路徑深度圖。用反證法證明。由上述算法形成的圖記為圖G,假設(shè)圖G并非本文定義的路徑深度圖G，即圖G總存在一點(diǎn)A,其節(jié)點(diǎn)值depth(A)=k,而該點(diǎn)對(duì)應(yīng)的單元格與迷宮出口的最短路徑的長(zhǎng)度為l, lk,設(shè)最短路徑為AfPl-1f Pl-2P1f出口，而在圖G中此路徑上有l(wèi)個(gè)節(jié)點(diǎn)，沿路徑順序其節(jié)點(diǎn)值為上界為k,下界為l的遞減整數(shù)數(shù)列因?yàn)閘Pi+1+1,則該圖G未達(dá)到穩(wěn)定平衡與前提G是穩(wěn)定平衡下的路徑深度圖矛盾，故假設(shè)不成立，從而證明了算法形成的最終圖就是待求解的路徑深度圖。3.3通過(guò)路徑深度圖尋找最短路徑算法構(gòu)造出路徑深度圖G后，就可以很方便地找到迷宮中任意一點(diǎn)到出口的最短路徑。在這里

12、 以求解迷宮入口到出口的最短路徑為例，設(shè)depth(s)二k。算法如下：步驟1指針p指向入口，入口位置進(jìn)路徑隊(duì)列 路徑深度標(biāo)記 depth二k- 1;步驟2尋找p指向的單元格周?chē)?上下左右可行進(jìn)方向)路徑深 度等于depth的單元格；步驟3該單元格進(jìn)入路徑隊(duì)列p指向該單元格，depth-;步驟4如果depth0,轉(zhuǎn)步驟2;步驟5如果depth=0,說(shuō)明找到出口，出口位置進(jìn)入路徑隊(duì)列 算 法結(jié)束。至此，迷宮最短路徑新算法結(jié)束。4算法評(píng)價(jià)4.1時(shí)間空間復(fù)雜度分析本算法主要分兩個(gè)部分 而最主要的時(shí)間開(kāi)銷(xiāo)就在第一部分求路徑深度圖算法上。算法主要過(guò)程是逐步判斷每個(gè)單元格是否與周?chē)?個(gè)單元格達(dá)到穩(wěn)定平衡狀

13、態(tài)時(shí)間復(fù)雜度為O( 4XNXM),空間方面主要需要兩個(gè)NXM的二維數(shù)組(一個(gè)存儲(chǔ)迷宮信息一個(gè)存儲(chǔ)路徑深度圖),故空間復(fù)雜度為 O(NXM)。第二部分算法為通過(guò)路徑深度圖求最短路徑當(dāng)最短路徑 長(zhǎng)度為k時(shí)，時(shí)間方面最多需要判斷3k次，空間方面路徑隊(duì) 列長(zhǎng)度為k,其中k=O( N+M),所以時(shí)間和空間復(fù)雜度均為 O( N+M)。綜上所述，本算法的時(shí)間和空間復(fù)雜度均為O(NXM)。而經(jīng)典算法中廣度優(yōu)先搜索 空間復(fù)雜度方面除了要兩個(gè)NXM的二維數(shù)組存儲(chǔ)迷宮信息和迷宮單元格訪問(wèn)信息外 還 實(shí)驗(yàn)結(jié)果顯示，不論是峰值信噪比還是濾波圖像的視覺(jué)質(zhì) 量，數(shù)字雙邊l1濾波器的濾波效果均極為顯著性能大大優(yōu)于中值濾波器。

14、可見(jiàn)，脈沖雙邊l1濾波器比傳統(tǒng)中值濾波器具有更強(qiáng)的噪聲抑制能力和邊緣保持能力。同時(shí)式(10)運(yùn)算簡(jiǎn)單, 實(shí)現(xiàn)方便，因此是對(duì)傳統(tǒng)中值濾波器極為合理而有效的推廣與 改進(jìn)，具有重要的實(shí)用價(jià)值。5結(jié)論本文旨在研究非線性數(shù)字濾波器設(shè)計(jì)問(wèn)題?；诜€(wěn)健統(tǒng)計(jì)理論和雙邊濾波思想 文中提出穩(wěn)健的圖像復(fù)原統(tǒng)一框架 并 由此導(dǎo)出了一種數(shù)字濾波器的統(tǒng)一設(shè)計(jì)框架 簡(jiǎn)潔地建立了非 線性數(shù)字濾波器與最優(yōu)能量泛函框架之間的理論聯(lián)系?；诮y(tǒng) 一設(shè)計(jì)框架，文中提出了一種新型脈沖噪聲濾波器 即雙邊l濾波器。雙邊l1濾波器賦予噪聲點(diǎn)的權(quán)重相對(duì)于圖像信息的權(quán)重接近于零，更好地抑制了噪聲點(diǎn)對(duì)濾波過(guò)程的影響 是一種 比中值濾波器更為魯棒的濾

15、波機(jī)制。實(shí)驗(yàn)結(jié)果驗(yàn)證了雙邊l1濾波器抑制脈沖噪聲的有效性。(收稿日期：2006年2月)參考文獻(xiàn)：FARSIU S, ROBINSON M D, ELAD 虬 et al.Fast and robust multiframe super resolutionJ.IEEE Transactions on Image Processing, 2004, 13(10): 1327- 1344.TOMASI C, MANDUCHI R.Bilateral filtering for gray and color imagesC/ /Proc 6th Int Conf Computer Vision, New Delhi, India, 1998: 839- 846.ELAD M.On the bilateral filter an