IDA*——AcWing 180. 排书

IDA*

定义

IDA*(Iterative Deepening A*)是一种结合了深度优先搜索(DFS)的递归深度限制特性和A搜索的启发式估价函数的搜索算法。它主要用于解决启发式搜索问题,尤其是当搜索空间很大或者搜索成本不确定时。

IDA* 是一种最佳优先搜索算法,其基本思想是在深度优先搜索的基础上,通过逐步增加搜索深度并结合A*算法中的估价函数f(n)=g(n)+h(n),来找到从初始节点到目标节点的最短路径。其中,g(n)是从初始节点到当前节点的实际代价,h(n)是从当前节点到目标节点的启发式估计代价。

运用情况

  1. 内存限制: IDA特别适合那些内存有限制的环境,因为它不像A那样需要维护一个开放列表(open list),而是采用递归的方式逐步深入搜索。
  2. 未知或变化的成本: 当搜索空间中节点的移动成本不是预先完全已知或可能变化时,IDA*通过逐步探索来适应这种不确定性。
  3. 最优解搜索: 当寻找问题的最优解而非任一解时,IDA*通过其最佳优先的特性保证找到的是从起点到终点的最短路径。
  4. 大型或无限状态空间: 对于状态空间非常大或理论上无限的情况,IDA*通过逐步加深搜索深度来逐步逼近解,避免了一次性需要大量内存来存储整个搜索树的问题。

注意事项

  1. 启发式函数的选择: h(n)的选择至关重要,它需要保证不大于实际的最小代价,否则算法可能不会终止。理想的h(n)接近实际成本但又易于计算。
  2. 深度限制: 初始时设置一个合理的深度限制,随着搜索的进行逐渐增加,直到找到解或达到某个预设的深度上限。
  3. 效率: 虽然IDA避免了A中的开放列表维护,但如果启发式不够好或搜索空间极大,递归调用可能会导致大量的重复计算和较慢的收敛速度。
  4. 栈溢出风险: 由于使用递归,如果搜索深度过大,可能会导致栈溢出。在实现时可以考虑使用迭代版本来避免这一问题。

解题思路

  1. 初始化: 设定初始深度限制d=0,以及一个足够大的上限D作为退出条件。
  2. 计算阈值: 使用当前深度限制计算f(n)的阈值,即f_limit = g(start) + d * h(start),其中g(start)=0,因为是从初始节点开始。
  3. 深度优先搜索: 从初始节点开始执行深度优先搜索,只有当节点的f(n)=g(n)+h(n)小于当前的f_limit时才继续扩展该节点的子节点。
  4. 递归加深: 如果在当前深度限制下没有找到解,则增加深度限制d=d+1,回到步骤2,继续搜索。
  5. 结束条件: 当搜索到目标节点或达到预设的深度上限D时,结束搜索。

AcWing 180. 排书   

题目描述

180. 排书 - AcWing题库

运行代码

#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 15;  // 书的数量上限
using namespace std;
int n;  // 实际的书的数量
int q[N];  // 存储书的初始排列
int w[5][N]; // 辅助数组,用于在搜索过程中保存中间状态 
// 估价函数:计算当前状态与目标状态的差异,返回还需要多少步才能达到目标状态
int f() { int tot = 0;for (int i = 0; i + 1 < n; ++i) {if (q[i + 1]!= q[i] + 1) {++tot;}}return (tot + 2) / 3;
} 
// 深度优先搜索函数
bool dfs(int depth, int max_depth) { if (depth + f() > max_depth) { // 如果当前深度加上估计的剩余深度超过了限制深度,进行剪枝return false; }if (f() == 0) { // 如果估价函数为0,说明已经达到目标状态return true; }for (int len = 1; len < n; ++len) { // 枚举要移动的连续段的长度for (int l = 0; l + len - 1 < n; ++l) { // 枚举连续段的起始位置int r = l + len - 1; for (int k = r + 1; k < n; ++k) { // 枚举要插入的位置(连续段的结束位置的后面)memcpy(w[depth], q, sizeof q); // 复制当前状态到辅助数组int y = l; for (int x = r + 1; x <= k; x++, y++) { // 将连续段插入到指定位置q[y] = w[depth][x]; }for (int x = l; x <= r; x++, y++) {q[y] = w[depth][x]; }if (dfs(depth + 1, max_depth)) { // 递归搜索下一层return true; }memcpy(q, w[depth], sizeof q); // 如果不成功,恢复当前状态 }}}return false; 
} 
int main() { int T; cin >> T; while (T--) { cin >> n; for (int i = 0; i < n; ++i) {cin >> q[i]; }int depth = 0; // 迭代加深搜索,从深度0开始,每次增加1,直到找到解或者深度达到5while (depth < 5 &&!dfs(0, depth)) { depth++; }if (depth >= 5) {cout << "5 or more" << endl; } else {cout << depth << endl; }}return 0; 
}

代码思路

  • 估价函数 f():用于估计从当前状态到达目标状态(书按照 1∼n 的顺序依次排列)还需要的最少操作次数。通过计算当前排列中顺序不正确的后继关系的数量 tot ,然后返回 (tot + 2) / 3 作为估计值。这是因为每次移动一个连续段最多可以改变 3 个元素的后继关系。
  • dfs(int depth, int max_depth) 函数:进行深度优先搜索。
    • 参数 depth 表示当前搜索的深度(即已经进行的操作次数)。
    • max_depth 是限制的最大深度。如果在当前深度 depth 下,加上估计的还需要的最少操作次数 f() 超过了 max_depth ,就意味着即使后面按照最优方式操作也无法在限制深度内达到目标状态,此时进行剪枝(直接返回 false ,不再继续搜索该路径)。
    • 通过三重循环来枚举移动连续段的长度、起始位置和插入位置,模拟进行抽取连续段并插入到其他位置的操作。
    • 在每次尝试一种可能的操作后,递归调用 dfs(depth + 1, max_depth) 搜索下一层。如果找到解(即达到目标状态),则返回 true ,否则恢复原来的状态(通过 memcpy(q, w[depth], sizeof q); ),继续尝试其他可能的操作。
  • 主函数中的迭代加深搜索:从深度 0 开始,每次增加 1,调用 dfs(0, depth) 进行搜索。如果在深度小于等于 4 时找到了解,就输出对应的操作次数;如果直到深度达到 5 还没有找到解,就输出 "5 or more" 。

改进思路

  1. 优化内存使用:可以减少使用的辅助数组数量,或者使用更高效的数据结构来存储中间状态。
  2. 改进剪枝策略:可以进一步优化估价函数,使其更加准确,从而增强剪枝效果,减少不必要的搜索。
  3. 优化循环结构:对于一些循环的边界条件和步长进行优化,以减少不必要的计算。

改进代码

#include <iostream>
#include <cstring>
#include <algorithm>const int N = 15;  // 书的数量上限int n;  // 实际的书的数量
int q[N];  // 存储书的初始排列// 估价函数:计算当前状态与目标状态的差异,返回还需要多少步才能达到目标状态
int f() { int tot = 0;for (int i = 0; i + 1 < n; ++i) {if (q[i + 1]!= q[i] + 1) {++tot;}}return (tot + 2) / 3;
} // 深度优先搜索函数
bool dfs(int depth, int max_depth) { if (depth + f() > max_depth) { // 如果当前深度加上估计的剩余深度超过了限制深度,进行剪枝return false; }if (f() == 0) { // 如果估价函数为0,说明已经达到目标状态return true; }for (int len = 1; len < n; ++len) { // 枚举要移动的连续段的长度for (int l = 0; l + len - 1 < n; ++l) { // 枚举连续段的起始位置int r = l + len - 1; for (int k = r + 1; k < n; ++k) { // 枚举要插入的位置(连续段的结束位置的后面)int temp[N];memcpy(temp, q, sizeof(q));  // 复制当前状态int y = l; for (int x = r + 1; x <= k; x++, y++) { // 将连续段插入到指定位置q[y] = temp[x]; }for (int x = l; x <= r; x++, y++) {q[y] = temp[x]; }if (dfs(depth + 1, max_depth)) { // 递归搜索下一层return true; }memcpy(q, temp, sizeof(q)); // 如果不成功,恢复当前状态 }}}return false; 
} int main() { int T; std::cin >> T; while (T--) { std::cin >> n; for (int i = 0; i < n; ++i) {std::cin >> q[i]; }int depth = 0; // 迭代加深搜索,从深度0开始,每次增加1,直到找到解或者深度达到5while (depth < 5 &&!dfs(0, depth)) { depth++; }if (depth >= 5) {std::cout << "5 or more" << std::endl; } else {std::cout << depth << std::endl; }}return 0; 
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

场景管理分析平台介绍

在数字化浪潮的推动下&#xff0c;数据已成为企业决策的重要依据。特别是在智能驾驶、虚拟现实和物联网等领域&#xff0c;场景数据的高效管理和利用至关重要。在智能驾驶领域面对海量的场景数据&#xff0c;如何高效处理、精准分析&#xff0c;并将其转化为有价值的决策支持&a…

C++基础(十一):STL简介

从今天开始&#xff0c;我们正式步入STL的学习&#xff0c;STL&#xff08;标准模板库&#xff0c;Standard Template Library&#xff09;是C标准库的重要组成部分&#xff0c;提供了一系列通用的类和函数模板&#xff0c;包括容器、算法、迭代器等。它的设计极大地提高了代码…

AI让大龄程序员重新焕发活力

AI是在帮助开发者还是取代他们&#xff1f; 在软件开发领域&#xff0c;生成式人工智能&#xff08;AIGC&#xff09;正在改变开发者的工作方式。无论是代码生成、错误检测还是自动化测试&#xff0c;AI工具正在成为开发者的得力助手。然而&#xff0c;这也引发了对开发者职业…

Python爬虫零基础实战,简洁实用!

1.爬虫简介 简单来讲&#xff0c;爬虫就是一个探测机器&#xff0c;它的基本操作就是模拟人的行为去各个网站溜达&#xff0c;点点按钮&#xff0c;查查数据&#xff0c;或者把看到的信息背回来。就像一只虫子在一幢楼里不知疲倦地爬来爬去。 你可以简单地想象&#xff1a;每个…

【SPIE独立出版】第四届智能交通系统与智慧城市国际学术会议(ITSSC 2024)

第四届智能交通系统与智慧城市国际学术会议&#xff08;ITSSC 2024&#xff09;将于2024年8月23-25日在中国西安举行。本次会议主要围绕智能交通、交通新能源、无人驾驶、智慧城市、智能家居、智能生活等研究领域展开讨论&#xff0c; 旨在为该研究领域的专家学者们提供一个分享…

文心一言最常用的20条指令及指令说明,含增强指令

下面是20条文心一言的指令及其说明&#xff0c;每条指令尽量简洁明了&#xff0c;以便在有限的字数内提供尽可能多的信息。以下是这些指令及其说明&#xff1a; 1. 查询天气 指令&#xff1a;今天北京的天气怎么样&#xff1f;说明&#xff1a;此指令用于查询特定城市&#xf…

无人机5公里WiFi低延迟图传模组,抗干扰、长距离、低延迟,飞睿智能无线通信新标杆

在科技日新月异的今天&#xff0c;我们见证了无数通信技术的飞跃。从开始的电报、电话&#xff0c;到如今的4G、5G网络&#xff0c;再到WiFi的广泛应用&#xff0c;每一次技术的革新都极大地改变了人们的生活方式。飞睿智能5公里WiFi低延迟图传模组&#xff0c;它以其独特的优势…

Python 获取tiktok视频评论回复数据 api接口

TIKTOK api接口 用于爬取tiktok视频评论回复数据 详细采集页面如图 https://www.tiktok.com/dailymail/video/7329872821990182190?qneural%20link&t1706783508149 请求API http://api.xxxx.com/tt/video/info/comment/reply?video_id7288909913185701125&comment_…

ELK优化之Filebeat部署

目录 1.安装配置Nginx 2.安装 Filebeat 3.设置 filebeat 的主配置文件 4.修改Logstash配置 5.启动配置 6.kibana验证 主机名ip地址主要软件es01192.168.9.114ElasticSearches02192.168.9.115ElasticSearches03192.168.9.116ElasticSearch、Kibananginx01192.168.9.113ng…

AE的首选项设置

打开AE,点击 编辑->首选项->常规 显示 点击“所有关键帧”&#xff0c;这样显示路径就会显示所有关键帧 导入 将序列素材改为25帧每秒&#xff0c;作为以后制作的默认 媒体和磁盘缓存 根据个人需求选择磁盘缓存的文件夹&#xff0c;如果d盘空间充足&#xff0c;就改成…

上海外贸建站公司wordpress模板推荐

Sora索啦高端制造业wordpress主题 红色高端制造业wordpress主题&#xff0c;适合外贸企业出海建独立站的wordpress模板。 https://www.jianzhanpress.com/?p5885 Yamal外贸独立站wordpress主题 绿色的亚马尔Yamal外贸独立站wordpress模板&#xff0c;适用于外贸公司建独立站…

Autosar MCAL-S32k324 Crypto配置-RandomNumber生成及使用

文章目录 前言CryptoPrimitivesCryptoPrimitiveAlgorithmFamilyCryptoPrimitiveAlgorithmModeCryptoPrimitiveAlgorithmSecondaryFamilyCryptoPrimitiveServiceCryptoDriverObject代码使用Random Generate执行流程配置job函数使用示例总结前言 之前介绍过AES-CMAC算法的配置,…

Linux|信号

Linux|信号 信号的概念信号处理的三种方式捕捉信号的System Call -- signal 1.产生信号的5种方式2.信号的保存2.1 core 标志位 2.信号的保存2.1 对pending 表 和 block 表操作2.2 阻塞SIGINT信号 并打印pending表例子 捕捉信号sigaction 函数验证当前正在处理某信号&#xff0c…

视觉语言模型:融合视觉与语言的未来

1. 概述 视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;是能够同时处理和理解视觉&#xff08;图像&#xff09;和语言&#xff08;文本&#xff09;两种模态信息的人工智能模型。这种模型结合了计算机视觉和自然语言处理的技术&#xff0c;使得它们能够在…

代码随想录-Day49

300. 最长递增子序列 给你一个整数数组 nums &#xff0c;找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列&#xff0c;删除&#xff08;或不删除&#xff09;数组中的元素而不改变其余元素的顺序。例如&#xff0c;[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的 …

使用握手信号实现跨时钟域数据传输

目录 描述 输入描述&#xff1a; 输出描述&#xff1a; 参考代码 描述 分别编写一个数据发送模块和一个数据接收模块&#xff0c;模块的时钟信号分别为clk_a&#xff0c;clk_b。两个时钟的频率不相同。数据发送模块循环发送0-7&#xff0c;在每个数据传输完成之后&#xf…

Cube-Studio:开源大模型全链路一站式中台

开源项目&#xff0c;欢迎star哦&#xff0c;https://github.com/data-infra/cube-studio 一款真正意义的 LLMOps 框架 LLMOps&#xff08;Large Language Model Operations&#xff09;是一个涵盖了大型语言模型&#xff08;如GPT系列&#xff09;开发、部署、维护和优化的一…

docker部署mycat,连接上面一篇的一主二从mysql

一、docker下载mycat镜像 查看安装结果 这个名称太长&#xff0c;在安装容器时不方便操作&#xff0c;设置标签为mycat docker tag longhronshens/mycat-docker mycat 二、安装容器 先安装一个&#xff0c;主要目的是获得配置文件 docker run -it -d --name mycat -p 8066:…

SpringBoot新手快速入门系列教程7:基于Redis的一个简单存取数据的例子

新手可能有这样的疑问&#xff0c;有了数据库的存取方式&#xff0c;我们为什么还要使用Redis这种缓存数据库读取方式呢&#xff1f; 原因主要有以下几点&#xff1a; 1. 性能提升 数据库查询尤其是复杂查询可能会消耗大量的时间和资源。而Redis是一个内存数据库&#xff0c…

刷题之买股票的最佳时机(leetcode)

买股票的最佳时机 动态规划入门题。 最简单的模拟式解法&#xff1a; class Solution { public:int maxProfit(vector<int>& prices) {//也可以换一种思路&#xff0c;因为只交易一次&#xff0c;那么找出股票最便宜的时候买入&#xff0c;最贵的时候卖出&#xff…