连云港做网站制作/百度关键词搜索引擎排名优化
目录
闲聊
前言
DFS算法的无效搜索
BFS算法的空间浪费
IDDFS
A*算法
IDA*
Power Calculus
问题描述
输入
输出
问题分析
代码
闲聊
前几周在忙着数学竞赛,所以就没时间更新,高等数学,一生之敌,真不知道报名的时候我是怎么想的,看了几个星期宋浩,就跑的去丢人现眼了(@_@),没几题会做的。就算是捐款了。
前言
这次讲的是IDA*算法,有关IDA*算法,我想先聊聊IDFS,BFS,IDDFS,A*这些图算法。
DFS算法的无效搜索
dfs算法又叫深度优先算法,就是对一个图搜索时,这个算法是一条完整路径一条完整路径搜索,怎么算一条完整路径呢,简单数对于一棵树从他的根节点到叶子节点,对于一个复杂的图,就是他搜索的最后一个节点没办法再衍生出其他路径的时候,假设我吗要对一棵树使用dfs进行遍历,就会发现如果这棵树很深,但是答案又在非常浅的地方,就会导致大量的无效搜索。
BFS算法的空间浪费
bfs算法又叫广度优先搜索,简单说就是一层一层的进行搜索,但写过bfs算法的都知道,对于每一层,我们一般都需要开出一定的空间来存储当前层的信息,以便进行下一层的搜索,如果这棵树比较复杂,那么这个空间消耗也是非常大的。
IDDFS
前面说明了BFS算法和DFS算法的缺点,我们现在来说说他们的优点,BFS算法的优点就是对于答案再很浅的层级时,这个算法很高效,没有过多的无效搜索,DFS算法的优点就是空间消耗非常少,因为它只需要开出一条路径的内存即可,而这条路径的深度绝对不会超过树的深度,可以发现,这两个算法其实是互补的,如果我们可以将两个算法适当结合,那么将极大提高算法的时间,空间效率,这就是IDDFS算法。
IDDFS算法是一个限制深度的DFS算法,不是说人家dfs总是一股脑往一条路走吗,那么我们给他加一个限制让他不要一直走下去不就行了吗。在代码上体现就是再原本dfs的基础上增加一个剪枝,如果当前搜索深度大于我所设定的深度,就return
A*算法
我觉得这应该不算一种算法,应该算一种思想,就是如果我可以根据现有的条件推断将来我一定完不成这个任务,那么就及时止损。形象点就是给算法加上一对预知未来的眼睛,具体有关A*算法设计可以看看我前面的文章A*算法
IDA*
如果说IDDFS算法还有可以优化的空间,我想结合A*算法一定是不二之选,所有搜索算法其实都有一个通病,就是搜索的盲目性,这也就是大部分搜索算法大家都习惯叫暴力法,如果结合A*算法使得搜索算法具有一定的目的性,那么将极大地摆脱“暴力”的标签。(由于A*算法其实是一种思想,所以没有具体的算法模板,需要大量的练习强化)。
Power Calculus
问题描述
问x经过最少经过到少次乘除运算可以到达x的n次方
输入
有多个测试每个测试输入一个整数n (1<=n<=1000)
输出
对于每个测试输出最小的步数
问题分析
两个幂函数相乘(除),指数相加(减),那么这个问题就可以简化为1经过多少次加减运算可以到达n。一开始我其实是想用动态规划计算的,因为后一个状态需要用到前一步的条件,然后打表,只用x,然后x平方,等等,但是我发现这个其实还有个除的过程,而且其实每一个子问题是用前一个子问题的解解决的,这不是动态规划,反而更像是分治法的思想,最后只好老老实实用分治做,其实dfs本质上也是个分治,怎么说呢,就是搜索到一个节点的路径可以由到与他有关系的节点的路径推得,而这两个问题又是两个独立的问题,好了扯远了,本题使用dfs算法
确实这题用dfs好像能过,但我们也可以想一想能不能玩出点花样来,用刚刚讲的IDA*算法
- 首先是IDDFS的核心——限制深度
if (now > depth) return false; //IDDFS剪枝
- 之后就是A*算法思想———预测
if (sum << (depth - now) < n) return false; //A_star算法剪枝
这个代码讲一下,首先这里使用了移位符号,相当于sum×2的(depth-now)次方,就是如果以sum增长最快的方式接近n都无法到达,那么说明这个深度不行,这个深度以上都没有答案,需要到更深的地方搜索答案
代码
#include<iostream>
using namespace std;int da[15]; //路径数组bool IDA_star(int n,int sum,int now,int depth) {if (now > depth) return false; //IDDFS剪枝 da[now] = sum; //记录深度为depth路径上各个点的信息if (sum << (depth - now) < n) return false; //A_star算法剪枝if (sum == n) return true; //找到答案结束for (int i = 1; i <= now;i++) {//代码中必须保证两个IDA_star都被执行,才可以保证所有情况都被搜索/*像这样的写法就是错的,它会导致程序在没找到答案之前提前终止,导致下面的IDA_star没办法执行(一开始我就是这样写的,结果输入31输出还是31)return IDA_star(n, sum + da[i], now + 1, depth);return IDA_star(n, sum - da[i], now + 1, depth);*///两种情概况if(IDA_star(n, sum + da[i], now + 1, depth)) return true;if(IDA_star(n, sum - da[i], now + 1, depth)) return true;}//最好还是在这里也return一下,保证程序的完整性return false;
}int main() {int n;while (~scanf_s("%d", &n) && n) {//逐渐增加深度for (int depth=1;; depth++) {if (IDA_star(n,1,1,depth)) {//注意这里的depth是从1开始的代表的是路径深度,及路径上节点个数,但是要输出路径长度需要数路径上的边,数值上等于节点数减一cout << depth-1 << endl;//打印路径代码/*for (int i = 1; i <= depth; i++) {cout << da[i] << " ";}*/break;}}}return 0;
}
大学生数学竞赛我能力还是不行,下次再战,说什么都要入一次决赛!
相关文章:

IDA*算法 Power Calculus————poj 3134
目录 闲聊 前言 DFS算法的无效搜索 BFS算法的空间浪费 IDDFS A*算法 IDA* Power Calculus 问题描述 输入 输出 问题分析 代码 闲聊 前几周在忙着数学竞赛,所以就没时间更新,高等数学,一生之敌,真不知道报名的时候我是怎么想…...

重磅!CoRL 2024顶刊会议 清华大学高阳研究组发布“基于大模型先验知识的强化学习”
正在德国举办的机器人研究领域的顶级学术会议CoRL 2024,清华大学交叉信息研究院高阳研究组发布重磅研究成果,提出“基于大模型先验知识的强化学习”框架(Reinforcement Learning with Foundation Priors) 来促进具身智能体在操作任务中的学习…...

泷羽sec学习打卡-Windows基础命令
声明 学习视频来自B站UP主 泷羽sec,如涉及侵权马上删除文章 笔记的只是方便各位师傅学习知识,以下网站只涉及学习内容,其他的都与本人无关,切莫逾越法律红线,否则后果自负 关于windows的那些事儿-Base 一、Windows-BaseWindows有哪些版本呢,有什么区别呢?…...
RTC精度及校准
RTC精度偏差: RTC的基准时间和精度与石英晶体的频率相关,晶体的谐振频率取决于温度,因此RTC性能与温度相关,晶体的频率偏差是晶体正常频率的温度反转函数。 一、硬件方面: 1.使用高精度振荡器的RTC模块; …...

jQuery案例
以下是几个常见的 jQuery 示例,展示了它在不同场景下的应用: 1. 隐藏和显示元素 通过按钮点击隐藏和显示一个 <div> 元素。 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><met…...

常见 HTTP 状态码分类和解释及服务端向前端返回响应时的最完整格式
目前开发的项目很大程度上是为明年的国产化做准备了,所以借这个机会把用了十年的自研系统全部重写,订立更严格的规范,本文记录一下返回格式及对应状态码。 常见 HTTP 状态码及解释 HTTP 状态码用于表示客户端请求的响应状态,它们…...

MySQL系列之如何在Linux只安装客户端
导览 前言Q:如何安装一个Linux环境下的MySQL客户端一、准备文件1. 确认Server版本2. 选择Client安装文件 二、下载并安装1. 下载1.1 寻找文件1.2 文件说明 2. 安装2.1 上传至Linux服务器2.2 执行安装 三、连接验证1. 确认远程授权2. 建立远程连接 结语精彩回放 前言…...

内核设备树,你真的了解吗?
在嵌入式系统和内核开发中,设备树(Device Tree, 简称 DT)扮演着至关重要的角色,帮助系统在启动时准确识别硬件配置并匹配合适的驱动程序。虽然设备树应用广泛,但其结构、工作机制及应用细节却不总是被深入理解。本文将…...

MySQL:客户端工具创建数据库
MySQL 是一个开源的关系型数据库管理系统(RDBMS),用于存储、管理和检索数据。MySQL是基于SQL语言的,它具有高效、可靠、易用的特点。 客户端工具 这个mysqld.exe就在计算机安装的数据可服务,启动之后,mys…...

Linux笔记之pandoc实现各种文档格式间的相互转换
Linux笔记之pandoc实现各种文档格式间的相互转换 code review! 文章目录 Linux笔记之pandoc实现各种文档格式间的相互转换1.安装 Pandoc2.Word转Markdown3.markdown转html4.Pandoc 支持的一些常见格式4.1.输入格式4.2.输出格式 1.安装 Pandoc sudo apt-get install pandoc # …...

【iOS】知乎日报第三周总结
【iOS】知乎日报第三周总结 文章目录 【iOS】知乎日报第三周总结前言评论区文字评论区的一个展开效果评论区数据的一个请求修改了主页获取数据的逻辑主页无限轮播图图片主色调的一个获取将一些拓展部分的内容写在分类里小结 前言 本周笔者因为金工实习整个项目进展比较慢&#…...

【p2p、分布式,区块链笔记 Torrent】WebTorrent的add和seed函数
在【p2p、分布式,区块链笔记 Torrent】WebTorrent的上传和下载界面的示例中,主要通过WebTorrent类的add和seed函数实现相关功能。这两个函数都返回一个Torrent类对象的实例。 seed函数 import createTorrent, { parseInput } from create-torrent // &…...

Redis穿透、击穿、雪崩
redis是一款常用的非关系型数据库,我们常用与作为数据缓存的组件。 接下来介绍一下面试中常被问到的三个概念以及简单的解决方法。 穿透 什么叫缓存穿透 缓冲穿透,是当有一个请求过来时,查询redis缓存不存在,又去查询数据库&…...

VBA高级应用30例应用3在Excel中的ListObject对象:插入行和列
《VBA高级应用30例》(版权10178985),是我推出的第十套教程,教程是专门针对高级学员在学习VBA过程中提高路途上的案例展开,这套教程案例与理论结合,紧贴“实战”,并做“战术总结”,以…...

2024系统架构师---上午综合题真题(重复考试知识难点)
1.感知层威胁 1)信息窃听:通过搭线或者电磁泄露造成数据隐私泄露;感知执行层主要由各种物理传感器组成,是整个物理信息系统中信息的来源。为了适应多变的环境,网络节点多布置在无人监管的环境中,因此容易被攻击者攻击,常见的针对感知执行层的攻击方式有; 2)感知破坏:…...

连接kafka消息队列报org.apache.kafka.clients.NetworkClient异常
启动kafka后,连接kafka消息队列报org.apache.kafka.clients.NetworkClient异常 could not be established. Broker may not be available. (org.apache.kafka.clients.NetworkClient) 检查kafka运行日志,报The broker is trying to join the wrong clu…...

淘宝商品评论API:代码界的“买家秀”大揭秘
在淘宝这个神奇的购物天堂里,商品评论就像是隐藏的宝藏,等待着我们去挖掘。想象一下,如果你的代码能够自动获取这些评论,那岂不是像拥有了一台时光机,可以穿梭在买家的购物体验之中?今天,我们就…...

RabbitMQ队列详细属性(重要)
RabbitMQ队列详细属性 1、队列的属性介绍1.1、Type:队列类型1.2、Name:队列名称1.3、Durability:声明队列是否持久化1.4、Auto delete: 是否自动删除1.5、Exclusive:1.6、Arguments:队列的其他属性…...

游戏服务器和普通服务器的区别
服务器,顾名思义,是提供服务的设备,在计算机领域,服务器是指具有网络功能的高性能计算机,用于存储、处理和传输数据,而游戏服务器则是专门为游戏提供服务的服务器,它需要具备更高的性能、更稳定…...

Java 中的 Supplier:让数据生成更灵活
文章目录 1. Supplier 基础:无参返回,懒加载的利器2. 与 Optional 配合,优雅地处理默认值3. 惰性初始化缓存:提升性能4. 用于随机数、时间戳等动态数据的生成5. 结合 Stream 实现动态数据流6. 与工厂模式结合,动态创建…...

轻松理解操作系统 - Linux的数据块是如何储存数据的?
python入门 C入门 Linux 由于其开源、比较稳定等特点统治了服务端领域。 也因此,学习Linux 系统相关知识在后端开发等岗位中变得越来越重要,甚至可以说是必不可少的。 因为它的广泛应用,所以在程序员的日常工作和面试中,它都是经…...

青藤深度参编的终端安全国家标准正式发布
近日,国家市场监督管理总局、国家标准化管理委员会发布中华人民共和国国家标准公告,由TC260(全国网络安全标准化技术委员会)归口,公安部第三研究所牵头的GB/T 29240-2024《网络安全技术 终端计算机通用安全技术规范》&…...

软考:去中心化的部署有什么特点
微服务架构被认为是去中心化的,因为它具有以下特点 模块化:微服务架构将应用程序拆分为一系列小型服务,每个服务都是独立的模块,易于维护和扩展 。这种模块化设计使得每个服务可以独立于其他服务运行,没有单一的控制中…...

L8.【LeetCode笔记】回文数
1.题目 https://leetcode.cn/problems/palindrome-number/description/ 给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。 回文数 是指正序(从左向右)和倒序(从右向左&…...

双版本android studio安装
安装双版本原因:不同的AS存在不兼容的情况,导致旧版本的项目在新项目下要各种修改,很讨厌,使用双版本,各使用各的就没有这样的问题了。 建议:先安装低版本安装版,再安装高版本免安装版…...

npm镜像的常用操作
查看当前配置的 npm 镜像 npm config get registry切换官方镜像 npm config set registry https://registry.npmjs.org/切换淘宝镜像(推荐) npm config set registry https://registry.npmmirror.com/切换腾讯云镜像 npm config set registry http://mirrors.cloud.tencent…...

Unity插件NodeCanvas之行为树的详细教程
文章目录 前言叶节点 Leafs1、行为 Action2、判断 Condition控制组件 Composites1、顺序执行器 Sequencer2、选择执行器 Selector3、概率选择执行器 Probability Selector4、权重选择执行器 Priority Selector5、平行执行器 Parallel6、轮流选择器 Flip Selector7、完整执行器 …...

Vue全栈开发旅游网项目(9)-用户登录/注册及主页页面开发
1.用户登录页面开发 1.查询vant组件 2.实现组件模板部分 3.模型层准备 4.数据上传 1.1 创建版权声明组件Copyright 新建文件:src\components\common\Copyright.vue <template><!-- 版权声明 --><div class"copyright">copyright xx…...

Flutter 的 Widget 概述与常用 Widgets 与鸿蒙 Next 的对比
一、Flutter 的 Widget 概述 Flutter 是 Google 开发的一款开源 UI 框架,旨在帮助开发者快速构建高性能、高保真度的移动、Web 和桌面应用程序。在 Flutter 中,UI 的构建完全是通过 Widget 来实现的。Widget 是 Flutter 中所有用户界面元素的基础构建块…...

微服务day04
网关 网关路由 快速入门 创建新模块:hm-gateway继承hmall父项目。 引入依赖:引入网关依赖和nacos负载均衡的依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"…...