• 基于Python的深度优先搜索----解决迷宫最短路径问题

    好习惯，讲问题先上图：

    第二个好习惯，先上完整的代码：

    1. import numpy as np
    2. import matplotlib.pyplot as plt
    3. import matplotlib
    4. import random
    5.  
    6. matplotlib.rcParams["font.sans-serif"] = ["SimHei"]
    7. matplotlib.rcParams["axes.unicode_minus"] = False
    8.  
    9. def init():
    10.     global map
    11.     global xmax
    12.     global ymax 
    13.     
    14.     map = np.zeros((xmax+2,ymax+2))
    15.     map[0][:] = -1
    16.     map[xmax+1][:] = -1
    17.     for i in range(xmax+2):
    18.         map[i][0] = -1
    19.         map[i][-1] = -1
    20.  
    21.     map[2][2:8] = -1
    22.     map[1][5:9] = -1
    23.     map[4][2:8] = -1
    24.     
    25.     for i in range(3,7):
    26.         map[i][6] = -1
    27.     for i in range(4,8):
    28.         map[i][8] = -1
    29.     for i in range(6,9):
    30.         map[i][3] = -1
    31.     for i in range(8,11):
    32.         map[i][5] = -1
    33.     print(map)
    34.  
    35. def deepFirstSearch(steps,x,y):
    36.     global map
    37.     current_step = steps + 1
    38.     map[x][y] = current_step
    39.     next_step = current_step + 1
    40.     #遍历周围4个点:
    41.     #节点不是-1表示非障碍：
    42.     #0表示没遍历过 步数加1
    43.     #里面比当前的next_step大 说明不是最优方案
    44.     if map[x-1][y] != -1 \
    45.        and (map[x-1][y]>next_step or map[x-1][y]==0) : 
    46.         deepFirstSearch(current_step,x-1,y)
    47.         
    48.     if map[x][y-1] != -1 \
    49.        and (map[x][y-1]>next_step or map[x][y-1]==0) : 
    50.         deepFirstSearch(current_step,x,y-1)   
    51.     if map[x][y+1] != -1 \
    52.        and (map[x][y+1]>next_step or map[x][y+1]==0) : 
    53.         deepFirstSearch(current_step,x,y+1)
    54.  
    55.     if map[x+1][y] != -1 \
    56.        and (map[x+1][y]>next_step or map[x+1][y]==0) : 
    57.         deepFirstSearch(current_step,x+1,y)
    58.         
    59. def find_way(end):
    60.     global map
    61.     dirs = [(0,-1),(-1,0),(0,1),(1,0)]
    62.     track = [[end]]
    63.     for k in range(1,int(map[end[0]][end[1]])):
    64.         track0 = []
    65.         for i in track[-1]:
    66.             for j in range(4):
    67.                 if (int(map[int(i[0]) + dirs[j][0]][int(i[1]) + dirs[j][1]]) == int(map[i[0]][i[1]]) - 1) &\
    68.                     ([i[0] + dirs[j][0],i[1] + dirs[j][1]] not in track0):
    69.                     track0.append([i[0] + dirs[j][0],i[1] + dirs[j][1]])
    70.         track.append(track0)
    71.     return track
    72.     
    73. if __name__ == "__main__":
    74.     xmax = 10
    75.     ymax = 10
    76.     start = [1,1]
    77.     end = [1,ymax]
    78.     map = []
    79.     init()
    80.     oldmap = map.copy()
    81.     pathmap = map.copy()
    82.     
    83.     deepFirstSearch(-1,start[0],start[1])
    84.     print(map[end[0]][end[1]])
    85.  
    86.     for i in range(xmax+2):
    87.         for j in range(ymax+2):
    88.             if map[i][j] == -1:
    89.                 plt.scatter(i,j,s=5,c="black")
    90.     track = find_way(end)
    91.     for i in track:
    92.         p = i[0]
    93.         plt.scatter(p[0],p[1],s=3,c="yellow")
    94.     plt.scatter(start[0],start[1],s=3,c="red")
    95.     plt.scatter(end[0],end[1],s=3,c="blue")
    96.     plt.title("深度优先搜索最短路径！")
    97.     plt.savefig("1.jpg")

     地图初始化部分：

    额，我觉得吧，地图嘛，美观就行，随便化，是吧。

    为了方便，不需要特别为边缘部分写一段代码，我给地图加了一个边框。地图不可通行部分是用-1表示的

    虽然numpy对这点数据来说跑起来没啥帮助，但是习惯了，对，楼主是计算物理本家的

    换一个大一点的数据跑一下呢？

    其实这是有   递归深度  的限制的，Python里面一般是1000次  大概在楼主的例子是32*32的地图模拟。针对递归栈溢出，可以调整默认深度，但是再大的深度还是有限的，而且会占用更多的内存。

    而且，事实上，压根没法搞那么多递推。。。

    这里小调整一下，还是可以到四五十*四五十的。

    这说明我们的思路是有很大的改进空间的，

                            不过，如果只是应对作业的话，应该够了。

                                                                            未来的物理学家留言

    1. import sys
    2. sys.setrecursionlimit(3000)

    那么怎么优化呢，我会给在最后的，当然，那得等我先想出来。

    1. import numpy as np
    2. import matplotlib.pyplot as plt
    3. import matplotlib
    4. import random
    5.  
    6. matplotlib.rcParams["font.sans-serif"] = ["SimHei"]
    7. matplotlib.rcParams["axes.unicode_minus"] = False
    8.  
    9. def init():
    10.     global map
    11.     global xmax
    12.     global ymax 
    13.     
    14.     map = np.zeros((xmax+2,ymax+2))
    15.     map[0][:] = -1
    16.     map[xmax+1][:] = -1
    17.     for i in range(xmax+2):
    18.         map[i][0] = -1
    19.         map[i][-1] = -1
    20.  
    21.     map[2][2:8] = -1
    22.     map[1][5:9] = -1
    23.     map[4][2:8] = -1
    24.     
    25.     for i in range(3,7):
    26.         map[i][6] = -1
    27.     for i in range(4,8):
    28.         map[i][8] = -1
    29.     for i in range(6,9):
    30.         map[i][3] = -1
    31.     for i in range(8,11):
    32.         map[i][5] = -1
    33.     print(map)

    然后是  deepFirstSearch部分了

    顺便一提，实际上，如果想模拟得更细致的话，可以用六角形地图，这里用的是四方形地图，显然和实际有些差别。。。

    1. def deepFirstSearch(steps,x,y):
    2.     global map
    3.     current_step = steps + 1
    4.     map[x][y] = current_step
    5.     next_step = current_step + 1
    6.     #遍历周围4个点:
    7.     #节点不是-1表示非障碍：
    8.     #0表示没遍历过 步数加1
    9.     #里面比当前的next_step大 说明不是最优方案
    10.     if map[x-1][y] != -1 \
    11.        and (map[x-1][y]>next_step or map[x-1][y]==0) : 
    12.         deepFirstSearch(current_step,x-1,y)
    13.         
    14.     if map[x][y-1] != -1 \
    15.        and (map[x][y-1]>next_step or map[x][y-1]==0) : 
    16.         deepFirstSearch(current_step,x,y-1)   
    17.     if map[x][y+1] != -1 \
    18.        and (map[x][y+1]>next_step or map[x][y+1]==0) :
    19.         deepFirstSearch(current_step,x,y+1)
    20.  
    21.     if map[x+1][y] != -1 \
    22.        and (map[x+1][y]>next_step or map[x+1][y]==0) : 
    23.         deepFirstSearch(current_step,x+1,y)

    在这个地方是可以加一些东西以限制深度的，这样就不用无脑增加递归深度了。

    比如：

    1.限制对偏远地区的搜索，

                    我们可以大胆推测：最短路线是不会经过  【30-40】 【30-40】的，对于这一部分不需要加以搜索

    2.在大片空白区域，

                    我们可以大胆推测：最短路线是沿着直线的，我们可以先搜索出一大块空白区域，然后直接一条直线连过去。

    3.本质上，还是深度的思路不合适，要更换思路。但做一些这些的考量是有益的，因为暴力不是永远管用的。在求解魔方上帝之数的时候，数学家好像就是这样的吗？

    4.有没有这样一种可能，正是因为我们的地图有大片的空白，所以无形中浪费了内存？我们在找地图的时候为什么不直接把有效地区给 剪切  出来呢？

    5.  ......  自己分析

    好了，在给所有的点标上数字后，你就能清楚得知道从任意一个点出发，到达这个点需要的最小步数了

    1. array([[-1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1.,
    2.         -1., -1., -1., -1.],
    3.        [-1.,  2.,  1.,  2.,  3., -1., -1., -1., -1., 22., 23., 24., 25.,
    4.         26., 27., 28., -1.],
    5.        [-1.,  1., -1., -1., -1., -1., -1., -1., 22., 21., 22., 23., 24.,
    6.         25., 26., 27., -1.],
    7.        [-1.,  2.,  3.,  4.,  5.,  6., -1., 22., 21., 20., 21., 22., 23.,
    8.         24., 25., 26., -1.],
    9.        [-1.,  3., -1., -1., -1., -1., -1., -1., -1., 19., 20., 21., 22.,
    10.         23., 24., 25., -1.],
    11.        [-1.,  4.,  5.,  6.,  7.,  8., -1., 14., -1., 18., 19., 20., 21.,
    12.         22., 23., 24., -1.],
    13.        [-1.,  5.,  6., -1.,  8.,  9., -1., 13., -1., 17., 18., 19., 20.,
    14.         21., 22., 23., -1.],
    15.        [-1.,  6.,  7., -1.,  9., 10., 11., 12., -1., 16., 17., 18., 19.,
    16.         20., 21., 22., -1.],
    17.        [-1.,  7.,  8., -1., 10., -1., 12., 13., 14., 15., 16., 17., 18.,
    18.         19., 20., 21., -1.],
    19.        [-1.,  8.,  9., 10., 11., -1., 13., 14., 15., 16., 17., 18., 19.,
    20.         20., 21., 22., -1.],
    21.        [-1.,  9., 10., 11., 12., -1., 14., 15., 16., 17., 18., 19., 20.,
    22.         21., 22., 23., -1.],
    23.        [-1., 10., 11., 12., 13., 14., 15., 16., 17., 18., 19., 20., 21.,
    24.         22., 23., 24., -1.],
    25.        [-1., 11., 12., 13., 14., 15., 16., 17., 18., 19., 20., 21., 22.,
    26.         23., 24., 25., -1.],
    27.        [-1., 12., 13., 14., 15., 16., 17., 18., 19., 20., 21., 22., 23.,
    28.         24., 25., 26., -1.],
    29.        [-1., 13., 14., 15., 16., 17., 18., 19., 20., 21., 22., 23., 24.,
    30.         25., 26., 27., -1.],
    31.        [-1., 14., 15., 16., 17., 18., 19., 20., 21., 22., 23., 24., 25.,
    32.         26., 27., 28., -1.],
    33.        [-1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1.,
    34.         -1., -1., -1., -1.]])

    或者改变 end 和 start

    当然，你可能已经发现了。最短路径往往不止一条。

    当然，你可能会嘲笑楼主，为什么不在深度搜索时就保存好整个路径呢？

            楼主觉得意义不大，这样只会增加内存。。。

            其实是楼主不会。。

    楼主的方法其实挺简单的，就是从头再搜索一遍，你说，那能不能给出所有的最短路线呢？嗯，问道楼主了，你可以自己推一推，写个码，分享在下面。。

    1. def find_way(end):
    2.     global map
    3.     dirs = [(0,-1),(-1,0),(0,1),(1,0)]
    4.     track = [[end]]
    5.     for k in range(1,int(map[end[0]][end[1]])):
    6.         track0 = []
    7.         for i in track[-1]:
    8.             for j in range(4):
    9.                 if (int(map[int(i[0]) + dirs[j][0]][int(i[1]) + dirs[j][1]]) == int(map[i[0]][i[1]]) - 1) &\
    10.                     ([i[0] + dirs[j][0],i[1] + dirs[j][1]] not in track0):
    11.                     track0.append([i[0] + dirs[j][0],i[1] + dirs[j][1]])
    12.         track.append(track0)
    13.     return track

     那么的话，在主函数部分的话，就只剩下地图可视化的部分了。回到开始去找吧。

    游戏结束。

    哦！

    你还记得怎么避免递归深度吗？嗯

    那当然是bfs广度搜索啦

    上图：

     上代码：

    1. import numpy as np
    2. import matplotlib.pyplot as plt
    3.  
    4. pre_route = []  
    5. q = []    
    6. dire = [(1,0),(-1,0),(0,1),(0,-1)]
    7.  
    8. visited = [] 
    9. route = []
    10. father = []
    11.  
    12. def bfs():
    13.     global xmax
    14.     global ymax
    15.     global start 
    16.     global map
    17.     global end
    18.  
    19.     global q
    20.     global dire
    21.     global father
    22.     global route
    23.     global pre_route
    24.     global visited
    25.     
    26.     visited = np.zeros((xmax+2,ymax+2))
    27.     visited[start[0]][start[1]]=1 
    28.     
    29.     q.append([start[0],start[1]])
    30.     while q:    
    31.         now = q[0]
    32.         q.pop(0)    
    33.         for i in range(4):
    34.             point=[now[0] + dire[i][0],now[1] + dire[i][1]]   
    35.             if map[point[0]][point[1]] == -1  or visited[point[0]][point[1]] == 1:
    36.                 continue
    37.             
    38.             father.append(now)
    39.             visited[point[0]][point[1]] = 1
    40.             q.append(point)
    41.             pre_route.append(point)
    42.  
    43.             if point[0] == end[0] and point[1] == end[1]:
    44.                 return True           
    45.     print("there is no way to exit")
    46.     return False
    47.  
    48. def get_route():    
    49.     global father
    50.     global route
    51.     global pre_route
    52.  
    53.     route = [pre_route[-1],father[-1]]
    54.     for i in range(len(pre_route)-1,-1,-1):
    55.         if pre_route[i]==route[-1]:
    56.             route.append(father[i])
    57.     route.reverse()
    58.     return route
    59.     
    60. def show_map():   
    61.     global map
    62.     global route
    63.     global end
    64.     global start
    65.  
    66.     plt.scatter(list(np.where(map==-1)[0]),list(np.where(map==-1)[1]),s=3,c="black")
    67.     plt.scatter([i[0] for i in route],[i[1] for i in route],s=3,c="yellow")
    68.     plt.scatter(start[0],start[1],s=3,c="red")
    69.     plt.scatter(end[0],end[1],s=3,c="blue")
    70.     plt.show()
    71.  
    72. def init():
    73.     global xmax
    74.     global ymax
    75.     global map
    76.     
    77.     map = np.zeros((xmax,ymax))
    78.     map[3][4:53] = -1
    79.     map[4][44:89] = -1
    80.     map[5][2:52] = -1
    81.     map[53][66:78] = -1
    82.     map[91][20:67] = -1
    83.  
    84.     map[0][:] = -1
    85.     map[-1][:] = -1
    86.     for i in range(ymax):
    87.         map[i][0] = -1
    88.         map[i][-1] = -1
    89.         
    90.  
    91. if __name__ =='__main__':
    92.     start = [1,1]
    93.     end = [25,40]
    94.     xmax = 100
    95.     ymax = 100
    96.     map = []
    97.     init()   
    98.  
    99.     if bfs():
    100.         route=get_route()
    101.         show_map()

    嗯，那什么是广度搜索呢：

    这玩意比深度搜索好一点的地方是，额，深度搜索需要把所有的地方都搜索一遍，这就很难应对大型地图。我们把广度搜索所搜索的地方表示出来：

    你看。很明显。少分析了很多数据。

    在解决  最短 最快 的问题时，应当有限使用广度搜索法。。。

    很好，很有精神！！

  • 相关阅读:
    Dockerd搭建redis三主三从&&扩容&&缩容
    华为云AOM 2.0版本发布
    【Java 进阶篇】JavaScript 正则表达式（RegExp）详解
    Java 基础 进程与线程
    [架构之路-15]：目标系统 - 硬件平台 - 什么是多核设计？多核面临的问题？什么是大小核设计？
    IP-adapter masking
    万字长文详解Webpack5高级优化
    Android Java JVM常见问答分析与总结
    Selenium获取百度百科旅游景点的InfoBox消息盒
    【学习】目标检测中的anchor
  • 原文地址：https://blog.csdn.net/Chandler_river/article/details/126610722