2025年广度优先搜索c++语言（广度优先搜索怎么遍历）

科技前沿 • 2025-06-09 11:12 • 阅读 42

大家好，我是讯享网，很高兴认识大家。

记忆化搜索，可能没听说过，但其实在搜索与回溯和广度优先搜索中就已经用到了，例如其中的

或

就是通过记忆点 ( nx , ny ) 或 ( x , y ) 是否走过来避免重复到达一个点，因为一个点如果被走过了，再走一次也是有着相同的结果，如果要重复走一个点的话就会导致多次查询从而超时，所以，记忆化搜索就是将已经遍历过的信息保存起来，以避免重复遍历增加程序花费的时间 ( 大概意思就是用空间换时间 )

例如在递推 & 递归中讲到的使用递归求解斐波那契数列的第 n 项的值，当时写的代码是这样的

对于 n = 5 来说，它需要往下求出 Fibonacii ( 4 ) 和 Fibonacii ( 3 ) 的值，而 Fibonacii ( 4 ) 又要求 Fibonacii ( 3 ) 和 Fibonacii ( 2 ) 的值，当求出 Fibonacii ( 3 ) 后，事实上我们已经知道了 Fibonacii ( 3 ) 为 2，但是在第一步却要再求一次 Fibonacii ( 3 )，就是相当于多做了一次，当然在这里不是很明显，如果 n = 50，n = 100 呢，就会导致巨量的重复计算，从而让计算机也算不过来

所以，对于那些已经计算过的数，就可以将它记下来，方便下一次的计算，例如在第一次计算 Fibonacii ( 3 ) 时，可以将 Fibonacii ( 3 ) 的值记录在数组中，在下一次使用到 Fibonacii ( 3 ) 就不用再重新计算一次了，直接 O( 1 ) 查找数组中对应位置的数值即可

讯享网

所以记忆化搜索最重要的就是记忆历史信息，为后面的计算做好铺垫，通过记忆化搜索优化的代码如下

记忆化搜索大大提高了程序执行的效率，未优化的代码在执行 n = 40 时就已经用了很长时间了，但是通过优化过后即使是 n = 100 也能够瞬间输出答案 ( 虽然炸 int 了，改成 long long 就行了 )

搜索是一个非常实用的算法 ( 虽然优化不好铁锭得炸 )，在比赛中是一个非常实用的骗分得分技巧，有些题甚至可以用极致的优化得到不少的分，所以，学习搜索的优化方法是十分有用的

感觉这期有点氵，所以把压箱底的快读取了出来

所谓快读，就是比 scanf 还快上亿倍的读入方式，适用于遇到数据量无比巨大的题，遇到需要卡常的题或只是想装杯的时候

快读的原理就是通过 getchar 飞快的速度来读入字符，再转换为数字并返回

num 左移一位加 num 左移三位就等于 num*10，即

而 c^48 就等于 c-48，使用位运算相比于直接使用加减乘除要快

马上就要进行 SCP2022 的初赛了，所以我在这里祝每位参加的选手都能取得一个好的成绩！( 所以这次才讲记忆化搜索以及快读 )

好了那么如果你觉得本篇文章对你有所帮助的话请不要忘记支持！

2025年广度优先搜索c++语言（广度优先搜索怎么遍历）

相关推荐