迷宮最短路徑問題的計算機解法

1、迷宮 最短路徑 問題的計 算機解法 的信息目錄1. 問題描述12. 數(shù)據(jù)的輸入與輸出22.1. 輸入迷宮問題的大小規(guī)模22.2. 建立數(shù)值迷宮圖形22.3. 走向(directioro 控制22.4. 數(shù)據(jù)輸出23. 數(shù)據(jù)結構23.1. 數(shù)組(arroy)33.2. 棧(stock)33.3. 隊歹 34. 算法基本思想34.1. 基本算法思想34.1.1. 步驟一:34.1.2. 步驟二：34.1.3. 步驟三34.2. 具體實施44.2.1. 其一：44.2.2. 其二：45. 算法細化參考46. 算法分析56.1. 吋間復雜性56.1.1. 其一：56.1.2. 其二：56.2. 空間復

2、雜性56.2.1. 其一：56.2.2. 其二：6扳手1-11拉車1-21鋼材1-32迷宮最短路徑問題的計算機解法的信息迷宮最短路徑(the shortest path of labyrinth)問題是一個典型的搜索、遍歷問題其程 序設計思想在許多計算機運算程序、計算機管理程序中均有應用。一般來說用計算機解決一 個具體問題時.大致需要經(jīng)過下列幾個步驟:首先要從具體問題抽象出一個適當?shù)臄?shù)學模型然 后設計一個解此數(shù)學模型的算法最后編出程序進行調試、調整直至得到最終解答。其中尋 求數(shù)學模型的實質是分析問題從屮提取操作的對象并找出這些操作對彖z間的關系然后用 數(shù)學語言加以描述。但是，迷宮最短路徑問題處

3、理的對象不僅僅是純粹的數(shù)值，而且還包括字符、 表格、圖象等多種具冇一定結構的數(shù)據(jù)，這些非數(shù)值計算問題無法用數(shù)學方程加以描述，這就給 程序設計帶來一些新的問題。迷宮最短路徑(the shortest path of labyrinth)問題是一個典 型的搜索、遍歷問題其程序設計思想在許多計算機運算程序、計算機管理程序中均有應用。 一般來說用計算機解決一個具體問題時大致需要經(jīng)過下列兒個步驟:首先要從具體問題抽象 出一個適當?shù)臄?shù)學模型然后設計一個解此數(shù)學模型的算法最后編出程序謎行調試、調整直 至得到最終解答。其中，尋求數(shù)學模型的實質是分析問題，從中提取操作的對彖,并找出這些操 作對象z間的關系.然后

4、用數(shù)學語言加以描述。但是迷宮最短路徑問題處理的對象不僅僅是純 粹的數(shù)值而且還包括字符、表格、圖彖等多種具有一泄結構的數(shù)據(jù)這些非數(shù)值訃算問題無法 用數(shù)學方程加以描述.這就給程序設計帶來一些新的問題。1 問題描述迷宮最短路徑問題即從一個迷宮的入口(sourse)到lb (destination)找出一條最短路 徑。求迷宮屮從入口到出口的路徑并找出其屮最短者的計算機解法應當用“窮舉求解”的方 法即從入口出發(fā)，順某一方向向前探索若能走通，則繼續(xù)往前走否則沿原路退回(回溯),換一個 方向再繼續(xù)探索，直至所有對能的通路都探索到并確定出最短路徑為止o為了保證在任何位置 上都能沿原路退冋確保正確記錄各個路徑的

5、長度在求迷宮最短路徑問題屮應用諸如順序表 數(shù)組、棧、隊列等數(shù)據(jù)結構也就是自然而然的事了。扳手1-1拉車1-2鋼材1-32. 數(shù)據(jù)的輸入與輸出迷宮最短路徑問題的數(shù)據(jù)輸入主要包括程序規(guī)模、數(shù)字化迷宮形成、行進方向設定等。 其數(shù)據(jù)輸出包括迷宮圖形和運行結果。2.1. 輸入迷宮問題的大小規(guī)模釆用m行門列數(shù)值矩陣描述迷宮。控制問題規(guī)模的系數(shù)m、n都應該是正整數(shù).反映迷 宮的長寬尺度。(路墻比)也是一個正整數(shù)用來調整迷宮中0與1的個數(shù)比例。該數(shù)越人 迷宮中0的個數(shù)越多，宮墻相對越少謎宮越容易通過。22建立數(shù)值迷宮圖形可用一個二維數(shù)組moze m 4- 1 n 4- 1 模擬該數(shù)值迷宮由隨機函數(shù)產(chǎn)生隨機數(shù)

6、(random value) 0或1。數(shù)組元素為0表示該位置允許通過數(shù)組元素為1表示該位置已被封 鎖，用以表示通路或宮墻。和mozem 口分別為迷宮的入口和出口。這樣便得到了 以矩陣形式排列的迷宮數(shù)值模型。2.3. 走向(direction)控制用二維數(shù)組dire 82 存放八個方向上的位移量。2.4. 數(shù)據(jù)輸岀運行該程序首先輸出模擬迷宮的二維數(shù)組，若其中存在最短路徑則由出口冋溯到入口 再 打印這一條路徑如下所示(m .n). (i ,j).(1.1喏無通路則打?。?quot;there is no path ! ”3. 數(shù)據(jù)結構本問題將用到多種類型的數(shù)據(jù)結構(das structure)其優(yōu)

7、點在于實現(xiàn)了信息的隱蔽.即將 一切用戶不必了解的細節(jié)都封裝在某種結構類型中。3.1. 數(shù)組(array)數(shù)組是一種應用廣泛的數(shù)據(jù)結構其元素之間的關系由下標體現(xiàn)，用二維數(shù)組模擬迷宮形 彖貼切。為了程序中判斷方便把迷宮擴展成為mazem + 2 門+ 2 .擴展部分的元素(迷宮外 圍)設置為1 相當于在迷宮周圍布上一圈不準通過的墻。這樣在迷宮的任何一個位置(ij)上 都有八個可供考慮的移動方向。3.2. 棧(stack)棧是回溯(bockt racking)通道時常用的一種數(shù)據(jù)結構.為了標志已經(jīng)通過的位置采用一 個狀態(tài)順序ttstatusm n 初值為0。在尋找路徑的過程中若通過了位置(i j)

8、則將元素 status訂j 設置為1 o3.3. 隊列(queue)隊列是一種具有先進先出特點的線性數(shù)據(jù)結構，為了記錄尋找過程中到達的位置(點)及 其前一個位置(點)，建立一個迷宮行進記錄數(shù)組seot m 3 n 3 。對于某一個數(shù)組元素seat p ，其屮,seat p 0 jfflseat p 1 記下到達位置的坐標i利.seat p 2 記下其前一個位 置在seat數(shù)組中的下標。4. 算法基本思想迷宮最短路徑問題的計算機算法(algorithm)是一個對數(shù)字化圖形的搜索問題，一般采用 狄克斯特fe(dijkst ra ,1959)算法。由于本問題具有迷宮中相鄰兩點路長恒為1的特點，可對該

9、 算法進行改進。4.1.基本算法思想4.1.1. 步驟一：若已經(jīng)到達出口，則停止搜索并輸出結果;否則執(zhí)行步驟二。4.1.2. 步驟二若前面的道路被封鎖，則改變前進方向并再次執(zhí)行步驟二;否則執(zhí)行步驟三。4.1.3. 步驟三前進一格并記錄在案，然后轉去執(zhí)行步驟一。上述步驟基于一個簡單的“順時針規(guī)則”，即按北、東北、東、西北八個方向，依次考慮 前進的方向。這種方法稱為廣度搜索法(breadth search)。4.2.具體實施4.2.1. 其一:從入口他在11開始將其記入行進記錄數(shù)組sex,譬如記入seat 1，并以它作為第 一個出發(fā)點，依次對八個方向進行搜索。若下一個位置moze ij 可通行且尚

10、未經(jīng)過(即maze i j = 0 且status i j = 0).則也記aseat 數(shù)組.譬如記在seat p.則在seot p 2 中 要記下其前一個位置在seat數(shù)組小的下標1。在八個方向都搜索過以后根據(jù)先進先出的原 則從seat數(shù)組屮重新取岀一個位置作為新的出發(fā)點。顯然seat數(shù)組是作為一個順序表示的 隊列出現(xiàn)的。重復以上過程，若能夠到達出口位置mazemn,已經(jīng)找到最短路徑。因 為我們采用的是廣度搜索法但每一層上的路徑長度都相等所以最先到達出口mazem n 的路徑一定屬于最短路徑。若sex數(shù)組中已經(jīng)沒有位置可以作為新的出發(fā)點了即迷宮中所有 位置都搜索完畢則表示迷宮沒有通路。利用“

11、順時針規(guī)則”雖能順利地通過迷宮但實際上卻 走了許多彎路，即在不少的數(shù)組元素處會重復進出。因此在第一次行進的過程中，計算機不但 要確定當前的行進路線，還須利用棧在重復進出兩次的方向上設置一道“虛擬封鎖門”；這樣, 當再次通過迷宮時.便能從“虛擬封鎖門”折冋而避免繞道好象計算機變得聰明起來。計算機 的這種本領是其“智能”的一種表現(xiàn)當然這種“智能”必須由人通過棧等數(shù)據(jù)結構"教”會 它。4.2.2. 其二:從入口moze 1 1 開始將其記入行進記錄數(shù)組se叫譬如記入sex 1 并以它作為第 個出發(fā)點依次對八個方向進行搜索。若下一個位置mcize i j阿通行且尚未經(jīng)過(即maze i j

12、= 0 jlstatus i j = 0)，貝9也記aseat 數(shù)縱譬如記在seat p ，則在seat p 2 小 要記下其前一個位置在seat數(shù)組中的下標1 o在八個方向都搜索過以后，根據(jù)先進先出的原 則從seat數(shù)組中重新取出一個位置作為新的出發(fā)點。顯然sex數(shù)組是作為一個順序表示的 隊列出現(xiàn)的。重復以上過程 若能夠到達出口位置maze m a ,表示已經(jīng)找到最短路徑。因 為我們采用的是廣度搜索法且每一層上的路徑長度都相等所以最先到達出口mazem n 的路徑一定屬于最短路徑。若seat數(shù)組中已經(jīng)沒有位置可以作為新的出發(fā)點了即迷宮屮所有 位置都搜索完畢，則表示迷宮沒有通路。利用“順時針規(guī)

13、則”雖能順利地通過迷宮，但實際上卻 走了許多彎路，即在不少的數(shù)組元素處會重復進出。因此在第一次行進的過程中，計算機不但 要確定當前的行進路線.還須利用棧在重復進出兩次的方向上設置一道“煨擬封鎖門”；這樣. 當再次通過迷宮吋便能從“虛擬封鎖門”折回而避免繞道.好象計算機變得聰明起來。計算機 的這種木領是其“智能”的一種表現(xiàn)當然這種“智能”必須由人通過棧等數(shù)據(jù)結構“教”會 它。5. 算法細化參考本算法采用類c語言描述.其數(shù)據(jù)結構部分前面已進行說明.此處不再贅述。6.算法分析6.1.時間復雜性6.1.1. 其一:這里選用漸進時間復雜度(asymptotic time complexity)。作為問題

14、的基本操作的原操 作，應是其重復執(zhí)行次數(shù)和算法的執(zhí)行時間成正比的原操作，多數(shù)情況下它是最深層循環(huán)內(nèi)的 語句中的原操作它的執(zhí)行次數(shù)和包含它的語句的頻度(frequency count)相同。因此建立迷 宮需要的時間為o (m3門)。在最壞情況下有m3n-1個位置要進aseat數(shù)組所以尋找路徑 也需要o (m 3 n)，總的時間復雜性為o(m 3 n)。這里選用漸進時間復雜®(asymptotic time complexity)。作為問題的基本操作的原操作，應是其重復執(zhí)行次數(shù)和算法的執(zhí)行時間成正比 的原操作多數(shù)情況下它是最深層循環(huán)內(nèi)的語句屮的原操作它的執(zhí)行次數(shù)和包含它的語句的 頻度(f

15、requency count)相同。因此建立迷宮需要的時間為o (m 3 n)。在最壞情況下有m3門 -1個位置要進aseat數(shù)組.所以尋找路徑也需要o (m3門)總的時間復雜性為o(m 3門)。6.1.2. 其二這里選用漸進時間復雜®(asymptotic time complexity) o作為問題的基本操作的原操 作應是其重復執(zhí)行次數(shù)和算法的執(zhí)行吋間成正比的原操作.多數(shù)情況下它是最深層循環(huán)內(nèi)的 語句屮的原操作，它的執(zhí)行次數(shù)和包含它的語句的頻/(frequency count)相同。因此建立迷 宮需要的時間為o (m3門)。在最壞情況下有m3n-1個位置要進aseat數(shù)組,所以尋

16、找路徑 也需要o(m3n),總的時間復雜性為o(m3a)。62空間復雜性6.2.1. 其一:本問題的空間復雜度(space complexity)與算法密切相關,它不僅需要存儲空間來寄存 迷宮本身所用的信息，還需要一些對數(shù)據(jù)進行操作的工作單元和存儲一些實現(xiàn)計算所需信息 的輔助空間。其中擻組maze、status seat所需要的空i'可都與m 3 n成正比.其余都是常 數(shù)。所以總的空間復雜性為o(m3門)o此外尚需說明的是所謂當前位置“可通” 指的是未 曾走到過的通道，即要求該位置不僅是通道，而且既不在當前路徑上(否則所求路徑就不是簡單 路徑)，也不是曾經(jīng)納入過路徑的通道(否則只能在死

17、胡同內(nèi)轉圈)o 一個迷宮的最短路徑可能 不止一條本算法只給出首先找到的一條。首先找到哪一條最短路徑，與在任一位置上對八個方 向的搜索次序有關即與dire數(shù)組元素值的排列次序有關(如圖1所示)調整dire數(shù)組元素值 的排列次序就可得到其它的最短路徑。本問題的空間復雜度(space complexity)與算法密切 相關,它不僅需要存儲空間來寄存迷宮本身所用的信息，述需要一些對數(shù)據(jù)進行操作的工作單 元和存儲一些實現(xiàn)計算所需信息的輔助空間。其中，數(shù)組mee、status, seat所需要的空 間都與m3n成正比其余都是常數(shù)。所以總的空間復雜性為o(m3q)。此外尚需說明的是.所謂當前位置“可通”，指的是未曾走到過的通道，即要求該位置不僅是通道，而且既不在當前 路徑上（否則所求路徑就不是簡單路徑），也不是曾經(jīng)納入過路徑的通道（否則只能在死胡同內(nèi) 轉圈）。一個迷宮的最短路徑可能不止一條本算法只給出首先找到的一條。首先找到哪一條 最短路徑與在任-位置上對八個方向的搜索次序有關.即與dire數(shù)組元素值的排列次序有關 （如圖1所示）調整dire數(shù)組元素值的排列次序就可得到其它的最短路徑。6.2.2. 其二：本問題的空間復雜度（space complexity ）與算法密切相關它不僅需要存儲空i'可來寄存 迷宮本身所用的信息還需要一些対數(shù)據(jù)進行操作的工作單元和存儲一些實現(xiàn)訃算所需信