当前位置： 首页 > news >正文

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

news 来源：原创 2024/5/8 8:06:59

好习惯，讲问题先上图：

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

import numpy as np
import matplotlib.pyplot as plt
import matplotlib
import random

matplotlib.rcParams["font.sans-serif"] = ["SimHei"]
matplotlib.rcParams["axes.unicode_minus"] = False

def init():
    global map
    global xmax
    global ymax 
    
    map = np.zeros((xmax+2,ymax+2))
    map[0][:] = -1
    map[xmax+1][:] = -1
    for i in range(xmax+2):
        map[i][0] = -1
        map[i][-1] = -1

    map[2][2:8] = -1
    map[1][5:9] = -1
    map[4][2:8] = -1
    
    for i in range(3,7):
        map[i][6] = -1
    for i in range(4,8):
        map[i][8] = -1
    for i in range(6,9):
        map[i][3] = -1
    for i in range(8,11):
        map[i][5] = -1
    print(map)

def deepFirstSearch(steps,x,y):
    global map
    current_step = steps + 1
    map[x][y] = current_step
    next_step = current_step + 1
    #遍历周围4个点:
    #节点不是-1表示非障碍：
    #0表示没遍历过 步数加1
    #里面比当前的next_step大 说明不是最优方案
    if map[x-1][y] != -1 \
       and (map[x-1][y]>next_step or map[x-1][y]==0) : 
        deepFirstSearch(current_step,x-1,y)
        
    if map[x][y-1] != -1 \
       and (map[x][y-1]>next_step or map[x][y-1]==0) : 
        deepFirstSearch(current_step,x,y-1)   
    if map[x][y+1] != -1 \
       and (map[x][y+1]>next_step or map[x][y+1]==0) : 
        deepFirstSearch(current_step,x,y+1)

    if map[x+1][y] != -1 \
       and (map[x+1][y]>next_step or map[x+1][y]==0) : 
        deepFirstSearch(current_step,x+1,y)
        
def find_way(end):
    global map
    dirs = [(0,-1),(-1,0),(0,1),(1,0)]
    track = [[end]]
    for k in range(1,int(map[end[0]][end[1]])):
        track0 = []
        for i in track[-1]:
            for j in range(4):
                if (int(map[int(i[0]) + dirs[j][0]][int(i[1]) + dirs[j][1]]) == int(map[i[0]][i[1]]) - 1) &\
                    ([i[0] + dirs[j][0],i[1] + dirs[j][1]] not in track0):
                    track0.append([i[0] + dirs[j][0],i[1] + dirs[j][1]])
        track.append(track0)
    return track
    
if __name__ == "__main__":
    xmax = 10
    ymax = 10
    start = [1,1]
    end = [1,ymax]
    map = []
    init()
    oldmap = map.copy()
    pathmap = map.copy()
    
    deepFirstSearch(-1,start[0],start[1])
    print(map[end[0]][end[1]])

    for i in range(xmax+2):
        for j in range(ymax+2):
            if map[i][j] == -1:
                plt.scatter(i,j,s=5,c="black")
    track = find_way(end)
    for i in track:
        p = i[0]
        plt.scatter(p[0],p[1],s=3,c="yellow")
    plt.scatter(start[0],start[1],s=3,c="red")
    plt.scatter(end[0],end[1],s=3,c="blue")
    plt.title("深度优先搜索最短路径！")
    plt.savefig("1.jpg")

 地图初始化部分：

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

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

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

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

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

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

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

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

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

                                                                        未来的物理学家留言

import sys
sys.setrecursionlimit(3000)

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

import numpy as np
import matplotlib.pyplot as plt
import matplotlib
import random

matplotlib.rcParams["font.sans-serif"] = ["SimHei"]
matplotlib.rcParams["axes.unicode_minus"] = False

def init():
    global map
    global xmax
    global ymax 
    
    map = np.zeros((xmax+2,ymax+2))
    map[0][:] = -1
    map[xmax+1][:] = -1
    for i in range(xmax+2):
        map[i][0] = -1
        map[i][-1] = -1

    map[2][2:8] = -1
    map[1][5:9] = -1
    map[4][2:8] = -1
    
    for i in range(3,7):
        map[i][6] = -1
    for i in range(4,8):
        map[i][8] = -1
    for i in range(6,9):
        map[i][3] = -1
    for i in range(8,11):
        map[i][5] = -1
    print(map)

然后是  deepFirstSearch部分了

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

def deepFirstSearch(steps,x,y):
    global map
    current_step = steps + 1
    map[x][y] = current_step
    next_step = current_step + 1
    #遍历周围4个点:
    #节点不是-1表示非障碍：
    #0表示没遍历过 步数加1
    #里面比当前的next_step大 说明不是最优方案
    if map[x-1][y] != -1 \
       and (map[x-1][y]>next_step or map[x-1][y]==0) : 
        deepFirstSearch(current_step,x-1,y)
        
    if map[x][y-1] != -1 \
       and (map[x][y-1]>next_step or map[x][y-1]==0) : 
        deepFirstSearch(current_step,x,y-1)   
    if map[x][y+1] != -1 \
       and (map[x][y+1]>next_step or map[x][y+1]==0) :
        deepFirstSearch(current_step,x,y+1)

    if map[x+1][y] != -1 \
       and (map[x+1][y]>next_step or map[x+1][y]==0) : 
        deepFirstSearch(current_step,x+1,y)

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

比如：

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

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

2.在大片空白区域，

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

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

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

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

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

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

或者改变 end 和 start

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

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

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

        其实是楼主不会。。

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

def find_way(end):
    global map
    dirs = [(0,-1),(-1,0),(0,1),(1,0)]
    track = [[end]]
    for k in range(1,int(map[end[0]][end[1]])):
        track0 = []
        for i in track[-1]:
            for j in range(4):
                if (int(map[int(i[0]) + dirs[j][0]][int(i[1]) + dirs[j][1]]) == int(map[i[0]][i[1]]) - 1) &\
                    ([i[0] + dirs[j][0],i[1] + dirs[j][1]] not in track0):
                    track0.append([i[0] + dirs[j][0],i[1] + dirs[j][1]])
        track.append(track0)
    return track

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

游戏结束。

哦！

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

那当然是bfs广度搜索啦

上图：

 上代码：

import numpy as np
import matplotlib.pyplot as plt

pre_route = []  
q = []    
dire = [(1,0),(-1,0),(0,1),(0,-1)]

visited = [] 
route = []
father = []

def bfs():
    global xmax
    global ymax
    global start 
    global map
    global end

    global q
    global dire
    global father
    global route
    global pre_route
    global visited
    
    visited = np.zeros((xmax+2,ymax+2))
    visited[start[0]][start[1]]=1 
    
    q.append([start[0],start[1]])
    while q:    
        now = q[0]
        q.pop(0)    
        for i in range(4):
            point=[now[0] + dire[i][0],now[1] + dire[i][1]]   
            if map[point[0]][point[1]] == -1  or visited[point[0]][point[1]] == 1:
                continue
            
            father.append(now)
            visited[point[0]][point[1]] = 1
            q.append(point)
            pre_route.append(point)

            if point[0] == end[0] and point[1] == end[1]:
                return True           
    print("there is no way to exit")
    return False

def get_route():    
    global father
    global route
    global pre_route

    route = [pre_route[-1],father[-1]]
    for i in range(len(pre_route)-1,-1,-1):
        if pre_route[i]==route[-1]:
            route.append(father[i])
    route.reverse()
    return route
    
def show_map():   
    global map
    global route
    global end
    global start

    plt.scatter(list(np.where(map==-1)[0]),list(np.where(map==-1)[1]),s=3,c="black")
    plt.scatter([i[0] for i in route],[i[1] for i in route],s=3,c="yellow")
    plt.scatter(start[0],start[1],s=3,c="red")
    plt.scatter(end[0],end[1],s=3,c="blue")
    plt.show()

def init():
    global xmax
    global ymax
    global map
    
    map = np.zeros((xmax,ymax))
    map[3][4:53] = -1
    map[4][44:89] = -1
    map[5][2:52] = -1
    map[53][66:78] = -1
    map[91][20:67] = -1

    map[0][:] = -1
    map[-1][:] = -1
    for i in range(ymax):
        map[i][0] = -1
        map[i][-1] = -1
        

if __name__ =='__main__':
    start = [1,1]
    end = [25,40]
    xmax = 100
    ymax = 100
    map = []
    init()   

    if bfs():
        route=get_route()
        show_map()

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

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

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

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

很好，很有精神！！

相关文章：

  • 微服务-SpringCloud学习(一)
  • 八股文之设计模式
  • 第6章 初识Spring框架
  • 【明年找到好工作】：面试题打卡第二天
  • 企业Java实战面试题
  • 多次握手登录
  • gdb调试 常用命令
  • 华为云上安装mysql-5.7.38-极其详细的安装教程
  • vue父子组件传值：父传子、子传父
  • 使用花生壳做内网穿透
  • 基于SSM的学生宿舍管理系统
  • 第二章第六节 ST图与迭代优化
  • Kotlin（九）类、属性、构造函数
  • Java 八股文能不背吗？Java 面试都只是背答案吗？
  • [CC2642R1][VSCODE+Embedded IDE+IAR Build+Cortex-Debug] TI CC2642R1基于VsCode的开发环境
  • [微信小程序] 使用ES6特性Class后出现编译异常
  • angular学习第一篇-----环境搭建
  • emacs初体验
  • fetch 从初识到应用
  • IP路由与转发
  • Java教程_软件开发基础
  • js写一个简单的选项卡
  • leetcode-27. Remove Element
  • php面试题 汇集2
  • Python_OOP
  • Swift 中的尾递归和蹦床
  • 不用申请服务号就可以开发微信支付/支付宝/QQ钱包支付！附：直接可用的代码+demo...
  • 翻译 | 老司机带你秒懂内存管理 - 第一部（共三部）
  • 基于Android乐音识别(2)
  • 近期前端发展计划
  • 如何用Ubuntu和Xen来设置Kubernetes？
  • 视频flv转mp4最快的几种方法（就是不用格式工厂）
  • 正则表达式小结
  • # Python csv、xlsx、json、二进制(MP3) 文件读写基本使用
  • #if #elif #endif
  • #快捷键# 大学四年我常用的软件快捷键大全，教你成为电脑高手！！
  • #我与Java虚拟机的故事#连载05：Java虚拟机的修炼之道
  • $.ajax()方法详解
  • （六）什么是Vite——热更新时vite、webpack做了什么
  • （篇九）MySQL常用内置函数
  • （三）Honghu Cloud云架构一定时调度平台
  • (一)基于IDEA的JAVA基础1
  • (原)记一次CentOS7 磁盘空间大小异常的解决过程
  • (原創) 物件導向與老子思想 (OO)
  • （转）Unity3DUnity3D在android下调试
  • .bat批处理（九）：替换带有等号=的字符串的子串
  • .describe() python_Python-Win32com-Excel
  • .NET业务框架的构建
  • @AutoConfigurationPackage的使用
  • @SuppressWarnings(unchecked)代码的作用
  • @WebService和@WebMethod注解的用法
  • [2009][note]构成理想导体超材料的有源THz欺骗表面等离子激元开关——
  • [20170705]lsnrctl status LISTENER_SCAN1
  • [202209]mysql8.0 双主集群搭建 亲测可用
  • [Angular 基础] - 数据绑定(databinding)