文章编号:1006 - 7353 (2004) 01 - 0042 (14) - 04
迷宫最短路径问题的计算机解法
X
周丰
(武汉交通职业学院,湖北武汉430062)
摘要:本文应用数组、栈、队列等数据结构,针对数字化的迷宫图形,采用广度搜索
的程序设计思想,完成了迷宫最短路径问题的一种
计算机算法,并解决了搜索过程中的
循环绕道问题。
关键词:最短路径;算法;数据结构;栈;队列
中图分类号: TP 312 文献标识码:A
迷宫最短路径( the Shortest Path of Labyrinth) 问题是一个典型的搜索、遍历问题,其程序设计思想在许多计算机运算程序、计算机管理程序中均有应用。一般来说,用计算机解决一个具体问题时,大致需要经过下列几个步骤:首先要从具体问题抽象出一个适当的数学模型,然后设计一个解此数学模型的算法,最后编出程序,进行调试、调整, 直至得到最终解答。其中,寻求数学模型的实质是分析问题,从中提取操作的对象,并找出这些操作对象之间的关系,然后用数学语言加以描述。但是,迷宫最短路径问题处理的对象不仅仅是纯粹的数值,而且还包括字符、表格、图象等多种具有一定结构的数据, 这些非数值计算问题无法用数学方程加以
描
述,这就给程序设计带来一些新的问题。
1. 问题描述
迷宫最短路径问题即从一个迷宫的入口(Sourse) 到出口(Destination) 找出一条最短路径。求迷宫中从入口到出口的路径并找出其中最短者的计算机解法,应当用“穷举求解”的方法,即从入口出发,顺某一方向向前探索,若能走通,则继续往前走;否则沿原路
退回(回溯) ,换一个方向再继续探索,直至所有可能的通路都探索到并确定出最短路径
为止。为了保证在任何位置上都能沿原路退回,确保正确记录各个路径的长度,在求迷宫最短路径问题中应用诸如顺序表数组、栈、队
列等数据结构,也就是自然而然的事了。
2. 数据的输入与输出
迷宫最短路径问题的数据输入主要包括
程序规模、数字化迷宫形成、行进方向设定等。其数据输出包括迷宫图形和运行结果。
2. 1 输入迷宫问题的大小规模
采用m 行n 列数值矩阵描述迷宫。控
制问题规模的系数m、n 都应该是正整数,
反
映迷宫的长宽尺度。Pat (路墙比) 也是一个正整数,用来调整迷宫中0 与1 的个数比例。该数越大,迷宫中0 的个数越多,宫墙相对越少,迷宫越容易通过。
2. 2 建立数值迷宫图形
可用一个二维数组maze [m + 1 ] [ n + 1 ]
模拟该数值迷宫,由__________随机函数产生随机数
(Random Value) 0 或1 。数组元素为0 表示该位置允许通过,数组元素为1 表示该位置已被封锁,用以表示通路或宫墙。maze [ 1 ] 42
X 收稿日期:2003 - 11 - 16
第17 卷第1 期
2004 年2 月
高等函授学报(自然科学版)
Journal of Higher Correspondence Education (Natural Sciences)
Vol. 17 No. 1
February 2004
[1 ]和maze [ m] [ n ]分别为迷宫的入口和出口。这样便得到了以矩阵形式排列的迷宫数值模型。
2. 3 走向(Direction) 控制
用二维数组dire[ 8 ] [ 2 ]存放八个方向上
的位移量,如图1 所示[1 ] [2 ] 。
2. 4 数据输出
运行该程序首先输出模拟迷宫的二维数
组,若其中存在最短路径,则由出口回溯到入口,再打印这一条路径,如下所示[2 ] :
(m ,n) , (i ,j) , ?, (1 ,1)
若无通路,则打印:“There is no path !”
图1
3. 数据结构
本问题将用到多种类型的数据结构(Da2
ta St ructure) ,其优点在于实现了信息的隐蔽,即将一切用户不必了解的细节都封装在某种结构类型中。
3. 1 数组(Array)
数组是一种应用广泛的数据结构,其元
素之间的关系由下标体现,用二维数组模拟迷宫形象贴切。为了程序中判断方便,把迷宫扩展成为maze[m + 2 ] [ n + 2 ] ,扩展部分
的
元素(迷宫外围) 设置为1 ,相当于在迷宫周
围布上一圈不准通过的墙。这样,在迷宫的任何一个位置(i ,j) 上都有八个可供考虑的移
动方向。
3. 2 栈(Stack)
栈是回溯(Backt racking) 通道时常用的
一种数据结构,为了标志已经通过的位置,采用一个状态顺序栈status[m] [ n ] ,初值为0 。在寻找路径的过程中,若通过了位置(i ,j) ,则将元素status[ i ] [j ]设置为1 。
3. 3 队列(Queue)
队列是一种具有先进先出特点的线性数
据结构,为了记录寻找过程中到达的位置(点) 及其前一个位置(点) ,建立一个迷宫行进记录数组seat [m 3 n ] [ 3 ] 。对于某一个数组元素seat [p ] ,其中,seat [p ] [ 0 ]和seat [p ] [ 1 ]记下到达位置的坐标i 和j ,seat [p ] [ 2 ]
记
下其前一个位置在seat 数组中的下标。
4. 算法基本思想
迷宫最短路径问题的计算机算法(Algo2 rithm) 是一个对数字化图形的搜索问题,一
般采用狄克斯特拉(Dijkst ra ,1959) 算法。由于本问题具有迷宫中相邻两点路长恒为1
的
特点,可对该算法进行改进。
4. 1 基本算法思想
(1) 若已经到达出口,则停止搜索并输出
结果;否则执行第(2) 步。
(2) 若前面的道路被封锁,则改变前进方向并再次执行第(2) 步;否则执行第(3) 步。
(3) 前进一格并记录在案,然后转去执行
第(1) 步。
上述步骤基于一个简单的“顺时针规
则”,即按北、东北、东、??西北八个方向,依
次考虑前进的方向。这种方法称为广度搜索法(Breadth Search) 。
4. 2 具体实施
从入口maze [ 1 ] [ 1 ]开始,将其记入行进
记录数组seat ,譬如记入seat [ 1 ] ,并以它作
为第一个出发点,依次对八个方向进行搜索。若下一个位置maze [ i ] [j ]可通行且尚未经
过
(即maze [ i ] [ j ] = 0 且status [ i ] [ j ] = 0) ,则也记入seat 数组,譬如记在seat [p ] ,则在
seat [p ] [ 2 ]中要记下其前一个位置在seat
数
组中的下标1 。在八个方向都搜索过以后, 根据先进先出的原则从seat 数组中重新取
出
一个位置作为新的出发点。显然, seat 数组是作为一个顺序表示的队列出现的。
43
第17 卷第1 期
2004 年2 月
高等函授学报(自然科学版)
Journal of Higher Correspondence Education (Natural Sciences)
Vol. 17 No. 1
February 2004
重复以上过程, 若能够到达出口位置
maze [m] [ n ] ,表示已经找到最短路径。因为,我们采用的是广度搜索法,且每一层上的路径长度都相等,所以最先到达出口maze [m] [ n ]的路径一定属于最短路径。若seat
数组中已经没有位置可以作为新的出发点了,即迷宫中所有位置都搜索完毕,则表示迷宫没有通路。
利用“顺时针规则”虽能顺利地通过迷
宫,但实际上却走了许多弯路,即在不少的数组元素处会重复进出。因此,在第一次行进的过程中,计算机不但要确定当前的行进路线,还须利用栈在重复进出两次的方向上设
置一道“虚拟封锁门”;这样,当再次通过迷宫
时,便能从“虚拟封锁门”折回而避免绕道,好
象计算机变得聪明起来。计算机的这种本领是其“智能”的一种表现,当然,这种“智能”必
须由人通过栈等数据结构“教”会它。5. 算法细化参考
本算法采用类C 语言描述,其数据结构
部分前面已进行说明,此处不再赘述。
# include < stdio. h >
# include < stdlib. h >
# define M 50
# define N 60
int maze[M] [ N ] , status [M] [ N ] , dire [ 9 ] [ 3 ] , seat [3000 ] [3 ] ;
void function - the - shortest - path (int m ,int n)
/ / 0 < m ≤M - 2 ,0 < n ≤N - 2
{/ / 变量声明部分———对所用其它变量完成变
量声明
i = 0 ;/ / 此处开始给迷宫设置围墙
while (i < = n + 1)
{maze[0 ] [i ] = 1 ;maze[m + 1 ] [i ] = 1 ;
i = i + 1 ;}
i = 1 ;
while (i < = m + 1)
{maze[i ] [0 ] = 1 ;maze [i ] [ n + 1 ] = 1 ;i = i + 1 ;}
i = 1 ;
/ / 此处开始建立迷宫;并对标志数组初始化
while (i < = m)
{j = 1 ;
while (j < = n)
{maze [i ] [j ] = random(1) ;
/ / 随机函数产生0 或1 并赋予迷宫
/ / 可用Pat 值调整0 与1 的比例,然后打印迷
宫相应位置(略)
status [i ] [j ] = 0 ;j = j + 1 ;}
i = i + 1 ;}
/ / 读入dire 数组;按顺时针建立八个方向上的
位移(略) ;
/ / 寻找最短路径
if (maze [1 ] [1 ] = = 0 & & maze [m] [ n ] = = 0)
/ / 出入口都可通行{seat [1 ] [0 ] = 1 ;seat [1 ] [1 ] = 1 ;
/ / 迷宫入口记入seat [1 ]
seat [1 ] [2 ] = - 1 ;
/ / 假设迷宫入口的出发点存于seat [ - 1 ]
status [1 ] [1 ] = 1 ;
top = 1 ;
/ / top 指向seat 数组中最新记入迷宫通行点的位置f = 1 ;
/ / f 指向seat 数组中存放即将作为新出发点的位置j = 0 ;/ / j = 0 ,表示找不到最短路径;j = 1 ,表示
成功找到最短路径
while (f < = top) / / 以下为Critical Loop 循环
{i = 1 ;
while (i < = 8)
{/ / 从f 所指的出发点出发,对八个方向搜索可
通行的位置
x = seat [f ] [0 ] + dire[i ] [1 ] ;
y = seat [f ] [1 ] + dire[i ] [2 ] ;
if (x = = m & & y = = n)
{/ / 找到最短路径,打印输出
printf (“%d , %d \ n”,m ,n) ;
while (f ! = - 1)
{printf (“%d , %d \ n”, seat [ f ] [ 0 ] , seat [ f ]
[1 ]) ;
f = seat [f ] [2 ] ;}
j = 1 ;/ / 建立找到路径的标志
f = top ;}/ / 找到一条最短路径,为退出Critical Loop 停止搜索准备条件
else
{if (status [ x ] [ y ] = = 0 & & maze [ x ] [ y ] = =
44
第17 卷第1 期
2004 年2 月
高等函授学报(自然科学版)
Journal of Higher Correspondence Education (Natural Sciences)
Vol. 17 No. 1
February 2004
0)
{/ / 新的通行位置(x ,y) 记入seat 数组
top = top + 1 ;
seat [ top ] [0 ] = x ;seat [ top ] [1 ] = y ;
seat [ top ] [2 ] = f ;
status[ x ] [ y] = 1 ;}
i = i + 1 ;}/ / 继续搜索下一个方向
}/ / end of while (i < = 8)
f = f + 1 ;/ / 准备取出一个新的出发点
}/ / 此时,seat 数组中已经没有数据,退出Criti2
cal Loop 循环
}
if (j = = 0) printf (“There is no path !”) ;
/ / 迷宫无通路
else printf (“Sourse or Destination can ’t
pass !”) ;/ / 出口或入口被封锁
return ;}
/ / the end of function - the - shortest - path
6. 算法分析
6. 1 时间复杂性
这里选用渐进时间复杂度(Asymptotic
Time Complexity) 。作为问题的基本操作的
原操作,应是其重复执行次数和算法的执行时间成正比的原操作,多数情况下它是最深层循环内的语句中的原操作,它的执行次数和包含它的语句的频度(Frequency Count) 相同。因此,建立迷宫需要的时间为O (m 3
n) 。在最坏情况下有m 3 n - 1 个位置要进
入seat 数组,所以寻找路径也需要O (m 3
n) ,总的时间复杂性为O(m 3 n) 。
6. 2 空间复杂性
本问题的空间复杂度( Space Complexi2
ty) 与算法密切相关,它不仅需要存储空间来寄存迷宫本身所用的信息,还需要一些对数据进行操作的工作单元和存储一些实现计
算
所需信息的辅助空间。
其中,数组maze 、status、seat 所需要的空
间都与m 3 n 成正比,其余都是常数。所以, 总的空间复杂性为O(m 3 n) 。
此外,尚需说明的是,所谓当前位置“可通”,指的是未曾走到过的通道,即要求该位置不仅是通道,而且既不在当前路径上(否则所求路径就不是简单路径) ,也不是曾经纳入过路径的通道(否则只能在死胡同内转圈) 。一个迷宫的最短路径可能不止一条,本
算法只给出首先找到的一条。首先找到哪一条最短路径,与在任一位置上对八个方向的搜索次序有关,即与dire 数组元素值的排列
次序有关(如图1 所示) ,调整dire 数组元素值的排列次序,就可得到其它的最短路径。参考文献
[1 ]严蔚敏、吴伟民. 数据结构[M] . 北京:清华大学出版社,2002.
[2 ]郭洁志. 计算机软件实践[M] . 陕西:西北电讯出版社,1985.
[3 ]黄刘生、唐策善. 数据结构[M] . 安徽:中国科学技术大学出版社,2002.
[4 ]王立柱. C/ C + + 与数据结构[M] . 北京:清华大学出版社,2002.
45
第17 卷第1 期
2004 年2 月
高等函授学报(自然科学版)
Journal of Higher Correspondence Education (Natural Sciences)
Vol. 17 No. 1
February 2004__
算法分析与设计 查找迷宫的最短路径(深度算法) 计算机科学与技术12级 16班 2012/12/16
【摘要】：迷宫求解是一个古老的游戏，要在迷宫中找到出口，需要经过一连串的错误尝试才能找到正确的路径，有的时候甚至找不到路径。类似于给定一个m*n的矩形网格，设其左上角为起点S。一辆汽车从起点出发驶向右下角终点T。在若干网格处设置了障碍，表示该网格不可到达。设计一个算法，求汽车从起点S出发到达终点T的一条路线。用计算机求解这个问题时，我们通常采用的是回溯方法，即从入口出发，顺某方向向前探索，若能走通，则继续往前走；否则沿原路退回。换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事。当然还有其他的方法来解决，例如顺序表，深度优先遍历，广度优先遍历等。 【关键词】:最短路径; 时间复杂度;深度优先搜索 【Summary】Maze solving is an ancient game , you want to find the exit in the maze , need to go through a series of trial and error to find the right path , and sometimes not even find the path . A m * n rectangular grid , similar to a given set its upper-left corner as the starting point S . A car from the starting point towards the bottom right corner of the end of T . Set up barriers at certain grid , indicates that the grid is unreachable . Design an algorithm , find the car starting to reach the end point T, route from the starting point S . Use the computer to solve this problem , we usually use the backtracking method , that is, starting from the entrance , Shun forward to explore a direction , if we go through , and continue to move forward ; otherwise return along the same route . Continue to explore another direction , until all possible paths to explore to far . In order to ensure that in any position along the same route back , it is clear that the need to use a LIFO structure to save the path from the entrance to the current position . Therefore , in seeking labyrinth path algorithm application "stack" is the natural thing to do . Of course , there are other ways to solve , for example, the sequence table , depth-first traversal , breadth -first traversal . 【Key phrase】Shortest path ; time complexity ; deep-first search
实验报告 课程名称数据结构 实验名称迷宫最短路径 实验类型综合型 实验地点计405机房 实验日期2017.5.13 指导教师魏海平 专业软件工程 班级软件1601 学号1611030102 姓名寇春雷 辽宁石油化工大学计算机与通信工程学院
数据结构实验报告评分表
实验二迷宫最短路径 题目：迷宫最短路径 ⒈问题描述 从一个迷宫的入口到出口找出一条最短路经。用一个二维数组MAZE(1..m，1..n)模拟迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。MAZE(1，1)和MAZE(m，n)分别为迷宫的入口和出口。 ⒉基本要求 (1)输入数据 a.输入迷宫的大小m行和n列，两者为整数 b.由随机数产生0或1，建立迷宫。 (2)输出数据 首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示：(m，n)，……，(i，j)，……，(1，1) 如无通道，则打印： THERE IS NO PATH. ⒊实现提示 (1)数据结构 ①为了在程序中判断方便，把迷宫扩展成为MAZE(0..m+1，0..n+1)，扩展部分的元素 设置为1，相当于在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置(I，j)上都有八个可以移动的方向。 ②用二维数组MOVE(1..8，1..2)存放八个方向上的位置量，如图所示： (i+MOVE[1，1]，j+MOVE[1，2]) ，2]) ，2]) ，2])
③为了标志已经通过的位置，采用一个标志数组MARK（1..m，1..n）初值为0，在寻 找路径的过程中，若通过了位置（i，j），则将MARK（i，j）置为为1。 ④为了记录查找过程中到达位置及其前一位置，建立一个Q（1..m*n-1，0..2）数组， 对于某一个数组元素Q(P)，其中，Q(P，0)和Q(P，1)记下到达位置i和j，Q(P，2)记下其出发点在Q数组中的下标。 （2）算法基本思想 将入口（1，1）作为第一个出发点，依次在八个反方向上搜索可通行的位置，形成第一层新的出发点，然后对第一层中各个位置分别搜索他所在八个方向上的可通行位置，形成第二层新的出发点，…，如此进行下去，直至达到出口(m，n)或者迷宫所有位置都搜索完毕为止。 具体实施：从(m，n)开始，将其记入Q数组，比如记入Q(1)，以它作为第一个出发点，依次对八个方向进行搜索，若下一个位置(I，j)可通行并且尚未经过（即MAZE(i，j)=0 且MARK(i，j)=0），则记入Q数组，如记在Q(P)，则在Q(P，2)中要记下其出发点在Q数组中的下标1，在八个方向上都搜索过以后，根据先进先出的原则Q从数组中重新取出一个位置作为新的出发点（这里，我们实际上把Q数组作为一个顺序表示的队列），重复以上过程，若能达到位置(m ，n)，表示找到最短路径；若Q数组中已经没有位置可以作为新的出发点了，则表示迷宫没有通路。 4.需求分析 (1)以二维数组maze[M+2][N+2]表示迷宫，其中maze[i][0]和maze[i][N+1](0= 中国计量学院实验报告 实验课程：算法与数据结构实验名称：迷宫的最优路径班级：学号： 姓名：实验日期：2013-5-20 一．实验题目： 输入一迷宫 查找并输出迷宫的最优路径 实验成绩：指导教师： 二．算法说明 1.定义一个结构体来表示起点和末点的坐标,定义一个数组来存放迷宫. struct elem { int x;//行 int y;//列 }; //定义结构体 int M[10][10]; 2.给数组中空白处赋上从起点到该处步骤的值. int find(int n) { for(i=0;i<9;i++) for(j=0;j<10;j++) { if(M[i][j]==n) { {if (M[i][j+1]==0) M[i][j+1]=n+1; else if(M[i][j+1]>n+1) M[i][j+1]=n+1;} {if (M[i+1][j]==0) M[i+1][j]=n+1; else if(M[i+1][j]>n+1) M[i+1][j]=n+1;} {if (M[i][j-1]==0) M[i][j-1]=n+1; else if(M[i][j-1]>n+1) M[i][j-1]=n+1;} {if (M[i-1][j]==0) M[i-1][j]=n+1; else if(M[i-1][j]>n+1) M[i-1][j]=n+1;} } } } 3.给最优路径附上特定的值,方便最后的输出. for (;;) { if(M[q.x+1][q.y]==(n-1)) {q.x++;M[q.x][q.y]=0;} else {if(M[q.x][q.y-1]==(n-1)) {q.y--;M[q.x][q.y]=0;} else {if(M[q.x-1][q.y]==(n-1)) {q.x--;M[q.x][q.y]=0;} else if(M[q.x][q.y+1]==(n-1)) {q.y++;M[q.x][q.y]=0;}}} n--; if(e.x==q.x&&e.y==q.y) {M[e.x][e.y]=0; break;} } 计算机科学与技术专业《数据结构与算法》 课程设计报告 设计题目：迷宫路径求解专业： 学号： 姓名： 指导老师： 完成日期： 一、需求分析 迷宫路径求解：利用二维数组创建一个迷宫。编写一个算法能够完成输出走出迷宫的所有的路径。 二、设计概要 maze[9][11]={ {1,1,1,1,1,1,1,1,1,1,1}, {1,0,1,1,1,1,1,0,0,0,1}, {1,0,0,0,0,1,0,0,1,0,1}, {1,0,1,1,0,1,0,1,1,0,1}, {1,0,0,1,0,0,0,1,0,0,1}, {1,1,0,1,1,1,0,1,0,1,1}, {1,1,0,1,1,1,0,1,0,1,1}, {1,1,0,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1,1} }; 一个迷宫用m*n的二维数组存储，用“0”代表可以通行，用“1”代表墙壁，不可通行。迷宫有一个路口和一个出口，设入口坐标为（x1，y1），出口坐标（x2，y2）。从迷宫的一个位置向东、南、西、北任意一个方向移动一步，前面若为“0”，则可前进一步，否则通行受阻，不能前进，则按顺时针改变为下一个方向。用一个switch语句控制方向的选择, 如： switch(d) {case 0:i=stack[s].i-1;j=stack[s].j;break; /*向西*/ case 1:i=stack[s].i;j=stack[s].j+1;break; /*向南*/ case 2:i=stack[s].i+1;j=stack[s].j;break; /*向东*/ case 3:i=stack[s].i;j=stack[s].j-1;break; /*向北*/ } 在走的同时需要用一个与迷宫同样大小的二维数组mark来存储走过的路径。避免重走已经走不通的老路。 为了寻找从入口点到出口点的一条通路，首先从入口点出发，按照四个方向的次序，当可以向前移动一步时，就把当前的的坐标入栈，若从当前位置无法继续前进时就做出栈操作，从上一次的位置的下一个方向，向前试探前进。如果当前位置为出口时，则表明找到一条路径从入口到出口的路径，打印出路径。若做出栈时为空，且当前位置不是出口，则表明没有找到一条可以出去的路径。结束程序。 三、详细设计 1.数据类型的定义； struct BinTreeNode { int i; int j; int d; #include void PutOut_all(); //找所有路径和最短路径并输出所有路径 void PutOut_Grap(); //输出迷宫图形 void Migong(); //使用迷宫 void main() { cout<<"*******************欢迎使用迷宫系统 *******************\n"; while(1) { int i; cout<<"请选择你要的操作：\n" <<"1.使用系统自带迷宫\n" <<"2.使用新建迷宫\n" <<"0.退出\n"; cout<<"请输入："; cin>>i; switch(i) { case 1: Init_maze();Migong();break; case 2: NewCreat();Migong();break; case 0: return; 求迷宫中从入口到出口的 路径的算法及实现 涂海丽东华理工大学３４４０００ １．本次设计所用到的库函数有：输入输出函数（ｓｔｄｉｏ．ｈ）过程调用函数（ｐｒｏｃｅｓｓ．ｈ）动态存储分配函数（ｍａｌｌｏｃ．ｈ）。 ２．本程序的设计过程分三大块：主程序（ｍａｉｎ（））试探函数（ｓｅａｒｃｈ（））数据子文件（ｉｎｐｕｔ．ｃ）。主要过程就是：通过主程序调用数据文件，然后用一维数组来模拟二维数组进行动态存储，再从第一个入口开始，调用试探函数探测通路，把探测到的通路入栈，进入下一层调用。直到找出所有的通路，最后打印输出。 ｆｏｒ（ｉ＝－１ｉ＜＝１＋＋ｉ）／／在当前点的８各方向进行探测 ｆｏｒ（ｊ＝－１ｊ＜＝１＋＋ｊ）｛ｉｈ＝ｉ０＋ｉｊｈ＝ｊ０＋ｊｉｆ（（ｉ！＝０｜｜ｊ！＝０）ｉｈ＞＝０ｉｈ＜ｒｏｗ＆ｊｈ＞＝０ｊｈ＜ｃｏｌｔａｂ［ｉｈ］［ｊｈ］＝＝０） ｛／／判断条件ｉｅ１［ｉｒ］＝ｉｈ／／当前点入栈，进入下一层调用 ｉｅ２［ｉｒ］＝ｊｈｔａｂ［ｉｈ］［ｊｈ］＝１ｓｅａｒｃｈ（ｒｏｗ，ｃｏｌ，ｔａｂ，ｉｈ，ｊｈ，ｉｒ＋１，ｉｅ１，ｉｅ２，ｎｏ）ｔａｂ［ｉ ｈ］［ｊｈ］＝０｝｝｝ｍａｉｎ（）｛ＦＩＬＥ＊ｆｐｉｎｔｒｏｗ，ｃｏｌ，＊ｔａｂ１，＊＊ｔａｂ２，＊ｉｅ１，＊ｉｅ２，ｉｒ，ｎｏ，ｉ０，ｊ０，ｉ，ｊｉｆ（（ｆｐ＝ｆｏｐｅｎ（＂ｉｎｐｕｔ．ｃ＂，＂ｒ＂））＝＝ＮＵＬＬ）／／打开数据文件 ｛ｐｒｉｎｔｆ（＂ＴｈｅｏｐｅｎＥｒｒｏｒ！＂）ｅｘｉｔ（０）｝ｆｓｃａｎｆ（ｆｐ，＂％ｄ％ｄ＂，ｒｏｗ，ｃｏｌ）／／读入迷宫的矩阵行和列大小 ｔａｂ１＝（ｉｎｔ＊）ｍａｌｌｏｃ（（ｕｎｓｉｇｎｅｄ）ｃｏｌ＊ｒｏｗ＊ｓｉｚｅｏｆ（ｉｎｔ））／／申请动态存储区 ｔａｂ２＝（ｉｎｔ＊＊）ｍａｌｌｏｃ（（ｕｎｓｉｇｎｅｄ）ｒｏｗ＊ｓｉｚｅｏｆ（ｉｎｔ＊））／／ｔａｂ１一维数组来模拟ｔａｂ２二维 数组ｉｅ１＝（ｉｎｔ＊）ｍａｌｌｏｃ（（ｕｎｓｉｇｎｅｄ）ｃｏｌ＊ｓｉｚｅｏｆ（ｉｎｔ））ｉｅ２＝（ｉｎｔ＊）ｍａｌｌｏｃ（（ｕｎｓｉｇｎｅｄ）ｃｏｌ＊ｓｉｚｅｏｆ（ｉｎｔ））ｆｏｒ（ｉ＝０ｉ＜ｒｏｗ；ｉ＋＋）ｔａｂ２［ｉ］＝（ｔａｂ１［ｉ＊ｃｏｌ］）ｉ０＝０ｊ０＝０／／从入口（１，１）开始ｆｏｒ（ｉ＝０ｉ＜ｒｏｗ；＋＋ｉ）ｆｏｒ（ｊ＝０ｊ＜ｃｏｌ＋＋ｊ）ｆｓｃａｎｆ（ｆｐ，＂％ｄ＂，（ｔａｂ２［ｉ］［ｊ］））／／读入矩阵的内容 ｆｃｌｏｓｅ（ｆｐ）／／存入到ｔａｂ１中 三详细设计程序 ＃ｉｎｃｌｕｄｅ＜ｍａｌｌｏｃ．ｈ＞ ＃ｉｎｃｌｕｄｅ＜ｓｔｄｉｏ．ｈ＞＃ｉｎｃｌｕｄｅ＜ｐｒｏｃｅｓｓ．ｈ＞ｖｏｉｄｓｅａｒｃｈ（ｉｎｔｒｏｗ，ｉｎｔｃｏｌ，ｉｎｔ＊＊ｔａｂ，ｉｎｔｉ０，ｉｎｔｊ０，ｉｎｔｉｒ，ｉｎｔ＊ｉｅ１，ｉｎｔ＊ｉｅ２，ｉｎｔ＊ｎｏ）／／试探函数 ｛ｉｎｔｉ，ｊｈ，ｉｈ，ｊ，ｃｏｕｎｔｉｆ（ｉ０＝＝ｒｏｗ－１ｊ０＝＝ｃｏｌ－１）／／若能到达出口 ｛＋＋（＊ｎｏ）／／方法数加１ ｐｒｉｎｔｆ（＂＃－－－－－－－－－－－－－－－－Ｔｈｅ￣￣￣￣［％ｄ］ｔｈ￣￣￣￣￣Ｓｏｌｕｔｉｏｎ－－－－－－－－－－－－－－－－－－－－＃＼ｎ＂，＊ｎｏ）／／打印该种路径的出现顺序 ｐｒｉｎｔｆ（＂（％ｄ，％ｄ）＂，１，１）／／从入口开始打印 ｃｏｕｎｔ＝０／／输出换行计数 C语言课程设计报告题目：迷宫问题 姓名： 班级： 学号： 组员： 指导教师： 学院： 专业： 课程设计（报告）任务及评语 目录 第1章课程设计的目的与要求 (1) 1.1 课程设计目的 (1) 1.2 课程设计的实验环境 (1) 1.3 课程设计的预备知识 (1) 1.4 课程设计要求 (1) 第2章课程设计内容 (2) 2.1程序功能介绍 (2) 2.2程序整体设计说明 (2) 2.2.1设计思路 (2) 2.2.2数据结构设计及用法说明 (3) 2.2.3程序结构（流程图） (4) 2.2.4各模块的功能及程序说明 (6) 2.2.5程序结果 (7) 2.3程序源代码及注释 (7) 第3章课程设计总结 (17) 参考资料 (18) 第1章课程设计的目的与要求 1.1 课程设计目的 本课程设计是计算机科学与技术专业重要的实践性环节之一，是在学生学习完《程序设计语言(C)》课程后进行的一次全面的综合练习。本课程设计的目的和任务： 1. 巩固和加深学生对C语言课程的基本知识的理解和掌握 2. 掌握C语言编程和程序调试的基本技能 3. 利用C语言进行基本的软件设计 4. 掌握书写程序设计说明文档的能力 5. 提高运用C语言解决实际问题的能力 1.2 课程设计的实验环境 硬件要求能运行Windows 2000/XP操作系统的微机系统。C语言程序设计及相应的开发环境。 1.3 课程设计的预备知识 熟悉C语言及C语言开发工具。 1.4 课程设计要求 1. 分析课程设计题目的要求 2. 写出详细设计说明 3. 编写程序代码，调试程序使其能正确运行 4. 设计完成的软件要便于操作和使用 5. 设计完成后提交课程设计报告 最短路径及其他路径 #include void PutOut_Grap(); //输出迷宫图形 void Migong(); //使用迷宫 void main() { cout<<"*******************欢迎使用迷宫系统*******************\n"; while(1) { int i; cout<<"请选择你要的操作：\n" <<"1.使用系统自带迷宫\n" <<"2.使用新建迷宫\n" <<"0.退出\n"; cout<<"请输入："; cin>>i; switch(i) { case 1: Init_maze();Migong();break; case 2: NewCreat();Migong();break; case 0: return; default :cout<<"*****输入错误，请重新输入！*****\n";break; } } 迷宫最短路径问题新算法 摘要: 提出了求解迷宫最短路径问题的新算法, 该算法抛弃了 经典算法( 深度优先搜索和广度优先搜索) 中繁杂低效的递归、回溯思想。通过合理的变换, 将原问题转化为迷宫路径深度图的生成问题。最后对算法进行了严谨的分析和实例测 试, 显示出该算法易于理解、易于编程、时间空间复杂度低等优点。 关键词: 最短路径; 时间复杂度; 深度优先搜索; 广度优先搜索 New Algorithm for Solving Shortest Path of Maze Problem ZHANG Lin- feng, LV Hui, QU Jun- feng (The Missile Institute, Air Force Engineering University, Sanyuan, Shannxi 713800, China) Abstract: A new algorithm is presented for solving the shortest path of maze problem, which is not based on the inef- ficient recursive backtracking theory of classical algorithm (DFS- Depth First Search and BFS- Breadth First Search).By appropriate conversion, the algorithm changes the original problem into the creation of the maze graph problem.At last, an example is given, which shows that the new algorithm is easy to be understood and programmed as well as its low time and space complexity. Key words: shortest path; time complexity; Depth First Search; Breadth First Search 1 问题描述 迷宫最短路径(the shortest path of maze) 问题是一个典 型的搜索、遍历问题, 其程序设计思想在人工智能设计、机器人 设计等事务中均有应用。 如图 1 所示, 一个 N×M的大方块迷宫, 带斜线的单元格表 求迷宫问题就是求出从入口到出口的路径。在求解时, 通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通, 则继续往前走；否则沿原路退回,换一个方向再继续试探, 直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回（称为回溯）, 需要用一个后进先出的栈来保存从入口到当前位置的路径。 首先用如图3.3 所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径, 即在求得的路径上不能重复出现同一通道块。 为了表示迷宫, 设置一个数组mg,其中每个元素表示一个方块的状态, 为0 时表示对应方块是通道, 为1 时表示对应方块为墙, 如图3.3 所示的迷宫, 对应的迷宫数组mg如下: int mg[M+1][N+1]={ /*M=10,N=10*/ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} }; 伪代码： c 语言描述如下： void mgpath() /* 路径为:(1,1)->(M-2,N-2)*/ { int i,j,di,find,k; top++; /* 初始方块进栈*/ Stack[top].i=1; Stack[top].j=1; Stack[top].di=-1; mg[1][1]=-1; while (top>-1) /* 栈不空时循环*/ { i=Stack[top].i; j=Stack[top].j; di=Stack[top].di; if (i==M-2 && j==N-2) /* 找到了出口, 输出路径*/ { printf(" 迷宫路径如下:\n"); for (k=0;k<=top;k++) { printf("\t(%d,%d)",Stack[k].i,Stack[k] .j); if ((k+1)%5==0) printf("\n"); } 算法分析与设计 查找迷宫的最短路径(广度算法) 计算机科学与技术12级 16班 2012/12/16 【摘要】本论文提出了求解迷宫最短路径问题的经典广度优先搜索。通过合理的变换, 将原问题转化为迷宫路径深度图的生成问题。最后对算法进行了严谨的分析和实例测试。迷宫求解是一个古老的游戏，要在迷宫中找到出口，需要经过一连串的错误尝试才能找到正确的路径，有的时候甚至找不到路径。类似于给定一个m*n的矩形网格，设其左上角为起点S。一辆汽车从起点出发驶向右下角终点T。在若干网格处设置了障碍，表示该网格不可到达。设计一个算法，求汽车从起点S出发到达终点T的一条路线。用计算机求解这个问题时，我们通常采用的是回溯方法，即从入口出发，顺某方向向前探索，若能走通，则继续往前走；否则沿原路退回。换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事。当然还有其他的方法来解决，例如顺序表，深度优先遍历，广度优先遍历等。 【关键词】:最短路径; 时间复杂度;广度优先搜索 【Summary】Maze solving is an ancient game , you want to find the exit in the maze , need to go through a series of trial and error to find the right path , and sometimes not even find the path . A m * n rectangular grid , similar to a given set its upper-left corner as the starting point S . A car from the starting point towards the bottom right corner of the end of T . Set up barriers at certain grid , indicates that the grid is unreachable . Design an algorithm , find the car starting to reach the end point T, route from the starting point S . Use the computer to solve this problem , we usually use the backtracking method , that is, starting from the entrance , Shun forward to explore a direction , if we go through , and continue to move forward ; otherwise return along the same route . Continue to explore another direction , until all possible paths to explore to far . In order to ensure that in any position along the same route back , it is clear that the need to use a LIFO structure to save the path from the entrance to the current position . Therefore , in seeking labyrinth path algorithm application "stack" is the natural thing to do . Of course , there are other ways to solve , for example, the sequence table , depth-first traversal , breadth -first traversal . 【Key phrase】Shortest path ; time complexity ; breadth-first search 设计题目:迷宫问题求解 问题描述 迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫如下图A所示，求出一条从入口到出口的通路，或得出没有通路的结论。图A ●任务： ●功能要求： (1) 建立一个大小为m×n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在 屏幕上显示出来； （2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。 （3）用一种标志（如数字8）在迷宫中标出该条通路； （4）在屏幕上输出迷宫和通路； （5）上述功能可用菜单选择。 需求分析： 1.迷宫的建立： 迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述， 2.迷宫的存储： 迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。 注：其中M，N分别表示迷宫最大行、列数，本程序M、N的缺省值为39、39，当然，用户也可根据需要，调整其大小。 3.迷宫路径的搜索： 首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。 #include int pass(int maze[100][100],pos curpos) { if(maze[curpos.line][curpos.row]==0) return 1; else return 0; } void FootPrint( int maze[100][100],pos pos) { maze[pos.line][pos.row] = 1; } pos nextpos(int maze[100][100],SqStack curPos) { pos curpos=curPos.seat; switch(curPos.di) { case 1: ++curpos.line; break; case 2: ++curpos.row; break; case 3: --curpos.line; break; case 4: --curpos.row; break; } return curpos; } int MazePath(int maze[100][100],pos start,pos end) { pos curpos; SqStack e; top=0; curpos=start; e.di=1; e.seat=curpos; S[++top]=e; while(top!=0) { curpos=nextpos(maze,e); if(pass(maze,curpos)) 实验报告 课程名：数据结构（C语言版）实验名：迷宫问题II 姓名： 班级： 学号： 撰写时间：2014/10/10 一实验目的与要求 1. 了解栈的应用 2. 利用栈在迷宫中找到一条路 二实验内容 ?一个迷宫如图1所示, 是由若干个方格构成的一个矩形, 其中有唯一的 一个入口(用标示), 有唯一的一个出口(用△标示). 图中深色的方格无 法到达, 浅色的方格都是可以到达的. 每一次只能从当前方格前进到与当前方 格有公共边的方格中(因此前进方向最多有四个). ?本次实验的迷宫问题要求找到从入口到出口的最短的路. 图1：迷宫 三实验结果与分析 程序： #include int Qx[Znum+1], Qy[Znum+1], P[Znum+1], head=0, tail=0; for(i=0;i 数据结构课程设计指导 一、课程设计要求 课程设计是数据结构课程的一个综合实践练习，是有别于课程实验的一个独立实践教学环节。课程设计一般在课程结束后进行，教学时数为1周。具体要求如下： 1、结合实际问题进一步理解和深化课程理论知识，做到理论与实际相结合。 2、能对实际问题进行分析和抽象，并进行数据结构设计和算法设计，具有初步的分析问题和解决问题的能力。 3、了解软件工程的理论与方法，初步掌握软件开发过程中的需求分析、系统设计、编码、测试等基本方法和技能。 4、进一步强化编程训练，提高程序设计能力。 5、设计内容要有一定的深度和难度，达到一定工作量，代码量不低于500行。 二、课程设计内容 课程设计的主要工作如下： 1、问题定义与需求分析：根据设计题目的要求，对问题进行分析，确定系统的功能需求和性能需求。 2、数据结构与算法设计：对问题描述中涉及的数据对象定义相应的数据结构，包括逻辑结构、存储定义和主要操作。对主要算法要进行时间和空间复杂度分析。 3、概要设计：采用面向对象方法设计软件结构，定义类及类之间的关系。要求系统结构合理、易于实现。 4、详细设计：对数据结构和基本操作做进一步的求精，写出数据存储定义，用程序流程图或伪码对算法进行描述。 5、编码与测试：用C++编程实现系统，并设计测试用例对系统进行测试，修改程序中的错误，形成格式和风格良好的源程序清单。 6、设计结果分析：对系统应用效果进行分析，评价系统的先进性、实际应用价值及在在的问题。 7、撰写课程设计报告。 三、课程设计考核 课程设计考核内容包括设计作品和设计报告两个部分。设计作品包括可运行的源程序（刻录成光盘），系统使用说明，主要程序代码（打印附在课程报告内）。课程设计报告主要报告系统分析、设计和实现过程，内容如下： 1、问题定义及设计要求； 2、主要设计内容：详细报告课程设计中所做的主要工作，包括系统分析、概要设计、数据结构设计、算法设计及模块设计和编程及测试等。 3、总结与体会：写出本次课程设计的主要创新点及存在的问题。 4、参考文献：列出所参考的主要文献。 5、小组成员及分工。 课程设计成绩分两部分，设计报告占50％，设计作品占50％。评价因素主要有： 《数据结构与算法设计》 课程设计任务书 题目迷宫设计 学生姓名学号专业班级 设计内容与要求【问题描述】 在迷宫中求从入口到出口的一条简单路径。迷宫可用方块来表示，每个方块或者是通道或者是墙。“迷宫求解”这个经典的问题，应用栈这种数据结构设计一个方案，并在图形界面上实现从入口到出口的一条简单路径，设计这个游戏可以加强自己的编程能力，自己找通路时还可以加强观察能力。 【软件功能】 1、求解迷宫通路的图形界面演示程序，根据用户界面提示自定义迷宫。 2、根据用户界面提示，用键盘输入，Home键设置迷宫起点，End键设终点，上下左右箭头键移动，Enter键添加墙，Del键删除墙，完成后按F9键演示，演示完毕后可F5刷新题图，重新对地图的起点、终点、障碍进行设置，Esc 键退出； 3、在找迷宫通路的过程中，演示查找的过程并查找成功的一条路径。 4、用户可以通过界面上提供的菜单选项，选择“A*算法求最短路径”演示求解迷宫最短路径。 【算法思想】 1、以一个长方阵表示迷宫，采用数组对迷宫信息进行存储，数组的元素的值表示迷宫对应位置的内容。0表示迷宫对应位置可通过；1表示迷宫对应位置为墙；2表示迷宫对应位置为已经走过的足迹3，表示迷宫对应位置是从栈中弹出的点，并且不能再次通过；4表示迷宫对应位置为起点，保证起点不可通过。 2.在设计走迷宫算法的过程中，主要是利用栈对路径信息进行存储，类N ode，定义了栈中存储的节点元素的类型，栈中的元素采用链式存储的结构。 3、采用A*算法，找到起点到终点的最短路径； 4、采用回溯算法控制并绘制人物在迷宫图形界面窗口中的位置。 5、用java编程语言，有简单、美观的图形界面。 【提交成果】 1.“《数据结构与算法设计》课程设计任务书”一份，打印装袋； 2.“《数据结构与算法设计》课程设计报告”一份，打印装袋； 3、上面两项内容的word文档，通过电子邮件交到指导教师。 起止时间2012 年 6 月18日至2012 年7月 1 日指导教师签名2012年 6 月18 日系（教研室）主任签名2012年 6 月18 日学生签名 2012 年 6 月 18 日c语言实现迷宫最优路径选择
迷宫路径求解
迷宫-最短路径及所有路径的问题
求迷宫中从入口到出口的路径的算法及实现概要
C语言课程设计--迷宫
关于迷宫最短路径与所有路径的问题
迷宫最短路径问题新算法
求解迷宫问题(c语言,很详细哦)
算法分析与设计 查找迷宫的最短路径(广度算法)
迷宫求解-数据结构-课业设计
迷宫问题 输出路径
数据结构迷宫最短路径实验报告
数据结构课程设计指导书(2015)
迷宫算法设计
相关主题
文本预览