回溯法求解迷宮問題

遇 娜,簡廣寧

(1.天津市紅橋區(qū)職工大學,天津市 300131;2.天津城市建設(shè)學院管理系,天津市 300384)

回溯法求解迷宮問題

遇 娜1,簡廣寧2

(1.天津市紅橋區(qū)職工大學,天津市 300131;2.天津城市建設(shè)學院管理系,天津市 300384)

文章從深度優(yōu)先探測法的設(shè)計思路入手,對構(gòu)造的方塊圖迷宮進行分析,并詳細介紹了該迷宮問題的設(shè)計思路及求解方法。迷宮中每一點用二維數(shù)組坐標表示,并采用堆棧存儲數(shù)據(jù),最終得出走出迷宮的最佳路徑。

迷宮;深度優(yōu)先算法;探測法;堆棧

一、問題描述

迷宮問題是機器智能中一種常見的問題,我們在生活中也會常常遇到這類問題:我們會順著某一方向向前探索,如果遇到岔口,則要選擇某一個路口前進,會出現(xiàn)兩種可能性,若能走通,則繼續(xù)往前走,最后順利通到出口處;否則沿原路退回,換一個方向在繼續(xù)探索,直至所有可能的通路都探索到為止。就要用到回溯的思想來解決這一問題。由于計算機在解迷宮問題時,通常是用的“窮舉求解”的方法,既從入口出發(fā),為了保證在任何位置上都能沿原路返回,顯然需要一個后進先出的結(jié)構(gòu)來保存從入口到當前位置的路徑。因此在迷宮通路算法中還需要應(yīng)用“?！眮泶鎯?shù)據(jù)。

如圖:用圖中所示的方塊圖表示迷宮。圖中的白色方塊方塊表示通道,黑色方塊表示墻。所求路徑必須為簡單路徑,即在求得的路徑上不能出現(xiàn)重復出現(xiàn)同一通道塊。

二、設(shè)計思想

此程序是求迷宮中從入口到出口的所有路徑。在搜索中還要建立一個堆棧,將所走過的路記錄下來,后退時將退出的路從堆棧中彈出。這樣保證了最終保存的是迷宮的一條出路。棧底元素為入口坐標,棧頂元素為迷宮的出口坐標。

假設(shè)“當前位置”指的是在搜索過程中某一時刻所在圖中某個方塊位置,則求迷宮中一條路徑的算法的基本思想是:若當前位置“可通”,則納入“當前路徑”,并繼續(xù)朝下一個位置探索,既切換“下一位置”為“當前位置”,如此重復直至到達出口;若當前位置“不可通”,則應(yīng)順著“來向”退回到“前一通道塊”,然后朝著除來向之外的其他方向繼續(xù)探索;若該通道塊四個方向皆“不可通”,則應(yīng)從當前位置上刪除該通道塊。所謂“下一位置”指的是“當前位置”四周四個方向上相鄰的方塊。假設(shè)以棧S為記錄“當前路徑”,則棧頂中存放的是“當前路徑上最后一個通道塊”。由此,“納入路徑”的操作既為“當前位置入?！?“從當前路徑上刪除前一個通道塊”的操作即為“出?！薄?/p>

三、概要設(shè)計

1.數(shù)據(jù)庫。為了要存儲所走過的路,每個記錄要有:行,列坐標,搜索方向三個數(shù)據(jù),而且數(shù)據(jù)庫應(yīng)組成堆棧形式,并用DEP作為棧頂指針,同時表示搜索深度。

2.產(chǎn)生規(guī)則。共有八條,可用數(shù)組D X和D Y表示方向增量:nx=x+dx(j);ny=y+dy(j)

if(nx,ny)是通路 then(nx,ny)是新結(jié)點

3.搜索策略。由于迷宮較大,為了防止溢出應(yīng)采用非遞歸算法。

四、詳細設(shè)計

1.迷宮的表示方法:

迷宮可以用一個二維數(shù)組A(X,Y)表示,其中,X表示行,Y表示列。數(shù)組中的元素由數(shù)字0和1組成,當A(X,Y)=1時表示墻;當A(X,Y)=0時表示路。

2.搜索方向的識別:

對于迷宮中的任意一點A(X,Y),有四個搜索方向:向上A(X-1,Y);向下A(X+1,Y);向左A(X,Y-1);向右 A(X,Y+1)。

3.搜索方向的表示方法:

(0,-1)表示向左;(0,1)表示向右;(-1,0)表示向上;(1,0)表示向下

4.向某個方向試探一步:

在搜索時一定要注意,任何一點的坐標加上搜索方向的坐標增量后,都要判斷是否超出了迷宮的邊界。當不出界時,A(X,Y)=0表示該方向為通路。

5.當從死胡同退出時,要將路堵死,可將其標記為2。

6.在搜索中還要建立一個堆棧,將所走過的路記錄下來,后退時將退出的路從堆棧中彈出。這樣保證了最終保存的是迷宮的一條出路。棧底元素為入口坐標,棧頂元素為迷宮的出口坐標。

五、流程圖如下:

六、程序代碼:

七、測試結(jié)果:

本程序通過上機在 Tubro C環(huán)境下調(diào)試通過,運行結(jié)果為:dow n right dow n dow n left dow n dow n right right right up right right。

通過調(diào)試可以運行出結(jié)果,并滿足程序設(shè)計的基本思想(所走路線如下圖箭頭所指路線:下右下下左下下右右右上右右)。

八、總結(jié)分析

迷宮問題比較典型,關(guān)鍵是探索路徑和方法,即在探索過程中記錄走過的路徑,能走通則繼續(xù)走;如某一位置的下一位置走不通,則要沿原路退回,這點尤其重要。我們需要一個后進先出結(jié)構(gòu)來保存從入口到當前位置的路徑,所以對“?！钡膽?yīng)用必不可少。其次,對迷宮的表示方法也很重要,迷宮中每一點用二維數(shù)組坐標表示,當前位置四周的四個方向的點的坐標變化也要清楚。每走一步都要時時檢測,對于此問題應(yīng)掌握其方法和思想,不僅在迷宮問題,在其他很多問題中也能有所應(yīng)用。對今后其他問題的研究會有很大幫助。

[1]嚴蔚敏,吳偉民編.數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].北京:清華大學出版社,1996.

[2]廖國勇,王廣超.用遺傳算法解迷宮問題[J].華東交通大學學報,2006,(02).

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

[4]朱素英.迷宮問題的圖論解法探討[J].湖南人文科技學院學報,2006,(03).

Solving the M azing Problems by Using the Back tracking M ethods

YU Na1,JIAN Guang-ning2
(1.Tianjin Hongqiao D istrict Staf f and Workers University,Tianjin 300131 China;2.Tianjin Institute of U rban Construction,Tianjin 300384 China)

This article does analyses of the block chart maze f rom the perspective of dep th-first p robe method and gives a detailed account of the design thoughts and solving methods about the mazing p roblems.In themaze chart,every spot is show n by the tw o-dimensional array coordinate and uses the stack store data to get the best w ay out of the maze.

dep th-first algorithm;p robe method;stack

TP312

A

1673-582X(2011)08-0046-04

2010-10-10

遇娜(1977-),女,天津市人,天津市紅橋區(qū)職工大學講師,從事計算機方面的教學與研究。