基于路徑標(biāo)記法的迷宮問題求解

王文霞

（運城學(xué)院計算機科學(xué)與技術(shù)系，山西　044000）

基于路徑標(biāo)記法的迷宮問題求解

王文霞

（運城學(xué)院計算機科學(xué)與技術(shù)系，山西044000）

0　引言

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

圖1　8×10的矩陣

1　算法思想

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

2　算法步驟

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

（2）調(diào)用文件函數(shù)fopen（）打開用矩陣表示的迷宮；

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

圖2　迷宮轉(zhuǎn)換圖

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

（5）通過對maze數(shù)組中的所有元素進(jìn)行統(tǒng)計2的個數(shù)（2表示通路）放于num變量中，即可統(tǒng)計出迷宮中每條路徑的長度，最后對2表示的通路進(jìn)行二次轉(zhuǎn)換變?yōu)椤蟆?/p>

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

3　算法實現(xiàn)

本算法采用C語言在VC++環(huán)境下實現(xiàn)，其數(shù)據(jù)結(jié)構(gòu)類型及核心代碼實現(xiàn)所下。

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

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

圖3　迷宮遞增排序路徑

4　結(jié)語

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

［1］嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)［M］.北京:清華大學(xué)出版社,2011.

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

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

［4］遇娜,簡廣寧.回溯法求解迷宮問題［J］.天津職業(yè)學(xué)院校聯(lián)合學(xué)報，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

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

標(biāo)記位置；矩陣表示；迷宮；路徑求解

運城學(xué)院教學(xué)改革研究項目（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.