回溯法求解迷宫问题

遇 娜,简广宁

(1.天津市红桥区职工大学,天津市 300131;2.天津城市建设学院管理系,天津市 300384)

回溯法求解迷宫问题

遇 娜1,简广宁2

(1.天津市红桥区职工大学,天津市 300131;2.天津城市建设学院管理系,天津市 300384)

文章从深度优先探测法的设计思路入手,对构造的方块图迷宫进行分析,并详细介绍了该迷宫问题的设计思路及求解方法。迷宫中每一点用二维数组坐标表示,并采用堆栈存储数据,最终得出走出迷宫的最佳路径。

迷宫;深度优先算法;探测法;堆栈

一、问题描述

迷宫问题是机器智能中一种常见的问题,我们在生活中也会常常遇到这类问题:我们会顺着某一方向向前探索,如果遇到岔口,则要选择某一个路口前进,会出现两种可能性,若能走通,则继续往前走,最后顺利通到出口处;否则沿原路退回,换一个方向在继续探索,直至所有可能的通路都探索到为止。就要用到回溯的思想来解决这一问题。由于计算机在解迷宫问题时,通常是用的“穷举求解”的方法,既从入口出发,为了保证在任何位置上都能沿原路返回,显然需要一个后进先出的结构来保存从入口到当前位置的路径。因此在迷宫通路算法中还需要应用“栈”来存储数据。

如图:用图中所示的方块图表示迷宫。图中的白色方块方块表示通道,黑色方块表示墙。所求路径必须为简单路径,即在求得的路径上不能出现重复出现同一通道块。

二、设计思想

此程序是求迷宫中从入口到出口的所有路径。在搜索中还要建立一个堆栈,将所走过的路记录下来,后退时将退出的路从堆栈中弹出。这样保证了最终保存的是迷宫的一条出路。栈底元素为入口坐标,栈顶元素为迷宫的出口坐标。

假设“当前位置”指的是在搜索过程中某一时刻所在图中某个方块位置,则求迷宫中一条路径的算法的基本思想是:若当前位置“可通”,则纳入“当前路径”,并继续朝下一个位置探索,既切换“下一位置”为“当前位置”,如此重复直至到达出口;若当前位置“不可通”,则应顺着“来向”退回到“前一通道块”,然后朝着除来向之外的其他方向继续探索;若该通道块四个方向皆“不可通”,则应从当前位置上删除该通道块。所谓“下一位置”指的是“当前位置”四周四个方向上相邻的方块。假设以栈S为记录“当前路径”,则栈顶中存放的是“当前路径上最后一个通道块”。由此,“纳入路径”的操作既为“当前位置入栈”;“从当前路径上删除前一个通道块”的操作即为“出栈”。

三、概要设计

1.数据库。为了要存储所走过的路,每个记录要有:行,列坐标,搜索方向三个数据,而且数据库应组成堆栈形式,并用DEP作为栈顶指针,同时表示搜索深度。

2.产生规则。共有八条,可用数组D X和D Y表示方向增量:nx=x+dx(j);ny=y+dy(j)

if(nx,ny)是通路 then(nx,ny)是新结点

3.搜索策略。由于迷宫较大,为了防止溢出应采用非递归算法。

四、详细设计

1.迷宫的表示方法:

迷宫可以用一个二维数组A(X,Y)表示,其中,X表示行,Y表示列。数组中的元素由数字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.在搜索中还要建立一个堆栈,将所走过的路记录下来,后退时将退出的路从堆栈中弹出。这样保证了最终保存的是迷宫的一条出路。栈底元素为入口坐标,栈顶元素为迷宫的出口坐标。

五、流程图如下:

六、程序代码:

七、测试结果:

本程序通过上机在 Tubro C环境下调试通过,运行结果为:dow n right dow n dow n left dow n dow n right right right up right right。

通过调试可以运行出结果,并满足程序设计的基本思想(所走路线如下图箭头所指路线:下右下下左下下右右右上右右)。

八、总结分析

迷宫问题比较典型,关键是探索路径和方法,即在探索过程中记录走过的路径,能走通则继续走;如某一位置的下一位置走不通,则要沿原路退回,这点尤其重要。我们需要一个后进先出结构来保存从入口到当前位置的路径,所以对“栈”的应用必不可少。其次,对迷宫的表示方法也很重要,迷宫中每一点用二维数组坐标表示,当前位置四周的四个方向的点的坐标变化也要清楚。每走一步都要时时检测,对于此问题应掌握其方法和思想,不仅在迷宫问题,在其他很多问题中也能有所应用。对今后其他问题的研究会有很大帮助。

[1]严蔚敏,吴伟民编.数据结构(C语言版)[M].北京:清华大学出版社,1996.

[2]廖国勇,王广超.用遗传算法解迷宫问题[J].华东交通大学学报,2006,(02).

[3]涂海丽.求迷宫中从入口到出口的路径的算法及实现[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-),女,天津市人,天津市红桥区职工大学讲师,从事计算机方面的教学与研究。