0x24 迭代加深

2023-12-20 23:36
文章标签 迭代 加深 0x24

本文主要是介绍0x24 迭代加深,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

0x24 迭代加深

1.迭代加深

深度优先搜索每次选定一个分支,不断深入,直至到达递归边界才回溯。这种策略带有一定的缺陷。试想以下情况:搜索树每个节点的分支数目非常多,并且问题的答案在某个较浅的节点上。如果深搜在一开始就选错了分支,就很可能在不包含答案的深层子树上浪费许多时间。

此时,我们可以从小到大限制搜索的深度,如果在当前深度限制下搜不到答案,就把深度限制增加,重新进行一次搜索,这就是迭代加深的思想。所谓“迭代”,就是以上一次的结果为基础,重新执行以逼近答案的意思。迭代加深 D F S DFS DFS的过程如下:

在这里插入图片描述

虽然该过程在深度限制为 d d d时,会重复搜索第 1 ∼ d − 1 1\sim d-1 1d1层的节点,但是当搜索树节点分支数目较多时,随着层数的深入,每层节点数会呈指数级增长,这点重复搜索与深层子树的规模相比,实在是小巫见大巫了。

总而言之,当搜索树规模随着层次的深入增长很快,并且我们能够确保答案在一个较浅层的节点时,就可以采用迭代加深的深度优先搜索算法来解决问题。

2.双向搜索

除了迭代加深之外,双向搜索也可以避免在深层子树上浪费时间。在一些题目上,问题不但有“初态”,还具有明确的“终态”,并且从初态开始搜索与从终态开始逆向搜索产生的搜索树都能覆盖这个状态空间。在这种情况下,就可以采用双向搜索——从初态到终态出发各搜索一半状态,产生两颗深度减半的搜索树,在中间交会、组合成最终的答案

如下图所示,左侧是直接进行一次搜索产生的搜索树,右侧是双向搜索产生的两颗搜索树,避免了层数过深时分支数量的大规模增长。

在这里插入图片描述

这篇关于0x24 迭代加深的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle

C++变换迭代器使用方法小结

《C++变换迭代器使用方法小结》本文主要介绍了C++变换迭代器使用方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、源码2、代码解析代码解析:transform_iterator1. transform_iterat

Mybatis从3.4.0版本到3.5.7版本的迭代方法实现

《Mybatis从3.4.0版本到3.5.7版本的迭代方法实现》本文主要介绍了Mybatis从3.4.0版本到3.5.7版本的迭代方法实现,包括主要的功能增强、不兼容的更改和修复的错误,具有一定的参考... 目录一、3.4.01、主要的功能增强2、selectCursor example3、不兼容的更改二、

C#使用yield关键字实现提升迭代性能与效率

《C#使用yield关键字实现提升迭代性能与效率》yield关键字在C#中简化了数据迭代的方式,实现了按需生成数据,自动维护迭代状态,本文主要来聊聊如何使用yield关键字实现提升迭代性能与效率,感兴... 目录前言传统迭代和yield迭代方式对比yield延迟加载按需获取数据yield break显式示迭

迭代器模式iterator

学习笔记,原文链接 https://refactoringguru.cn/design-patterns/iterator 不暴露集合底层表现形式 (列表、 栈和树等) 的情况下遍历集合中所有的元素

多线程篇(阻塞队列- LinkedBlockingDeque)(持续更新迭代)

目录 一、LinkedBlockingDeque是什么 二、核心属性详解 三、核心方法详解 addFirst(E e) offerFirst(E e) putFirst(E e) removeFirst() pollFirst() takeFirst() 其他 四、总结 一、LinkedBlockingDeque是什么 首先queue是一种数据结构,一个集合中

多线程篇(阻塞队列- LinkedBlockingQueue)(持续更新迭代)

目录 一、基本概要 1. 构造函数 2. 内部成员 二、非阻塞式添加元素:add、offer方法原理 offer的实现 enqueue入队操作 signalNotEmpty唤醒 删除线程(如消费者线程) 为什么要判断if (c == 0)时才去唤醒消费线程呢? 三、阻塞式添加元素:put 方法原理 图解:put线程的阻塞过程 四、非阻塞式移除:poll方法原理 dequ

六、我们应当怎样做需求调研:迭代

前面我一直在反复强调这样一个观点,需求分析不是一蹴而就的,是一个反复迭代的过程。它将从第一次需求分析开始,一直持续到整个项目生命周期。为什么这样说呢?让我们一起来分析分析。  在第一次的需求分析阶段,我们在一段时期内需要与客户进行反复地讨论,这个过程往往是这样一个反复循环的过程:需求捕获->需求整理->需求验证->再需求捕获••••••  需求捕获,就是我们与客户在一起开研讨会

多线程篇(阻塞队列- ArrayBlockingQueue)(持续更新迭代)

目录 一、源码分析 1. 先看个关系图 2. 构造方法 3. 核心属性 4. 核心功能 入队(放入数据) 出队(取出数据) 5. 总结 一、源码分析 1. 先看个关系图 PS:先看个关系图 ArrayBlockingQueue是最典型的有界阻塞队列,其内部是用数组存储元素的, 初始化时需要指定容量大小利用 ReentrantLock 实现线程安全。 在生产者

多线程篇(并发相关类- 原子操作类)(持续更新迭代)

目录 前言 一、原子变量操作类(AtomicLong为例) 1. 前言 2. 实例 二、JDK 8新增的原子操作类LongAdder 三、LongAccumulator类原理探究 前言 JUC包提供了一系列的原子性操作类,这些类都是使用非阻塞算法CAS实现的,相比使用锁实现原子性操作这在性能上有很大提高。 由于原子性操作类的原理都大致相同,这里讲解最简单的AtomicLo