走迷宫算法 用python实现
程序员文章站
2022-05-20 20:11:57
...
一个迷宫搜索的过程可以用python语言的算法来加以描述:
思路:穷举法。把所有的路都走了,总一条是对的。
首先老鼠不走回头路,它随便沿着一个方向一直走,遇到墙壁后换一个方向,直到没有路可以走,那么这条路就是死路。
然后,老鼠开始回退,一直回退到下一个路口,在沿着这条路一直走,以此类推,若存在到达出口的路,那么老鼠一定能走到出口。(因为最差的情况下,老鼠会把所有能走的路走一遍。)
用堆栈记录老鼠走过的路径,堆栈顶端为老鼠当前位置,若下一步有路可走,则压入堆栈,若下一步无路可走,则弹出顶端,一直弹出到有路可走为止。
if 上一格可走:
把方格编号加入到堆栈
往上走
判断是否为出口
elif 下一格可走:
把方格编号加入到堆栈
往上走
判断是否为出口
elif 左一格可走:
把方格编号加入到堆栈
往上走
判断是否为出口
elif 右一格可走:
把方格编号加入到堆栈
往上走
判断是否为出口
el色:
从堆栈删除一个方格编号
从堆栈中弹出一个方格编号
往回走
具体实现过程:(已知迷宫矩阵如下)
MAZE=[[1,1,1,1,1,1,1,1,1,1,1,1],\
[1,0,0,0,1,1,1,1,1,1,1,1],\
[1,1,1,0,1,1,0,0,0,0,1,1],\
[1,1,1,0,1,1,0,1,1,0,1,1],\
[1,1,1,0,0,0,0,1,1,0,1,1],\
[1,1,1,0,1,1,0,1,1,0,1,1],\
[1,1,1,0,1,1,0,1,1,0,1,1],\
[1,1,1,1,1,1,0,1,1,0,1,1],\
[1,1,0,0,0,0,0,0,1,0,0,1],\
[1,1,1,1,1,1,1,1,1,1,1,1]]
1表示墙体,无法通过,0表示道路,可以通过。
老鼠的初始位置为[1,1](第2行第2列)
出口位置为[8,10] (第9行第11列)
利用堆栈数据机构,寻找迷宫的出口
代码如下:
class Node:#用类来实现链表
def __init__(self):
self.x=0
self.y=0
self.next=None
#用全局变量top来记录堆栈顶端的数据。压入数据时,新数据的指针指向top(旧顶端),top指向新数据,从而新数据出现在堆栈的顶端(LIFPO)
def push(x,y):
global top
new_node=Node()
new_node.x=x
new_node.y=y
new_node.next=top
top=new_node
def pop():
global top
top=top.next #弹出数据时,top直接指向top.next
#检查节点
def check_point(x,y,ex,ey):
if x==ex and y==ey:
return 1
else:
return 0
#寻找下一节点
def next_step(MAZE,ex,ey):
a=top.x
b=top.y
ex=ex
ey=ey
if MAZE[a-1][b]==0:
push(a-1,b)
MAZE[a-1][b]=2
elif MAZE[a][b-1]==0:
push(a,b-1)
MAZE[a][b-1]=2
elif MAZE[a+1][b]==0:
push(a+1,b)
MAZE[a+1][b]=2
elif MAZE[a][b+1]==0:
push(a,b+1)
MAZE[a][b+1]=2
else:
pop()
#若老鼠走到了出口,那么停止算法,否则,老鼠会一直寻路。
def find_road(MAZE,x,y,ex,ey):
global top
a=ex
b=ey
head=Node()
head.x=x
head.y=y
head.next=None
top=head
while check_point(top.x,top.y,a,b)==0:
next_step(MAZE,a,b)
print('老鼠走过的路为:')
for i in range(10):
for j in range(12):
print(MAZE[i][j],end='')
print()
MAZE=[[1,1,1,1,1,1,1,1,1,1,1,1],\
[1,0,0,0,1,1,1,1,1,1,1,1],\
[1,1,1,0,1,1,0,0,0,0,1,1],\
[1,1,1,0,1,1,0,1,1,0,1,1],\
[1,1,1,0,0,0,0,1,1,0,1,1],\
[1,1,1,0,1,1,0,1,1,0,1,1],\
[1,1,1,0,1,1,0,1,1,0,1,1],\
[1,1,1,1,1,1,0,1,1,0,1,1],\
[1,1,0,0,0,0,0,0,1,0,0,1],\
[1,1,1,1,1,1,1,1,1,1,1,1]]
x=1
y=1
ex=8
ey=10
print('='*20)
print('迷宫为:')
for i in range(10):
for j in range(12):
print(MAZE[i][j],end='')
print()
print('='*20)
find_road(MAZE,x,y,ex,ey)
print('='*20)
while top!=None:
MAZE[top.x][top.y]=3
top=top.next
for i in range(10):
for j in range(12):
print(MAZE[i][j],end='')
print()
while top!=None:
MAZE[top.x][top.y]=3
top=top.next
for i in range(10):
for j in range(12):
print(MAZE[i][j],end='')
print()