事情的起源
昨天IG不是夺冠吗！心里真的很开心！恭喜IG夺冠！圆梦了，今天早上起床上课，无意在手机上看到一个迷宫的广告！然后室友也看到了，他是那种学习成绩比较优秀的，认为自己智商也非常高的，说这个太简单了！然后我就说你肯定过不了，就有了接下来的打赌，反正他玩了一上午都没有找到出口！我们的赌约是谁输了，谁就请对方一个月的烟钱！我平常的话丑的烟也不是很贵吗，就20来块一包左右的，然后我就欣然的接受了！然后我花了半个小时就写除了下面的这个算是个脚本吧！大家都知道什么是迷宫吧？给大家普及一下！
迷宫（Maze）指的是充满复杂通道，很难找到从其内部到达入口或从入口到达中心的道路，道路复杂难辨，人进去不容易出来的建筑物。
假设一个迷宫，它长这样（我自己画的，你也可以通过改变下面的矩阵从而改变迷宫的形状）。
起始点是红色小方块，终点是绿色的小方块，其中蓝色的■代表墙。
我们可以把迷宫抽象成一个矩阵，其中1代表墙，0代表有路，那么有
import numpy as np
maze=np.mat("""[
1 1 1 1 1 1 1 1 1 1 1;
1 0 1 0 0 0 0 1 0 0 1;
1 0 1 0 1 1 0 1 0 1 1;
1 0 0 0 0 0 1 0 0 0 1;
1 1 1 1 1 0 1 1 0 1 1;
1 0 0 0 0 0 1 1 1 0 1;
1 1 1 0 1 1 1 0 0 0 1;
1 0 0 0 1 0 0 0 0 1 1;
1 0 1 0 0 0 1 1 0 0 1;
1 1 1 1 1 1 1 1 1 11]""",dtype=np.int8)
使用numpy模块的矩阵，不仅仅是它比双重list代表的矩阵好，还有的是把元素设置为int8，每个元素在-127到128变化即可（实际上根本用不到那么多），况且int8只占一个字节。
定义四个方向
dire=[(0,1),(1,0),(0,-1),(-1,0)]
进群：548377875 即可获取大量的学习资料以及大量的PDF哦！Python是一个非常神奇的东西！
我们理一下思路，走迷宫的决策是：
标记当前位置
从栈中弹出一个位置和要走的方向，也就是当前位置和未知方向
看看未知方向，是否可以走。
如果有可以走，把当前位置和下一个未知方向压入栈。把新位置和一个未知方向压入栈，返回1步骤，如果未知方向不可以走，再探查下一个未知方向。如果发现是死路，退到之前的位置再看看。
下一个未知点是终点，搜索结束。返回路径
一直退到出发点直到栈长度为0，说明没有路径可以走到终点。
为什么要标记当前位置，我用一个小漫画说明
def mark(maze,pos):
maze[pos[0],pos[1]]=2
def passable(maze,pos):
return maze[pos[0],pos[1]]==0
mark标记函数很简单，把pos在地图maze上标记为2，表示走过了。
passable函数表示是否可以走，如果位置pos值为0就可以走。
def st_find(maze,start,end):
"""maze为迷宫矩阵，start和end是开始点和结束点
返回一个list"""
if start==end:
#特殊情况，起点就是终点
return [(start,0)]
st=[] #stack的缩写，表示栈
mark(maze,start)
st.append((start,0))
#将开始位置和要探索的未知未知压入栈
while len(st)!=0:
#只要还有没有探索完的地方就不会结束
pos,nxt=st.pop()
for i in range(nxt,4):
nextp=(pos[0]+dire[i][0],pos[1]+dire[i][1])
#下一个探查点
if passable(maze,nextp):
st.append((pos,i+1))
# 如果可行，把下一个没探测的点压入栈
mark(maze,nextp)
st.append((nextp,0))
#把新的位置等压入栈
if nextp == end:
#发现新位置是终点，结束
return st
break
print("没有发现路径")
return []
就这样，一个基于栈做为搜索的函数就写成了，更重要的是，它是非递归的，如果用递归写虽然简洁可是不容易理解。
其中，基于栈为搜索方式的搜索方法叫深度优先搜索(Depth First Search)，基于队列的叫宽度优先搜索 (Breadth First Search)。
运行函数，返回[((1, 1), 2), ((2, 1), 2), ((3, 1), 1), ((3, 2), 1), ((3, 3), 1), ((3, 4), 1), ((3, 5), 2), ((4, 5), 2), ((5, 5), 3), ((5, 4), 3), ((5, 3), 2), ((6, 3), 2), ((7, 3), 2), ((8, 3), 1), ((8, 4), 1), ((8, 5), 4), ((7, 5), 1), ((7, 6), 1), ((7, 7), 1), ((7, 8), 2), ((8, 8), 1), ((8, 9), 0)]
其中list的每一个元素的第一个代表坐标，将每一个元素链接起来就是路径。我们可以使用matplotlib画出迷宫和路线
import matplotlib.pyplot as plt
import matplotlib
# 设置matplotlib正常显示中文和负号
matplotlib.rcParams['font.sans-serif']=['SimHei'] # 用黑体显示中文
matplotlib.rcParams['axes.unicode_minus']=False # 正常显示负号
st=st_find(maze,(1,1),(8,9))
x=[]
y=[]
for i in st:
x.append(i[0][0])
y.append(i[0][1])
plt.plot(x,y,'r')
xq=[]
yq=[]
for i in range(10):
for j in range(11):
if maze[i,j]==1:
xq.append(i)
yq.append(j)
plt.plot(xq,yq,'*')
plt.title('深度优先搜索找到迷宫的路径')
plt.show()
有趣的是，走迷宫问题也可以使用递归来实现，具体操作如下，代码很简洁，栈（运行栈）在运行的时候，在程序内部出现的，用于保存每层函数递归的信息。
def find_path(maze,pos,end):
mark(maze,pos) #标记
if pos==end:
#走到终点或者开始点就是终点
print(pos,end=' ')
return True
for i in range(4):
nextp=(pos[0]+dire[i][0],pos[1]+dire[i][1])
#探索每一个可能性
if passable(maze,nextp):
if find_path(maze,nextp,end):
#递归开始，如果这样一直递归下去递归到终点
print(pos,end=' ')
#输出结果
return True
return False
到此结束咯！嘿嘿，烟钱到手，开心啊！反正我一天也抽不了多少！大概一天就是一包左右，一个月也就三条左右就快了！我可不是刻意坑我室友的，你知道的大学当班长，一些外快还是随便就能混到的，比如帮忙申请一个助学金的名额，或者奖学金的名额，他就能得到一笔不菲的钱，所以反正也是他请我们吃饭抽烟啥的，我就收了也没关系啦，反正也是两个人一起抽的！并没有大家想的那样哦！
网友评论