基于路徑標記法的迷宮問題求解

王文霞

（運城學院計算機科學與技術系，山西　044000）

基于路徑標記法的迷宮問題求解

王文霞

（運城學院計算機科學與技術系，山西044000）

0　引言

迷宮問題在我們的生活中常常遇到，例如我們順著某一方向向前進行探索，遇到岔口，則要選擇某一路口繼續前進，這樣會出現兩種情況：若能走通，繼續前進，直到出口；否則沿原路退回，選擇另一方向繼續探索，直到所有通路都探索到為止。國內外許多學者對迷宮問題進行了研究，從LEE算法開始有了很多不同的迷宮求解的改進方法［1-2］。本文中，利用遞歸函數visit（）用”2”標記搜索過程中的位置，可方便求得復雜迷宮的解；同時為了使迷宮中每個點判斷都有四個方向，在生成的迷宮外圍增加了一圈用1表示的墻［3-4］。例如圖1所示的用一個二維數組A［8，10］的矩陣表示的迷宮，下標從（0,0）開始。其中，圖中0表示通道，1表示障礙物，左上角（1，1）為入口，右下角（6，8）為出口。

圖1　8×10的矩陣

1　算法思想

此算法采用（0，1）組成的矩陣模擬復雜迷宮，通路用◇表示，障礙用■表示，調用visit（）函數，求出從入口（1，1）到出口（6，8）所有路徑，最后對矩陣中的所有路徑進行遞增排序且進行了二次轉化，并顯示出運行結果。

2　算法步驟

（1）在txt文檔中任意輸入一個由0、1組成的矩陣（也可通過隨機函數生成矩陣）；

（2）調用文件函數fopen（）打開用矩陣表示的迷宮；

（3）轉換迷宮；迷宮中除外圍墻外，所有迷宮中的1用□表示，迷宮中的0用■表示，轉換后的圖如圖2所示。

圖2　迷宮轉換圖

（4）從入口a（1，1）開始，依次對a［i］［j+1］、a［i+1］［j］、a ［i］［j-1］、a［i-1］［j］四個方向調用visit（）遞歸函數進行判斷，如能走通則把相對應位置置成2，直到走到迷宮出口a［6］［8］即表示迷宮有一條路徑，把此矩陣作為一個數組元素放在maze數組中，jilu++表示路徑條數加1。

（5）通過對maze數組中的所有元素進行統計2的個數（2表示通路）放于num變量中，即可統計出迷宮中每條路徑的長度，最后對2表示的通路進行二次轉換變為◇。

（6）對矩陣中的路徑長度進行簡單的選擇排序。

3　算法實現

本算法采用C語言在VC++環境下實現，其數據結構類型及核心代碼實現所下。

｝｝//迷宮所有路徑遞增排序

迷宮中所有路徑遞增排序的運行結果如圖3所示。

圖3　迷宮遞增排序路徑

4　結語

迷宮問題比較典型，其通路的路徑不只一條，本算法不僅給出了最短路徑，也給出了其他次短路徑。另外，本算法是通過文件函數調用的迷宮txt文檔，這樣就可以任意輸入一個txt文檔表示矩陣，從而達到對任意復雜迷宮路徑的求解。

［1］嚴蔚敏,吳偉民.數據結構［M］.北京:清華大學出版社,2011.

［2］王曉東.計算機算法設計與分析［M］.北京：電子工業出版社，2007.

［3］涂海麗.求迷宮中從入口到出口的路徑的算法及實現［J］.中國科技信息,2008,（23）.

［4］遇娜,簡廣寧.回溯法求解迷宮問題［J］.天津職業學院校聯合學報，2011（13）.

Mark Location；Matrix Representation；Maze；Path Solution

Maze Problem's Solution Based on Marking Path Location Method

WANG Wen-xia

（Department of Computer Science and Technology,Yuncheng University,Yuncheng Shanxi,044000）

1007-1423（2015）32-0039-03

10.3969/j.issn.1007-1423.2015.32.010

王文霞（1979-），女，山西運城人，講師，碩士研究生，研究方向為算法分析

2015-10-22

2015-11-10

基于標記搜索位置的方法并以矩陣表示法表示迷宮，提出一種對復雜迷宮路徑的簡潔求解算法。該算法不僅可以獲得迷宮從入口到出口的最短距離，而且可以得到以遞增排序的次短距離等有意義的批量信息。

標記位置；矩陣表示；迷宮；路徑求解

運城學院教學改革研究項目（No.JG201418）

Based on the method of marking location to search and the matrix representation to said a maze,proposes a simple algorithm to solve complex maze path.The algorithm can obtain the shortest distance of the maze from entrance to exit,and can get more meaningful information by increasing sort.