正文

搜索分析（dfsbfs递归记忆化搜索）

范仁义  范仁义  2022-09-17  437

关键词：

搜索分析（DFS、BFS、递归、记忆化搜索）

1、线性查找

在数组a[]={0,1,2,3,4,5,6,7,8,9,10}中查找1这个元素。

（1）普通搜索方法，一个循环从0到10搜索，这里略。

（2）递归（从中间向两边）

 1 //递归一定要写成记忆化递归 
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 bool vis[11];
 5 int count1=0;
 6 
 7 void search(int n){
 8     count1++;
 9     if(n>10||n<0||vis[n]){
10         //cout<<"back"<<endl;
11     }
12     else if(n==1){
13         vis[n]=true;
14         cout<<"find"<<endl;
15     } 
16     else {
17         vis[n]=true;
18         search(n-1);
19         search(n+1);
20         
21     }
22 }
23 
24 int main(){
25     int a[]={0,1,2,3,4,5,6,7,8,9,10};
26     search(9);
27     cout<<count1<<endl;
28     return 0;
29 
30 }

递归(从中间到两边)

这种方法一定要加标记数组，不然会出现死循环。

其中一个死循环：

search(9)->search(8)->search(9)

而这样的死循环太多了。

其实分析的时候直接把递归的树形图画出来就好了，直观而且方便。

这样带有标记数组的递归，本质上就是记忆化递归。

所以这种环形的递归都可以写成记忆化递归。

（3）递归（从后面向前面）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int count1=0;
 5 
 6 void search(int n){
 7     count1++;
 8     if(n>10||n<0){
 9     }
10     else if(n==1){
11         cout<<"find"<<endl;
12     } 
13     else {
14         search(n-1);        
15     }
16 }
17 
18 int main(){
19     int a[]={0,1,2,3,4,5,6,7,8,9,10};
20     search(10);
21     cout<<count1<<endl;
22     return 0;
23 
24 }

递归(从后面向前面)

这种方法是不需要标记数组的，因为递归是线性的，而不是环形的，递归之间没有交叉，不会造成重复访问。

这种和求阶乘的是一样的。

（4）BFS（从中间向两边）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 bool vis[11];
 4 int count1=0;
 5 queue<int> que;
 6 
 7 void searchBFS(int n){
 8     que.push(n);
 9     while(!que.empty()){
10         count1++;
11         cout<<"count1:"<<count1<<endl;
12         
13         int tmp=que.front();
14         que.pop();
15         vis[tmp]=true; 
16         cout<<"tmp:"<<tmp<<endl;
17         if(tmp==1) {
18             cout<<"find"<<endl;
19             return ;
20         }
21         else{
22             if(tmp-1>=0&&!vis[tmp-1]) que.push(tmp-1);
23             if(tmp+1<=10&&!vis[tmp+1]) que.push(tmp+1); 
24         }
25     }
26 }
27 
28 int main(){
29     int a[]={0,1,2,3,4,5,6,7,8,9,10};
30     searchBFS(9);
31     cout<<count1<<endl;
32     return 0;
33 
34 }

BFS（从中间向两边）

这种BFS也是一定要带标记数组的，所以也可以写成记忆化。

这种BFS如果不带标记数组的话，也是可以得到正确答案的，不过会重复算很多算过的东西。

例如：9 8 10 7 9 9 6 8 8 10 8 10 .........

比如说上面的9就访问了很多次，而由于队列FIFO的特性，所以虽然重复算很多次，还是会得到正确答案。

因为7、6那一支会逐渐到1的。

当然，BFS也可以直接写成线性的，这样也是不需要标记数组的。

其实还是那样，把情况的树形图画出来就很舒服了，直观方便。

二、阶乘

（1）普通求阶乘方法：略。

（2）阶乘的递归实现DFS

阶乘的递归实现

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int jiechen(int n){
 4     if(n==1) return 1;
 5     else{
 6         return n*jiechen(n-1);
 7     }
 8 }
 9 int main(){
10     cout<<jiechen(8)<<endl;
11     return 0;
12 }

DFS

从尾直接算到头，不需要标记数组

（2）阶乘的栈实现

 1 /*
 2 伪码：
 3 我们求f(n)，f(n)入栈
 4 在栈不空的情况下(下面循环)
 5 出栈 
 6 f(n)=f(n-1)*n
 7 如果f(n-1)没有被求出来，直接入栈 
 8 */
 9 
10 //对数组而言，我们操作的肯定是下标，而一定不是数组元素的值 
11 #include <bits/stdc++.h>
12 using namespace std;
13 stack<int> sta; 
14 int a[15];
15 
16 int jiechen(int n){
17     a[1]=1;
18     sta.push(n);
19     while(!sta.empty()){
20         int tmp=sta.top();
21         sta.pop();
22         //如果a[tmp-1]被计算了 
23         if(a[tmp-1]!=0){
24             a[tmp]=a[tmp-1]*tmp;
25             cout<<tmp<<" "<<a[tmp]<<endl;
26         } 
27         else{
28             sta.push(tmp);
29             sta.push(tmp-1);
30         } 
31     }
32     return a[8];
33 }
34 
35 int main(){
36     cout<<jiechen(8)<<endl;
37     return 0;
38 }

阶乘的栈实现

对数组而言，我们操作（存储进栈或者队列或者其它操作）的肯定是下标，而一定不是数组元素的值

其实栈实现和递归实现是一样的，因为递归在计算机内部就是用栈实现的。

记忆化搜索||poj1088滑雪

...比它小的数那里走，问最远长度是多少*解法：每一点dfs搜索一遍记忆化搜索：http://blog.csdn.net/acmer_sly/article/details/53440798递归：求解的方法都是相同的（距离是周围的点最大值加一），假设已知周围点的距离则dd[i]=dfs(xx,yy)+1; ... 查看详情

数字三角形记忆化搜索与递归

7 38 810 2744 45265在上面的数字三角形中寻找在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出... 查看详情

动态规划-记忆化搜索

1.数字三角形学习链接：http://blog.csdn.net/zwhlxl/article/details/46225947输入样例：5738810274445265输出样例：30递归代码：#include<stdio.h>#include<memory.h>#include<math.h>#include<string>#include< 查看详情

[专题练习]part1搜索

一.DFS(深度优先搜索)过于水略过。二.BFS(广度优先搜索)同上。三.记忆化记忆化搜索，就是我们的状态会重复利用，为了防止状态的重复计算耗费不必要的时间，我们可以把这个状态的结果记录下来，然后查询表中的结果就行了... 查看详情

洛谷p1464function动态规划（递推）/记忆化搜索（递归）

题目描述对于一个递归函数w(a,b,c)如果a<=0orb<=0orc<=0就返回值1.如果a>20orb>20orc>20就返回w(20,20,20)如果a<b并且b<c就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)其它别的情况就返回w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b 查看详情

记忆化搜索

记忆化搜素是DP的一种形式记忆化搜素是DP的一种形式查看详情

hdu1078fatmouseandcheese记忆化搜索(代码片段)

...所能得到的最多奶酪数。解题分析：这题很明显要用搜索做，但是在搜索的过程中，我们应该加入dp的思想，即记忆化搜索，对于已经搜索过的点，我们就可以不用重复搜索了，直接调用它的值就行。# 查看详情

poj1191棋盘切割（压缩dp+记忆化搜索）

一，题意：中文题二。分析：主要利用压缩dp与记忆化搜索思想三，代码：#include<iostream>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>usingnamespacestd;constintBig=20000000;intMat[10] 查看详情

function——记忆化搜索

反转链表(递归链表)爬楼梯(记忆化搜索数学)旋转数组(数组数学)(代码片段)

...tmp=head.next;head.next=pre;pre=head;head=tmp;returnpre;爬楼梯(记忆化搜索、数学)假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？**注意：**给定n是一个正整数。示例1：输入... 查看详情

openj_bailian-1088滑雪（记忆化搜索）

...行的最长区域的长度。分析：对于每一个点，进行记忆化搜索。若某点可以向四周某几个点滑行，记忆化搜索求出这几个可滑行点的最长滑行长度，取最大值，则该点的最长滑行长度为最大值+1.注意：不能直接dp[x][y]=max(dp[x][y],df... 查看详情

斐波那契数列的记忆搜索(代码片段)

...列求值“这个经典问题，分析并说明“从单一递归到记忆搜索”这个思想过程。本blog是整个动态规划学习的一部分。（记忆搜索是动态规划的递归写法）斐波那契数列斐波那契数列（Fibonaccisequence），又称黄金分割数列、因数学... 查看详情

leetcode编程总结

...表归并排序的递归过程，要好好体会一下#6、树型的暴力搜索（全路径搜索、DFS）需要进行回溯参见LeetCode93#7、利用return能使树型递归提早结束，类似于DFS参见LeetCode37#8、记忆化搜索，自上而下的解决问题、动态规划，自下而上... 查看详情

记忆化搜索(代码片段)

记忆化搜索什么是记忆化搜索？百度百科：算法上依然是搜索的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存。个人理解：就是每求到一个状态就保存下来，下次再遇到这个状态直接调用即可它有什么好处... 查看详情

wenbao与记忆化搜索(代码片段)

记忆化搜索：通俗地讲就是搜索的形式，dp的思想一些搜索难以完成，dp的动态转移方程又不好写的题，就会用到记忆化搜索，利用dp记录路径（相当于为dfs剪枝）用dfs进行模拟。。啦啦啦啦啦啦，，，，，，，，，好厉害！... 查看详情

coj1686：记忆化搜索

看了N遍才看懂题意。。。题意：给N个区间，每次能向左或向右走区间长度这么多，问能不能每次都在[0,m]这个范围内思路：爆搜是不行的。。这里把状态记录一下能剪枝很多定义:s[pos][now]=-1 查看详情

hdu-6143killernames（dp记忆化搜索+组合数）

...长度为n的姓-----可转换成用i种颜色给n个球染色，记忆化搜索dfs(n,i)---用i种颜色给n个球染色的方案数先给第1个小球涂色，有m种选择，假设涂色为color[1]，那么剩下n-1个小球：如果继续使用col 查看详情

记忆化搜索游荡的奶牛

[luogu1535]游荡的奶牛题目描述Searchingfortheverybestgrass,thecowsaretravellingaboutthepasturewhichisrepresentedasagridwithNrowsandMcolumns(2<=N<=100;2<=M<=100).KeenobserverFarmerJohnhasrecordedBess 查看详情