迷宫问题算法
Python基于递归算法实现的走迷宫问题
本文实例讲述了Python基于递归算法实现的走迷宫问题。分享给大家供大家参考，具体如下：
什么是递归?
简单地理解就是函数调用自身的过程就称之为递归。
什么时候用到递归？
如果一个问题可以表示为更小规模的迭代运算，就可以使用递归算法。
迷宫问题：一个由0或1构成的二维数组中，假设1是可以移动到的点，0是不能移动到的点，如何从数组中间一个值为1的点出发，每一只能朝上下左右四个方向移动一个单位，当移动到二维数组的边缘，即可得到问题的解，类似的问题都可以称为迷宫问题。
在python中可以使用list嵌套表示二维数组。假设一个6*6的迷宫,问题时从该数组坐标[3][3]出发，判断能不能成功的走出迷宫。
maze=[[1,0,0,1,0,1],
[1,1,1,0,1,0],
[0,0,1,0,1,0],
[0,1,1,1,0,0],
[0,0,0,1,0,0],
[1,0,0,0,0,0]]
针对这个迷宫问题，我们可以使用递归的思想很好的解决。对于数组中的一个点，该点的四个方向可以通过横纵坐标的加减轻松的表示，每当移动的一个可移动的点时候，整个问题又变为和初始状态一样的问题，继续搜索四个方向找可以移动的点，知道移动到数组的边缘。
所以我们可以这样编码：
# 判断坐标的有效性，如果超出数组边界或是不满足值为1的条件，说明该点无效返回False，否则返回True。
def valid(maze,x,y):
if (x>=0 and x<len(maze) and y>=0 and y<len(maze[0]) and maze[x][y]==1):
return True
else:
return False
# 移步函数实现
def walk(maze,x,y):
# 如果位置是迷宫的出口，说明成功走出迷宫
if(x==0 and y==0):
print("successful!")
return True
# 递归主体实现
if valid(maze,x,y):
# print(x,y)
maze[x][y]=2 # 做标记，防止折回
# 针对四个方向依次试探，如果失败，撤销一步
if not walk(maze,x-1,y):
maze[x][y]=1
elif not walk(maze,x,y-1):
maze[x][y]=1
elif not walk(maze,x+1,y):
maze[x][y]=1
elif not walk(maze,x,y+1):
maze[x][y]=1
else:
return False # 无路可走说明，没有解
return True
walk(maze,3,3)
递归是个好东西呀！
⑵ 求走迷宫的算法！（计算机的算法）（编程也可以
我的思路：
按照人类走迷宫的方法，贴着左边走，左边有路就向左走，左边没路向前走，左边前面都没路向右走
机器人的应该是：1.判断左边是否有墙，无墙：机器人左转，前进一步，继续判断左。。
2.左边有墙，则判断前方是否有墙，无则向前一步，跳回第一步
3.前方有墙（此时状态是左有墙，前有墙），则向机器人右转，跳回第一步
另外有个前提条件，机器人转弯需要原地转，有转弯半径的肯定不行。
还有个问题，就是机器人自己不知道自己已经从迷宫出来了，会一直走。。
⑶ 数据结构算法 用C++ 迷宫最短路径
一般迷宫寻路可以用递归的算法，或者用先进后出的栈数据结构实现
用的是深度优先的算法，可以寻找到走出迷宫的路径
但本题要求求出最短的路径，这就要使用广度优先的算法
一般在程序中需要用到先进先出的队列数据结构
下面是程序的代码，主要原理是用到
quei，quej和prep三个数组来构成队列
分别储存路径的行，列坐标和上一个节点在队列中的位置
大致算法如下，右三个嵌套的循环实现
首先是第一个节点进入队列
当队列不空（循环1）
｛
遍历队列中每节点(循环2）
｛
将八个方向能够走的节点加入队列（循环3）
｝
旧的节点出列
｝
#include<iostream>
#include<ctime>
usingnamespacestd;
#defineMAXNUM50
voidmain()
{
intm,n,i,j,x;
cout<<"请输入迷宫大小"<<endl;
cin>>m>>n;
intmaze[MAXNUM][MAXNUM];
srand((int)time(NULL));
for(i=0;i<=m+1;i++){
for(j=0;j<=n+1;j++){
if(i==0||j==0||i==m+1||j==n+1)
maze[i][j]=1;
else
{
x=rand()%1000;
if(x>700){maze[i][j]=1;}//控制矩阵中1的个数，太多1迷宫很容易走不通
else{maze[i][j]=0;}
}
cout<<maze[i][j]<<'';
}
cout<<endl;
}
//以上是输入和迷宫生成，一下是走迷宫
intmove[8][2]={0,1,1,0,0,-1,-1,0,1,1,-1,1,-1,-1,1,-1};
int*quei=newint[m*n];//储存行坐标队列
int*quej=newint[m*n];//储存列坐标队列
int*prep=newint[m*n];//储存之前一步在队列中的位置
inthead,rear,length;//队列头，队列尾，队列长度
head=0;rear=1;length=1;
quei[head]=1;quej[head]=1;prep[head]=-1;//入口位置进队列
intpos;//当前节点在队列中的位置，
intii,jj,ni,nj;//当前节点的坐标，新节点的坐标
intdir;//移动方向
if(maze[1][1]==1)length=0;//第一点就不能通过
elsemaze[1][1]=1;
while(length)//队列非空继续
{
for(pos=head;pos<head+length;pos++)//寻找这一层所有节点
{
ii=quei[pos];jj=quej[pos];//当前位置坐标
if(ii==m&&jj==n)break;
for(dir=0;dir<8;dir++)//寻找8个方向
{
ni=ii+move[dir][0];nj=jj+move[dir][1];//新坐标
if(maze[ni][nj]==0)//如果没有走过
{
quei[rear]=ni;quej[rear]=nj;prep[rear]=pos;//新节点入队
rear=rear+1;
maze[ni][nj]=1;//标记已经走过
}
}
}
if(ii==m&&jj==n)break;
head=head+length;
length=rear-head;//这一层节点出列
}
if(ii==m&&jj==n)
{
while(pos!=-1)
{
cout<<'('<<quei[pos]<<','<<quej[pos]<<')';
pos=prep[pos];
if(pos!=-1)cout<<',';
}
}
else
{
cout<<"THEREISNOPATH."<<endl;
}
delete[]quei;
delete[]quej;
delete[]prep;
}
⑷ A*path与Dijkstra寻路、迷宫生成
假设有人想从 A 点移动到一墙之隔的 B 点，如下图，绿色的是起点 A，红色是终点 B，蓝色方块是中间的墙。
在 A*寻路算法中，我们通过从绿色起点 A 开始，检查相邻方格的方式，向外扩展直到找到目标。
我们做如下操作开始搜索：
通常对于方格节点，我们认为水平/垂直移动一格耗费为 10，对角线移动耗费为 14。
G = 从 起点 沿着生成的路径，移动到当前节点的总移动耗费。
H = 从当前节点移动到 终点 的移动耗费估算。这经常被称为启发式的，因为它只是个猜测，我们没办法事先知道路径的实际长度。
对于方格节点通常使用 曼哈顿方法 ，它计算从当前格到 终点 之间水平和垂直的方格的数量总和，忽略对角线方向和障碍物。然后把结果乘以水平/垂直的移动耗费。
对于允许走对角线的节点使用 对角线方法 ，允许任意走的节点使用 欧几里得方法
当H值总为0时，退化为Dijkstra寻路算法
先构建一个如下的模型图,其中黑色为墙壁,红色为路径节点。墙可以为一个方形格子也可以仅仅是一条线(为方格时对角线上的墙壁始终无法被打通)。
先构建一个除了外圈为黑色墙壁,内部全是灰色通路的迷宫模型
⑸ 迷宫算法复杂度如何计算
迷宫生成可以O(n*m)完成。走迷宫的话可以O(n*m*2)左右。
只要记录走到每一格的最优解就可以了。
最好不要用深度优先搜索。用广度优先的实现方便。
⑹ 简单的迷宫算法
用python递归求解
dirs=[(0,1),(1,0),(0,-1),(-1,0)] #当前位置四个方向的偏移量
path=[] #存找到的路径
def mark(maze,pos): #给迷宫maze的位置pos标"2"表示“倒过了”
maze[pos[0]][pos[1]]=2
def passable(maze,pos): #检查迷宫maze的位置pos是否可通行
return maze[pos[0]][pos[1]]==0
def find_path(maze,pos,end):
mark(maze,pos)
if pos==end:
print(pos,end=" ") #已到达出口，输出这个位置。成功结束
path.append(pos)
return True
for i in range(4): #否则按四个方向顺序检查
nextp=pos[0]+dirs[i][0],pos[1]+dirs[i][1]
#考虑下一个可能方向
if passable(maze,nextp): #不可行的相邻位置不管
if find_path(maze,nextp,end):#如果从nextp可达出口，输出这个位置，成功结束
print(pos,end=" ")
path.append(pos)
return True
return False
def see_path(maze,path): #使寻找到的路径可视化
for i,p in enumerate(path):
if i==0:
maze[p[0]][p[1]] ="E"
elif i==len(path)-1:
maze[p[0]][p[1]]="S"
else:
maze[p[0]][p[1]] =3
print("\n")
for r in maze:
for c in r:
if c==3:
print('\033[0;31m'+"*"+" "+'\033[0m',end="")
elif c=="S" or c=="E":
print('\033[0;34m'+c+" " + '\033[0m', end="")
elif c==2:
print('\033[0;32m'+"#"+" "+'\033[0m',end="")
elif c==1:
print('\033[0;;40m'+" "*2+'\033[0m',end="")
else:
print(" "*2,end="")
print()
if __name__ == '__main__':
maze=[[1,1,1,1,1,1,1,1,1,1,1,1,1,1],\
[1,0,0,0,1,1,0,0,0,1,0,0,0,1],\
[1,0,1,0,0,0,0,1,0,1,0,1,0,1],\
[1,0,1,0,1,1,1,1,0,1,0,1,0,1],\
[1,0,1,0,0,0,0,0,0,1,1,1,0,1],\
[1,0,1,1,1,1,1,1,1,1,0,0,0,1],\
[1,0,1,0,0,0,0,0,0,0,0,1,0,1],\
[1,0,0,0,1,1,1,0,1,0,1,1,0,1],\
[1,0,1,0,1,0,1,0,1,0,1,0,0,1],\
[1,0,1,0,1,0,1,0,1,1,1,1,0,1],\
[1,0,1,0,0,0,1,0,0,1,0,0,0,1],\
[1,1,1,1,1,1,1,1,1,1,1,1,1,1]]
start=(1,1)
end=(10,12)
find_path(maze,start,end)
see_path(maze,path)
⑺ 试设计迷宫求解算法:迷宫是一个m行n列的0-1矩阵,其中0表示无障碍,1表示有障碍
假设8个方位被简单定义为 char a[8];
int path(point *location)
{
if(“location不为出口”&&“location.a[0]未涉足过”)
path(location->a[0]);
else if(“location不为出口”&&“location.a[1]未涉足过”)
path(location->a[0]);
else if(“location不为出口”&&“location.a[2]未涉足过”)
path(location->a[0]);
` ````````````````````
``````````
``````
``
else return 0;
}
这是一个迭代过程，需要对每一个方位的位置都遍历一遍，也是一个深度优先的遍历过程。
我在这只给lz一个示意，具体的算法在《数据结构》的书上基本都有，蛮经典的。希望能对lz有所帮组。
加油！
⑻ 李氏迷宫算法的发展
迷宫算法最初是由C．Y．Lee提出的,又称为李氏算法或波扩法，其优点是只要最短路径存在，就一定能找到，然而其缺点也是明显的，对于n×n的网格空间，它需要O（n2）的运行时间和存储空间并产生了较多的层间引线孔。
C.Y.LEE简介:
William C.Y.Lee(威廉．C．Y．李)博士，国际着名科学家，教育家，近代移动通信奠基人之一。
李博士于1963年获得美国Ohio State University电气工程博士学位；1964～1979年，开创了美国贝尔试验室下的移动无线电通信研究室；1979～1985年，任美国ITT公司国防通信部的尖端技术开发部主管；1985～2000年，任美国Vodafone AirTouch公司副总裁和首席科学家。2000～2005年，任美国LinkAir通信公司董事长，现任美国Treyspan公司董事长。
李博士因开发了商用的AMPS和CDMA技术而享誉全世界，在其几十年的科研生涯中，获得殊荣无数。1982年成为IEEE会员，1987年成为全美无线电俱乐部会员，1982～1998年应美国George Washington University邀请，主讲最早的面向产业的蜂窝和移动通信课程。还有ITTDCD的技术贡献奖(1984)，Ohio State University有突出贡献的校友(1990)，IEEE VTSAvant Garde奖(1990)，美国CTIA的奖励证书(1994)，IEEE车载技术协会技术服务奖(1996)，中美(SATEC)杰出贡献证书(1997)以及贝尔试验室致力服务奖(1998)，等等。李博士还是美国国家竞争委员会的会员，美国加利福尼亚州科学技术委员会成员，北京航空航天大学、西南交大的名誉教授。
李博士为蜂窝通信领域作出了巨大的贡献。他的重要专着和教科书《无线与蜂窝通信》(1989年第1版，1997年第2版，本书是2006年第3版的中文版)风靡全球，已被翻译成俄文版、汉语版、日语版、韩语版等多种文字。在该书第1版的序言里，李博士就明确阐述了他为蜂窝通信产业制定的目标：“让我们携起手来，使蜂窝产业发挥它最大的潜力，我们的目标是：在不远的将来，让便携式蜂窝电话把我们的通话遍及世界每一个角落。”
⑼ C语言迷宫问题，求该算法的时间和空间的复杂度。迷宫的路径已经定义好，求出路的算法。
该算法是不稳定的，其时空复杂度不仅和m,n有关，还和mg[][]的具体数值有关。
最坏情况下：每个点都试探过才走到终点。此时时间复杂度为：(m*n-1)*4，（其中4为4个方向），空间复杂度m*n*2，(其中m*n为存储迷宫图空间，m*n为栈空间);
再好情况下：一次试探过就走到终点。此时时间复杂度为：(min(m,n)-1)，空间复杂度m*n;
所以：
该算法时间复杂度为：[(m*n-1)*4+(min(m,n)-1)]/2，约为2×m×n
空间复杂度为3*m*n/2