广度优先，走出迷宫的最短路线，Python模拟 |
您所在的位置：网站首页 › 迷宫问题最短路径python › 广度优先，走出迷宫的最短路线，Python模拟 |
广度优先，走出迷宫的最短路线，Python模拟
|
紧接前面深度优先，为了解决蛇形走位，即找到最近的路线，考虑了使用广度优先，下面先来看看使用深度优先找到的路线 蛇形走位之称乎可谓当之无愧，那么在同样的条件下，广度优先找到的路线是怎样的呢，见下图 路线找的智能了很多，不再绕来绕去了，还不错。 思想就是分层，第一层是开始的位置‘11’， 第二层可以到的位置有‘12’和‘21’，第三层可以到的位置有‘22’，‘31’，以此类推，可以将每一层可以到的位置都存储起来，直到某一层里面包含了出口‘28’，那么这时就不再往下走了，这样做唯一的缺点就是有点吃内存，运行时间可能会比较长。 即然每一层的信息都存储了起来，那么也就是说我们的最短路径也就包含在每一层里面了，下面的问题就是把这条路径选出来，怎么选呢，在前面的分层查找里面，其实是可以找到‘28’是从上一层的哪一步过来的，这是可以实现的，假如说是‘38’，那‘38’的上一层是哪个呢，同样用‘28’找‘38’的方法，可以实现用‘38’来往上找，这样一层一层的就实现了往回找，直到找出起始位置，那么此时，路线也就找到了， 代码如下 import numpy as np #迷宫中0的位置代表墙，不能走 #8代表入口，1代表可走位置 #888代表出口 migong = ''' 0 0 0 0 0 0 0 0 0 0 0 8 1 0 1 1 1 0 0 0 0 1 1 0 1 1 1 0 888 0 0 1 1 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0''' data = np.array(migong.split(), dtype = int).reshape((10,10)) def direction_set(data): """ 函数功能，找到data中未被走过的地方，并同时记录该地方能够走的地方 """ dir_set = {} v, h = np.where(data > 0) for i,j in zip(v, h): key = str(i) + str(j) if data[i, j+1] > 0: #该地方东邻块是否能走 dir_set[key] = [str(i)+str(j+1)] if data[i+1, j] > 0: #该地方南邻块是否能走 if key in dir_set: dir_set[key] += [str(i+1)+str(j)] else: dir_set[key] = [str(i+1)+str(j)] #data[i, j-1] if data[i, j-1] > 0: #该地方西邻块是否能走 if key in dir_set: dir_set[key] += [str(i)+ str(j-1)] else: dir_set[key] = [str(i)+ str(j-1)] #data[i-1, j] if data[i-1, j] > 0: #该地方北邻块是否能走 if key in dir_set: dir_set[key] += [str(i-1)+str(j)] else: dir_set[key] = [str(i-1) +str(j)] return dir_set def get_forward_step(exit_index): layer_ori = ['11'] #存放第一层信息 while True: layer_sec = [] #存放第二层信息 for key in layer_ori: #将layer_ori里面所能达到的位置，存放在layer_sec中 layer_sec += direction[key] if exit_index in direction[key]: forward_step = key if exit_index in layer_sec: break layer_ori = layer_sec return forward_step if __name__ == '__main__': direction = direction_set(data) huish = ['28'] #data[int(huish[0][0]), int(huish[0][1])] = 888 #将出口用888标记 while True: forward_step = get_forward_step(huish[-1]) huish += [forward_step] if forward_step == '11': break step = huish[::-1][:-1] for ind in step: data[int(ind[0]), int(ind[1])] = -8 print(data) print(step) |
【本文地址】
今日新闻 |
推荐新闻 |