图搜索基础-深度优先搜索

图搜索基础-深度优先搜索

  • 参考
  • 原理
      • 引入
      • 流程解析
      • 手推例子
  • 代码实现
    • 运行结果
    • 结果分析

参考

理论参考:深蓝学院
实现参考:github项目

原理

引入

对于这样一个图,我们试图找到S到G的通路:
在这里插入图片描述
计算机程序不会像人眼一样,一下子连出一条从S到G的通路,需要一个一个节点的访问。每个节点,在建模和编程的时候都设计为一个数据结构,可以知道跟他直接连通的有哪些节点,以及这些边的代价。
我们假想自己就是程序,在访问一个节点,比如S时,看到S和p,d,e三个节点都有边。那我就可以先看看p是否和G有边,或者先看看d是否和G有边,也可以先看看e是否和G有边,这个暂时不重要。假设我们先看p是否和G有边,我们发现p和q有边,和G无边。这时候我们面临了关键选择:我是沿这条线继续深入,看看q是否和G有边哪?还是回过头开另一条线,看看d是否和G有边?这里的选择就是深度优先和广度优先的全部区别所在。

因为可以认为q是p的下一级节点,继续查看p,就是往深处探寻。就像是面对岔路口一样,我是继续选一个岔路往前走还是回到上一个岔路口,深度优先选择选一个岔路口继续深入,而且每次面对这样的选择都这么做。如果一直走到了死胡同也没到终点,再回到上一个岔路口,换一条路继续深入。

根据这个树形结构,可以更好理解,深度:
在这里插入图片描述
你要说,明明是图结构,为什么又变成树结构?回答是,程序面对岔路口时,并不知道地图全貌(他知道,但他不理解)。

主要的找通路问题解决了,还有两个次要问题:

  1. 我们找通路是为了下次走方便的,所以要记录下来这条通路经过了哪些节点。其实我们只需要记录每一个节点的父节点,只要每个节点只有一个父节点,最后一定能回溯出唯一的一条通路
  2. 我们通常不仅是要找通路,更是要找最短路径。在面临一个节点有多个父节点时,需要比较不同父节点时从起点到这个节点的累计代价和,取代价和最小的父节点为父节点。

流程解析

我们根据图搜索的一个通用模板进行流程解析:

  1. 初始化节点数据结构(节点,父节点,累计代价和)。

  2. 初始化开放列表openlist,把初始节点s包含其中,无父节点,累计代价和为0。

  3. 初始化封闭列表closelist,没有任何东西。

  4. 执行以下循环,直到所有节点被访问或通路被找到,或其他结束标准:
    3.1. 根据算法规则,从openlist中取出一个节点。
    3.2. 根据图结构,获得该节点的相邻节点(和该节点有边的节点),并排除掉在closelist中的节点
    3.3 领域查询:

    • 如果相邻节点不在openlist中,以该节点为父节点,计算累计代价值,将此相邻节点直接加入openlist。
    • 如果相邻节点在openlist中,则假设以该节点为父节点,计算此时累计代价值,并与openlist中的历史累计代价值比较:
      • 如果此时累计代价值大,则不加入openlist。
      • 反之将之前的剔除openlist,把此时的加入openlist。

    3.4. 把该节点放入closelist。
    3.5. 判断该节点是否为终止节点。

  5. 终止节点的累计代价就是整条通路的累计代价;从终止节点开始查询父节点就找到了从初始节点到终止节点的整条通路。

图搜索的核心在于3.1的算法规则。对于深度优先算法,我们应该提取最近加入的节点。
举个例子就是:当我们面对岔路时,我们应该走刚看到的岔路中的一条,而不是之前看到的岔路中的一条。
这个思想直接对应于一种数据结构:堆栈。所以用堆栈管理openlist就可以实现深度优先搜索。

当然,此时还有一个小小的问题:

  • 当前节点的相邻节点有好几个,他们应该以什么样的顺序压入堆栈哪?毕竟越晚被压入,越早被取出嘛,压入先后是有不同的。这点随意。比如面对一个岔路,可以顺时针编号,可以逆时针编号,这部分的优化不是深度优先算法的工作。

手推例子

道理明白了,我们结合流程,手推一遍算法的实现:
参照这个图,假设起点为S,重点为r(不用G是因为搜索过程太长了):
在这里插入图片描述

  1. 初始化节点数据结构(节点,父节点,累计代价和)。
  2. 初始化开放列表openlist,把初始节点s包含其中,无父节点,累计代价和为0。
  3. 初始化封闭列表closelist,没有任何东西。
  4. 开始循环:
    a. 弹出openlist最上层节点S;查找到邻居节点d,e,p,都不在openlist和closelist中,因此依次放进openlist,此时openlist为p,e,d;将节点S放入closelist;S没有终止节点r,继续;
    b. 弹出openlist最上层节点d,查找到邻居节点e,c,b,openlist中已经有e,但这个例子中没有定义代价,所以无法判断是否替换掉原有的e,暂时不管,依次放进openlist,此时openlist为p,e(s),e(d),c,b;将节点d放入closelist;d没有终止节点r,继续;
    c. 弹出openlist最上层节点b,查找到邻居节点a,放进openlist,此时openlist为p,e(s),e(d),c,a;将节点b放入closelist;b没有终止节点r,继续;
    d. 弹出openlist最上层节点a,查找到没有邻居节点,什么都不放入openlist,此时openlist为p,e(s),e(d),c;将节点a放入closelist;a没有终止节点r,继续;
    e. 弹出openlist最上层节点c,查找到邻居节点a,放进openlist,此时openlist为p,e(s),e(d),a;将节点c放入closelist;c没有终止节点r,继续;
    f. 弹出openlist最上层节点a,查找到没有邻居节点,此时openlist为p,e(s),e(d);将节点a放入closelist;发现a没有终止节点r,继续;
    g. 弹出openlist最上层节点e(d),查找到邻居节点h,r,放进openlist,此时openlist为p,e(s),h,r;将节点e(d)放入closelist;发现e(d)没有终止节点r,继续;
    h. 弹出openlist最上层节点r,查找到邻居节点f,放进openlist,此时openlist为p,e(s),h,f;把r放进closelist,r就是终止节点,循环结束
  5. r父节点是e(d),e(d)父节点是d,d父节点是s,因此通路为s-d-e-r。因为没有定义代价,所以通路累计代价值不知道。

代码实现

核心代码:

class DFS(AStar):
    """DFS add the new visited node in the front of the openset
    """
    def searching(self):
        """
        Depth-first Searching.
        :return: path, visited order
        """
        # 初始化节点数据结构(在其他文件中定义过了)
            # 因为是栅格地图,节点标识就用坐标标识了
            # 节点的父节点,由self.PARENT列表维护
            # 到达此节点的累计代价值,由self.g列表维护

        # 初始化Openlist
        self.PARENT[self.s_start] = self.s_start    # 维护节点的父节点;起始点父节点是自己
        self.g[self.s_start] = 0                    # 到达此节点的累计代价值;起始点累计代价值为0
        self.g[self.s_goal] = math.inf
        heapq.heappush(self.OPEN, (0, self.s_start))# 把起始点压入openlist

        # 初始化Closelist(在基类中定义过了)
            # 和初始的Openlist一样,是个空列表

        # 循环直到所有节点被遍历完(Openlist空掉)
        while self.OPEN:
            # 弹出最近压入Openlist堆栈的节点
            _, s = heapq.heappop(self.OPEN)
            # 将弹出节点加入Closelist,不再访问
            self.CLOSED.append(s)

            # 如果当前节点就是终点,跳出循环
            if s == self.s_goal:
                break
            
            # 如果当前节点不是终点,进行邻域查询
            for s_n in self.get_neighbor(s):
                # 检查该邻域点是否在closelist中(他给漏掉了,我加上去:)
                if s_n in self.CLOSED:
                    continue

                # 以当前节点为父节点的邻域节点的累计代价值 = 当前节点的累计代价值 + 从当前节点到该邻域节点代价值之和
                    # 当前节点的累计代价值在上一次循环中被计算过,所以已知
                    # 从当前节点到该邻域节点代价值之和,在基类中被实现,基于栅格地图哈慢炖距离,如果是障碍物则无穷
                new_cost = self.g[s] + self.cost(s, s_n)

                if s_n not in self.g:
                    self.g[s_n] = math.inf

                # 如果以当前节点为父节点,此邻域节点的累计代价值更小,就把原来的剔除Openlist,把现在的加进去,并更新父节点,和累计代价值
                if new_cost < self.g[s_n]:  # conditions for updating Cost
                    self.g[s_n] = new_cost  # 更新累计代价值
                    self.PARENT[s_n] = s    # 更新父节点
                    # 检查剔除原来在openlist中的记录(他给漏掉了,我加上去:)
                    if s_n in self.OPEN:
                        self.OPEN.remove(s_n)

                    # 把邻域节点压入Openlist
                    # dfs, add new node to the front of the openset
                    prior = self.OPEN[0][0]-1 if len(self.OPEN)>0 else 0    # 计算新元素在列表中位置(自动的堆栈结构更好,他这个要自己维护)
                    heapq.heappush(self.OPEN, (prior, s_n)) 

        return self.extract_path(self.PARENT), self.CLOSED

以上代码是我在源代码,根据前一节得到的流程伪代码添加了注释和缺失步骤的版本。
可以看到,和之前说的伪代码流程除了循环中几个顺序不一样(无所谓)外,其他完全一致。

运行结果

在这里插入图片描述

结果分析

可以看到,深度优先在面临选择时,会一条路走到黑:在有多个选择时,先一直往左下方向走;当没有选择时,溜着墙边这一条路走。

他这次表现的不好,主要是默认面临多个选择时,先探索左下角。当然你可以改成默认右上角,但这是由于我们知道了全局地图,但算法不知道,如果写死了,下次出发点在右上角,终点在左下角,还是会出现类似情况。最好的办法是让算法知道目标大概在哪个方向,这就是启发式算法做的工作了。如前所述:

当前节点的相邻节点有好几个,他们应该以什么样的顺序压入堆栈哪?毕竟越晚被压入,越早被取出嘛,压入先后是有不同的。这点随意。比如面对一个岔路,可以顺时针编号,可以逆时针编号,这部分的优化不是深度优先算法的工作。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/415111.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

鸿蒙应用程序包安装和卸载流程

开发者 开发者可以通过调试命令进行应用的安装和卸载&#xff0c;可参考多HAP的调试流程。 图1 应用程序包安装和卸载流程&#xff08;开发者&#xff09; 多HAP的开发调试与发布部署流程 多HAP的开发调试与发布部署流程如下图所示。 图1 多HAP的开发调试与发布部署流程 …

线性DP-前缀和

哪种连续子字符串更长 思路 我们遍历输入字符串s中的每个字符。对于每个字符&#xff0c;我们检查它是1还是0&#xff0c;并相应地更新currentLength1和currentLength0。当我们遇到一个1时&#xff0c;我们增加currentLength1的值&#xff0c;并将currentLength0重置为0&#…

2023秋季飞书未来无限大会--随笔

这个时代的飞书 数字时代 工作协同平台 AI时代 帮助企业和个人用好AI 企业如何引用大模型能力&#xff1f; 智慧体— 接近人&#xff0c;有进步空间智能伙伴 用时代的科技打造爱不释手的好产品 移动互联网 – 改变信息分发方式 大模型 –自然的人机交互方式 业务协同 …

Swagger接口文档管理工具

Swagger 1、Swagger1.1 swagger介绍1.2 项目集成swagger流程1.3 项目集成swagger 2、knife4j2.1 knife4j介绍2.2 项目集成knife4j 1、Swagger 1.1 swagger介绍 官网&#xff1a;https://swagger.io/ Swagger 是一个规范和完整的Web API框架&#xff0c;用于生成、描述、调用和…

kali linux通过aircrack-ng命令破解wifi密码

相关阅读&#xff1a;如何破解攻击WiFi 百度安全验证https://baijiahao.baidu.com/s?id1764248756021219497&wfrspider&forpc上面2篇文章写得都很不错 一、前期准备工作 1、将无线网卡挂载到Kali上 ​ 将无线网卡插到电脑上&#xff0c;如果弹出检测到新的USB设备&…

break,continue

break&#xff1a;跳出并结束循环 continue:跳过本次循环&#xff0c;执行下一次循环 代码演示&#xff1a; package com.zhang.loop;public class BreakAndContinueDemo8 {public static void main(String[] args) {//掌握break和continue的作用//1. break&#xff1a;跳出循…

​LeetCode解法汇总2673. 使二叉树所有路径值相等的最小代价

目录链接&#xff1a; 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目&#xff1a; https://github.com/September26/java-algorithms 原题链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个整数 n 表示一棵 满二叉树 里面节…

Java设计模式 | 七大原则之迪米特法则

基本介绍 一个对象应该对其他对象保持最少的了解类与类关系越密切&#xff0c;耦合度越大迪米特法则&#xff08;Demeter Principle&#xff09;又叫最少知道法则&#xff0c;即一个类对自己依赖的类知道的越少越好。也就是说&#xff0c;对于被依赖的类不管多么复杂&#xff…

虚拟机 VMware 安装 Windows2000 (iso 光盘镜像)

上篇博客关于 kali 的安装&#xff0c;我们下载的直接是 vmx 文件 这次我们以 iso 文件为例&#xff0c;因此配置过程会有些许不同 先在本地新建一个文件夹用于存放我们一会儿下载的 iso 镜像文件 下载好后是一个后缀为 .iso 的文件 同样我们先打开 VMware 依次点击文件 -&g…

亚信安慧AntDB开启超融合数据库新纪元

&#xff08;一&#xff09; 前言 据统计&#xff0c;在信息化时代的今天&#xff0c;人们一天所接触到的信息量&#xff0c;是古人一辈子所能接收到的信息量的总和。当今社会中除了信息量“多”以外&#xff0c;人们对信息处理的“效率”和“速度”的要求也越来越高。譬如&…

lv21 QT对话框3

1 内置对话框 标准对话框样式 内置对话框基类 QColorDialog, QErrorMessage QFileDialog QFontDialog QInputDialog QMessageBox QProgressDialogQDialog Class帮助文档 示例&#xff1a;各按钮激发对话框实现基类提供的各效果 第一步&#xff1a;实现组件布局&…

C语言标准库函数qsort( )——数据排序

大家好&#xff01;我是保护小周ღ&#xff0c;本期为大家带来的是深度解剖C语言标准库函数 qsort()&#xff0c;qsort()函数他可以对任意类型的数据排序&#xff0c;博主会详细解释函数使用方法&#xff0c;以及使用快速排序的左右指针法模拟实现函数功能&#xff0c;这样的排…

本科毕业设计:计及并网依赖性的分布式能源系统优化研究。(C语言实现)(内包含NSGA II优化算法)(一)

目录 前言 1、分布式能源系统模型介绍 2、运行策略 前言 本篇文章介绍的是我的毕业设计&#xff0c;我将C语言将其实现。 1、分布式能源系统模型介绍 这是我将研究的分布式能源系统的框架&#xff0c;内部供能装置包括&#xff1a;太阳能光伏板&#xff1b;sofc燃料电池、太阳…

【数据结构】周末作业

1.new(struct list_head*)malloc(sizeof(struct list_head*)); if(newNULL) { printf("失败\n"); return; } new->nextprev->next; prev->nextnew; return; 2.struct list_head* pprev->next; prev->nextp->next; p->next->prevpr…

设计模式----装饰器模式

在软件开发过程中&#xff0c;有时想用一些现存的组件。这些组件可能只是完成了一些核心功能。但在不改变其结构的情况下&#xff0c;可以动态地扩展其功能。所有这些都可以釆用装饰器模式来实现。 装饰器模式 允许向一个现有的对象添加新的功能&#xff0c;同时又不改变他的…

python_可视化_交互_多条线段点击高亮显示

需求 使用matplotlib 绘制折线图 响应鼠标事件 单击折线 线条高亮显示 解决方法: 使用 mplcursors 库, 一句代码可实现. 代码 import matplotlib.pyplot as plt import mplcursors import numpy as np# 生成一些示例数据 x np.linspace(0, 10, 100) y np.sin(x)# 创建绘图…

Linux的gdb调试

文章目录 一、编译有调试信息的目标文件二、启动gdb调试文件1、查看内容list/l&#xff1a;l 文件名:行号/函数名&#xff0c;l 行号/函数名2、打断点b&#xff1a;b文件名:行号/函数名&#xff0c;b 行号/函数名 与 查看断点info/i&#xff1a;info b3、删除断点d&#xff1a;…

基于InternLM和LangChain搭建自己的知识库

背景 LLM存在一定的局限性&#xff0c;如&#xff1a; 知识时效性受限&#xff1a;如何让LLM能够获取最新的知识专业能力有限&#xff1a;如何打造垂直领域的大模型定制化成本高&#xff1a;如何打造个人专属的LLM应用 正文 为了突破LLM的局限性&#xff0c;目前有两种范式…

Python入门学习:if语句与条件控制--and、or、in、not in详解与实践

Python入门学习&#xff1a;if语句与条件控制–and、or、in、not in详解与实践 &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程&#x1…

Zookeeper启动报错排查

前言&#xff1a;生产linux部署的zookeeper&#xff0c;执行启动脚本后&#xff0c;还是无法使用&#xff0c;故进行重启排查 在zookeeper的bin目录下执行 ./zkServer.sh start-foreground 可实时查看启动日志排查问题 根据上面的日志可以看出&#xff0c;是zoo.cfg配置文件里…