每周一算法:迭代加深搜索

2024-03-15 19:52

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

题目链接

加成序列

题目描述

满足如下条件的序列 X X X(序列中元素被标号为 1 、 2 、 3 … m 1、2、3…m 123m)被称为加成序列

  1. X [ 1 ] = 1 X[1]=1 X[1]=1
  2. X [ m ] = n X[m]=n X[m]=n
  3. X [ 1 ] < X [ 2 ] < … < X [ m − 1 ] < X [ m ] X[1]<X[2]<…<X[m−1]<X[m] X[1]<X[2]<<X[m1]<X[m]
  4. 对于每个 k k k 2 ≤ k ≤ m 2≤k≤m 2km)都存在两个整数 i i i j j j 1 ≤ i , j ≤ k − 1 1≤i,j≤k−1 1i,jk1 i i i j j j可以相等),使得 X [ k ] = X [ i ] + X [ j ] X[k]=X[i]+X[j] X[k]=X[i]+X[j]

你的任务是:给定一个整数 n n n,找出符合上述条件的长度 m m m最小的“加成序列”

如果有多个满足要求的答案,只需要找出任意一个可行解。

输入格式

输入包含多组测试用例。
每组测试用例占据一行,包含一个整数 n n n

当输入为单行的 0 0 0 时,表示输入结束。

输出格式

对于每个测试用例,输出一个满足需求的整数序列,数字之间用空格隔开。

每个输出占一行。

数据范围

1 ≤ n ≤ 100 1≤n≤100 1n100

输入样例

5
7
12
15
77
0

输出样例

1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77

算法思想

题目要求输出长度最小的加成序列,由于要输出序列,因此深度优先搜索是一个不错的选择。
深度优先搜索的基本思想是每次选定一个分支,不断深入,直至到达递归边界然后回溯。这种策略带有一定的缺陷,试想当搜索树每个节点的分支数目非常多,并且问题的答案在某个较浅的节点上,如果深搜一开始选错了分支,就很可能在不包含答案的深层子树上浪费很多时间。如下图所示:
在这里插入图片描述
上图表示搜索的状态空间,红色五角星为答案,那么深度优先搜索算法产生的搜索树如下图所示,算法中矩形圈出的深层子树浪费了很多时间。
在这里插入图片描述
此时,可以从小到大限制搜索的深度,如果在当前深度限制下搜索不到答案,就把深度限制增加,重新进行一次搜索,这就是迭代加深思想。

所谓“迭代”,就是以上一次的结果为基础,重复执行以逼近答案的思想,迭代加深搜索的过程如下:
在这里插入图片描述
虽然搜索过程中深度限制为 d d d时,会重复搜索 1 ∼ d − 1 1\sim d-1 1d1层的节点,但是当搜索树节点分支数目较多时,随着层数的深入,每层节点数会呈指数级增长,这点重复搜索与深层子树的规模相比,实在是小巫见大巫了。

总而言之,当搜索树规模随着层次的深入增长很快,并且题目能够确保答案在一个较浅层的节点时,就可使采用迭代加深的深度优先搜索算法来解决。例如,有些题目描述会包含“如果10步内搜索不到结果就算无解”的情况。

算法实现

寻找最短加成序列恰好符合迭代加深搜索的情况,序列的长度 m ( m ≤ 10 ) m(m\le10) mm10不会太大,但是每次枚举两个数的和产生的分支很多,即搜索树规模随着层次的深入增长很快,并且答案在一个较浅层的节点。算法实现的基本过程如下:

  • 序列中的第一个数为 1 1 1,即 X [ 1 ] = 1 X[1]=1 X[1]=1
  • 依次搜索序列中的每个位置 k k k
    • 当到达限制搜索深度时,搜索结束,如果序列中最后一个数为 n n n,即 X [ m ] = n X[m]=n X[m]=n,则找到最短加成序列。
    • 为了保证 X [ k ] = X [ i ] + X [ j ] X[k]=X[i]+X[j] X[k]=X[i]+X[j],枚举序列已确定的任意两个数求和,将其填入 k k k位置
    • 继续搜索 k + 1 k+1 k+1位置

算法优化

  • 优化搜索顺序:为了最快搜索到 n n n,可以优先枚举序列中较大的数
  • 排除等效冗余:对于序列中两个数的和,如果已经搜索过,就没有必要在递归搜索了,例如: 1 + 4 1+4 1+4 2 + 3 2+3 2+3,其和都为 5 5 5,搜索一次即可。

代码实现

#include <iostream>
using namespace std;
const int N = 105;
int x[N]; //加成序列
int n, m = N;
//k表示序列当前位置,d表示限制搜索深度
bool dfs(int k, int d)
{//达到限制搜索深度时,如果序列中最后一个元素为n,返回真,否则返回假if(k == d) return x[k - 1] == n; bool st[N] = {0}; //通过标记,排除等效冗余,即已经搜索过的和//优化搜索顺序,优先选择较大的数进行求和for(int i = k - 1; i >= 0; i --){for(int j = i; j >= 0; j --){int sum = x[i] + x[j];if(sum <= x[k - 1] || sum > n || st[sum]) continue;st[sum] = true;x[k] = sum;if(dfs(k + 1, d)) return true;}}return false;
}
int main()
{x[0] = 1; // 第1个数字是1while(cin >> n, n){int d = 1; //从深度1开始,迭代加深搜索,直到找到一组加成序列while(!dfs(1, d)) d ++;for(int i = 0; i < d; i ++) cout << x[i] << " ";cout << endl;}return 0;
}

这篇关于每周一算法:迭代加深搜索的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java设计模式---迭代器模式(Iterator)解读

《Java设计模式---迭代器模式(Iterator)解读》:本文主要介绍Java设计模式---迭代器模式(Iterator),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录1、迭代器(Iterator)1.1、结构1.2、常用方法1.3、本质1、解耦集合与遍历逻辑2、统一

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具,能够有效提升用户体验,通过结合自动补全功能和适当的样式,可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框(Search Box)详解搜索框是一个用于输入查询内容的控件,通常用于网站或应用程

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

C++迭代器失效的避坑指南

《C++迭代器失效的避坑指南》在C++中,迭代器(iterator)是一种类似指针的对象,用于遍历STL容器(如vector、list、map等),迭代器失效是指在对容器进行某些操作后... 目录1. 什么是迭代器失效?2. 哪些操作会导致迭代器失效?2.1 vector 的插入操作(push_back,

Android NDK版本迭代与FFmpeg交叉编译完全指南

《AndroidNDK版本迭代与FFmpeg交叉编译完全指南》在Android开发中,使用NDK进行原生代码开发是一项常见需求,特别是当我们需要集成FFmpeg这样的多媒体处理库时,本文将深入分析A... 目录一、android NDK版本迭代分界线二、FFmpeg交叉编译关键注意事项三、完整编译脚本示例四

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

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

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

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n