读书报告《啊哈!算法!》第4章

如题,这是一篇读书报告》.《

首先,我了解到深搜和广搜两种算法,有什么不同之处呢?

深搜

从某条路一直走到底撞到边界条件再回头,尝试其他可能

有道题目:

P1036

通过深搜实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;
int a[10001];
int n,k,sum,total;
inline void print()
{
printf("%d",total);
}
inline bool prime(int x)
{
for(register int i=2; i<=sqrt(x); i++)
if(x%i==0)
return false;
return true;
}
inline void dfs(int step,int sum,int cnt)
{
if(step==n+1||cnt==k)
{
if(prime(sum) && cnt==k)
total++;
return;
}
dfs(step+1,sum+a[step],cnt+1);
dfs(step+1,sum,cnt);
return;
}
int main()
{
scanf("%d %d",&n,&k);
for(register int i=1; i<=n; i++)
scanf("%d",&a[i]);
dfs(1,0,0);
print();
return 0;
}

上题中即使用了深搜
总结:深搜重要之处在于边界条件 十分重要~~!!!

不然会死循环或者浪费时间等一大堆事

广搜:层层递进

对<(^-^)>特点就是层层递进

在走迷宫这道题目中 广搜就像这样↓

5cfd0e2dd55ed14327

层层递进

5cfd0e7c38a6860476

使用两个坐标的队列以及一个step的队列记录,同时在每个节点进行扩展

总结:好好利用搜索可以解决很多循环无法解决的问题,但边界条件要设置好,以及每次调用函数时的数据要对应。

-------------本文结束,感谢您的阅读-------------