写给妹妹的编程札记 3 - 穷举: 深度优先搜索/广度优先搜索

2024-05-24 04:58

本文主要是介绍写给妹妹的编程札记 3 - 穷举: 深度优先搜索/广度优先搜索,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

        前文,我们讨论了从循环遍历到搜索基本框架,并解决了一个经典的八皇后问题。对搜索剪枝也有了一些基本的了解。 下面, 我们来看看搜索的两个最基本的策略: 深度优先搜索和广度优先搜索。

        Wikipedia上有比较简单的介绍 (英文版包含更多的参考信息)

                深度优先搜索:

                        http://zh.wikipedia.org/wiki/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2

                        http://en.wikipedia.org/wiki/Depth-first_search

                广度优先搜索:

                        http://zh.wikipedia.org/wiki/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2

                        http://en.wikipedia.org/wiki/Breadth-first_search


        首先看一个比较简单的例子, 假如我们要搜索树数据结构上的节点,找出树结构上权重为5的节点,如果存在多个权重为5的节点,返回距离根节点最近的任意一个。在这里例子中, 之所以说简单的原因在于从根节点出发, 到每个节点只有一条路径可以达到。实际场景中,搜索空间中节点之间关系可能是复杂的,两个节点之间有多条可达路径。


        下面首先看深度优先搜索,怎么进行搜索?

                 第一步:搜索根节点 (A, 1), 权重为1, 并不等于5

                 第二步:任意挑选一个子节点继续 (深度+1), 访问(E, 4), 权重为4, 并不等于5

                 第三步:任意挑选一个当前节点的子节点继续 (深度+1)  - 访问(C, 3)

                              这里就是体现了深度优先, 虽然根节点(A, 1)的子节点(B, 5), (F, 8) 还没有遍历, 但我们优先往纵深方向遍历

                              (C, 3) 的权重为3, 也不等于5

                 第四步:任意挑选一个当前节点的子节点继续(深度+1) ? 

                              不过,我们发现(C, 3) 没有”更深“的子节点。 怎么办? 这个时候,我们需要回溯, 也就是访问上一个节点的其他子节点。

                              (C, 3)的上个节点是什么?我们需要保存这个信息,后进先出的栈结构适合这个需求。 因为回溯的时候,最先需要访问的是最后压入栈的节点。

                              当我们知道(C, 3)的上一个节点是(E, 4)后, 我们在第四步,尝试访问(E, 4)尚未访问过的节点(D, 5)


                              节点(D, 5)的权重等于5。 我们找到一个候选! 

                              这个时候,我们能够停止了吗? 如果题目要求只要找到任意一个权重等于5的话,我们已经找到了。

                              但,由于题目要求如果多个节点权重相等,需要返回距离根节点比较近的。 所以我们还需要继续遍历下去......

                  ......


        我们尝试结合栈数据结构,重新整理一下上面的搜索过程:

                第一步:判断根节点(A, 1),  权重不等于5

                             把根节点压入栈, 栈中包含元素[ (A, 1)

                第二步:任意挑选栈顶元素(A, 1)的尚未访问过”的一个子节点(E, 4)进行访问

                             判断节点(E, 4)的权重,权重不等于5

                             把节点(E, 4)压入栈,栈中包含元素[ (A, 1), (E, 4)

                第三步:任意挑选栈顶元素(E, 4)的尚未访问过”的一个子节点(C, 3)进行访问

                             判断节点(C, 3)的权重,权重不等于5

                             把节点(C, 3)压入栈,栈中包含元素[ (A, 1), (E, 4), (C, 3)

                第四步:任意挑选栈顶元素(C, 3)的尚未访问过”的一个子节点进行访问, 

                             但(C, 3)没有子节点, 把节点(C, 3)弹出栈,栈中包含元素[ (A, 1), (E, 4)

                第五步:任意挑选栈顶元素(E, 4)的尚未访问过”的一个子节点(D, 5)进行访问, 

                             判断节点(D, 5)的权重,权重等于5, 记录下一个解

                             把节点(D, 5)压入栈,栈中包含元素[ (A, 1), (E, 4), (D, 5)

                第六步:任意挑选栈顶元素(D, 5)的尚未访问过”的一个子节点进行访问, 

                             但(D, 5)没有子节点, 把节点(D, 5)弹出栈,栈中包含元素[ (A, 1), (E, 4)

                第六步:任意挑选栈顶元素(E, 4)的尚未访问过”的一个子节点进行访问, 

                             但(E, 4)没有”尚未访问过的“子节点, 把节点(E, 4)弹出栈,栈中包含元素[ (A, 1)

                ......

                一直进行到栈空为止


        可以看到上面的每一步操作,已经比较”机械“, 类似于《写给妹妹的编程札记 1 - 穷举: 从循环到递归》的转化,不难写出搜索程序。虽然上面描述的时候, 我们显式定义了栈数据结构,但实际程序中,有时也可以直接利用递归程序本身使用的系统调用栈。





        接下来,我们再来看广度优先搜索,怎么进行的?

                 第一步:搜索根节点 (A, 1), 权重为1, 并不等于5

                 第二步:遍历根节点的所有子节点

                                 这里就是体现了广度优先,优先遍历当前看到的所有子节点

                                 2.a 访问节点(E, 4), 权重为4, 并不等于5

                                 2.b 访问节点(B, 5), 权重为5, 等于5!

                                 2.c 访问节点(F, 8), 权重为8, 并不等于5


                                 这个时候,我们已经找到一个解,节点(B, 5), 是否应该结束呢?

                                 对于当前问题, 我们可以结束了。 因为不可能还有其他权重等于5的节点,距离根节点比(B, 5)还要近。


         如果题目要求我们找到所有权重为5的节点,那么,我们还需要继续,直到遍历完所有节点。

                 第三步:在遍历完所有根节点的子节点后, 下一步,我们应该是要遍历根节点子节点的子节点。

                                 我们怎么知道根节点的子节点是什么呢? 需要一个额外的数据结构存储起来。

                                 先进先出的队列适合这个要求,因为我们按访问过的子节点顺序,遍历这些子节点的子节点

                                 首先,遍历根节点的第一个子节点(E, 4)的所有子节点:

                                 3.a  访问节点(C, 3), 权重为3, 并不等于5

                                 3.b  访问节点(D, 5), 权重为5, 等于5!又找到一个解。

                  ......


        类似地,我们尝试结合队列数据结构,重新整理一下上面的搜索过程:

               第一步:访问根节点(A, 1),  权重不等于5

                               把根节点插入队列, 队列中包含元素 <(A, 1)>

               第二步:遍历队首节点(A,1)的所有“尚未访问过”子节点

                               2.a 访问节点(E, 4), 权重为4, 并不等于5

                                      把节点(E, 4)插入队列, 队列中包含元素<(A, 1), (E, 4)>

                               2.b 访问节点(B, 5), 权重为5, 等于5!
                                      把节点(B, 5)插入队列, 队列中包含元素<(A, 1), (E, 4), (B, 5)>
                               2.c 访问节点(F, 8), 权重为8, 并不等于5
                                      把节点(F, 8)插入队列, 队列中包含元素<(A, 1), (E, 4), (B, 5), (F, 8)>

                               到此为止,队首节点(A, 1)的所有子节点已经遍历完,可以把队首元素从队列中删除, 此时队列中包含元素<(E, 4), (B, 5), (F, 8)>

                               队列数据结构,始终保存着已经被遍历,但子节点尚未被遍历的所有节点的集合。

                第三步:遍历队首节点(E,4)的所有“尚未访问过”子节点

                                ......

                一直进行到队列为空为止。


        深度优先搜索和广度优先搜索的基本思想,如上面描述这样,非常直接和容易理解。简单的比较可以给我们一个印象:

        1. 一般如果需要找出所有解, 深度优先搜索会比广度优先搜索好。 虽然两者时间复杂度上差不多,但广度优先搜索需要比较大的空间来存储队列。

        2. 求最优解时, 一般可以优先考虑广度优先搜索。深度优先搜索一般需要遍历所有可能,而广度优先可以通过设计使得寻找到的第一个就是最优的。


        深度优先搜索和广度优先搜索的取舍还是需要具体问题具体分析。 她们是非常基本的框架,在这些基本框架的基础上, 有很多变种,技巧,技术和演化。如: A*, alpha-beta剪枝, 爬山法,beam search等等等等。 有些巧妙的算法,也充分利用和吸收了这些基本搜索策略。如,有向图的强连通分支可以通过两次深度优先遍历得到, 单源最短路的Dijkstra算法跟广度优先算法类似等等。




        

这篇关于写给妹妹的编程札记 3 - 穷举: 深度优先搜索/广度优先搜索的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/997437

相关文章

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

Python与DeepSeek的深度融合实战

《Python与DeepSeek的深度融合实战》Python作为最受欢迎的编程语言之一,以其简洁易读的语法、丰富的库和广泛的应用场景,成为了无数开发者的首选,而DeepSeek,作为人工智能领域的新星... 目录一、python与DeepSeek的结合优势二、模型训练1. 数据准备2. 模型架构与参数设置3

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

C#多线程编程中导致死锁的常见陷阱和避免方法

《C#多线程编程中导致死锁的常见陷阱和避免方法》在C#多线程编程中,死锁(Deadlock)是一种常见的、令人头疼的错误,死锁通常发生在多个线程试图获取多个资源的锁时,导致相互等待对方释放资源,最终形... 目录引言1. 什么是死锁?死锁的典型条件:2. 导致死锁的常见原因2.1 锁的顺序问题错误示例:不同