开个专题记录自己搜索的学习过程，对于这种搜索的不同思想我只能说前人的肩膀太过于厚实。
1.BFS
摘用OI Wiki的一段话
BFS（Breadth First Searth）为图论中的基础算法，在搜索算法中该算法通常指利用队列结构逐层扩展状态的搜索方式。与图论中的 BFS 算法思想一致特别适合求解最短路径或最少步骤类问题。
人话就是，类似于向水里扔一块石头，波纹一圈圈向外扩散，先到达离中心最近的点，同一圈波纹上的点同时到达而且找到的路径一定是最短的
1. 洛谷P1443 马的遍历
题目：有一个 n×m 的棋盘，在某个点 (x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。输入只有一行四个整数，分别为 n,m,x,y。一个 n×m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 −1）。
唯一要说的：会bfs，以及知道马走日
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int dx[8]={2,2,-2,-2,1,1,-1,-1};
const int dy[8]={1,-1,1,-1,2,-2,2,-2};
int main(){
int n,m,x,y;
cin>>n>>m>>x>>y;
x--;
y--;
vector<vector<int>> dist(n,vector<int>(m,-1));
queue<pair<int,int>> q;
dist[x][y]=0;
q.push({x,y});
while(!q.empty()){
auto[cx,cy]=q.front();
q.pop();
int step=dist[cx][cy];
for (int i = 0; i < 8; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1) {
dist[nx][ny] = step + 1;
q.push({nx, ny});
}
}
}
for (int i=0;i<n;i++) {
for (int j= 0;j<m;j++) {
cout<<dist[i][j];
if (j <m-1) cout << " ";
}
cout << endl;
}
return 0;
}
|
2. P1135 奇怪的电梯
题目：大楼的每一层楼都可以停电梯，而且第 i 层楼（1≤i≤N）上有一个数字Ki。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： 3,3,1,2,5 代表了 Ki，从 1 楼开始。在 1 楼，按“上”可以到 4 楼，按“下”是不起作用的，因为没有 −2 楼。那么，从 A 楼到 B 楼至少要按几次按钮呢？
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(){
int n,a,b;
cin>>n>>a>>b;
vector<int> k(n+1);
for(int i=1;i<=n;i++){
cin>>k[i];
}
if(a==b){
cout<<0<<endl;
return 0;
}
vector<bool> visited(n+1,false);
vector<int> step(n+1,0);
queue<int> q;
q.push(a);
visited[a]=true;
step[a]=0;
while(!q.empty()){
int cur=q.front();
q.pop();
int up=cur+k[cur];
if(up <= n && !visited[up]){
visited[up]=true;
step[up]=step[cur]+1;
if(up==b){
cout<<step[up]<<endl;
return 0;
}
q.push(up);
}
int down = cur - k[cur];
if (down >= 1 && !visited[down]) {
visited[down] = true;
step[down] = step[cur] + 1;
if (down == b) {
cout << step[down] << endl;
return 0;
}
q.push(down);
}
}
cout << -1 << endl;
return 0;
}
|
有个疑惑的点就是为什么要标记每一个楼层的访问情况，万一路径就是重叠某个楼层的呢？
事实证明这个担心不存在
BFS中，包含重复访问楼层的路径一定不是最短路径。任何包含环的路径都可以去掉环而得到更短的路径！
小结论
- 在BFS中，第一次访问某个状态时的步数就是最短步数
- 后续再访问这个状态，步数不会更少
- 包含重复状态的路径一定不是最短路径
- 标记visited就是利用了这个性质
2.回溯
**什么是回溯？**回溯算法是一种通过试探和回退来搜索所有可能解的算法，它本质上是DFS的一种运用（深以为然），但是搜索过程中会通过“剪枝”来避免无效搜索
核心思想：试错与回溯
试探：从初始状态开始，一步步构建可能的解
验证：检查当前部分解是否满足约束条件
回溯：当发现当前路径不可能得到有效解时，撤销最近的选择，返回上一步尝试其他选项
1. 洛谷P1219 [USACO1.5] 八皇后 Checker Challenge
题目：一个 6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。举个例子，布局可以用序列 2 4 6 1 3 5 来描述，第 i 个数字表示在第 i 行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 3 个解。最后一行是解的总个数。
太坏了太坏了，N皇后问题的变种，约束性更强了竟然要求对角线平行的斜线也不能有棋子啊啊啊啊啊啊，never mind ，实际上，标准的 N 皇后问题就是这样的：不允许多个皇后在同一条斜率为 ±1 的线上。嗯。
所以这就是 N 皇后问题，只是输入输出格式特别。
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> cols;
vector<bool> col_used;
vector<bool> diag1_used;
vector<bool> diag2_used;
int cnt=0;
vector<vector<int>> first_3;
void dfs(int row){
if(row==n+1){
cnt++;
if(cnt<=3){
first_3.push_back(cols);
}
return;
}
for(int col=1;col<=n;col++){
if(!col_used[col] && !diag1_used[row-col+n] && !diag2_used[row+col]){
cols[row-1]=col;
col_used[col]=true;
diag1_used[row-col+n]=true;
diag2_used[row+col]=true;
dfs(row+1);
col_used[col]=false;
diag1_used[row-col+n]=false;
diag2_used[row+col]=false;
}
}
}
int main(){
cin>>n;
cols.resize(n);
col_used.resize(n+1,false);
diag1_used.resize(2*n-1,false);
diag2_used.resize(2*n-1,false);
dfs(1);
for(int i=0;i<first_3.size();i++){
for(int j=0;j<n;j++){
cout<<first_3[i][j]<<" ";
}
cout<<endl;
}
cout<<cnt<<endl;
return 0;
}
|
补充
- 字典序：因为我们按照从上到下递归，并且列数也是，得到的解自然就是字典序
- 对角线标记：
主对角线(row-col+n),因为row-col为常数但是避免负数，所以加n
副对角线(row+col)为常数
- 理解回溯是什么(类似于迷宫)
你往前走一步，做个标记
如果发现前面是死路，就退回上一步，擦掉标记
尝试另一条路
在 N 皇后问题中：
我们在第 1 行放一个皇后，标记占用的列和对角线
然后在第 2 行找能放的位置
如果第 2 行找不到能放的位置，说明第 1 行的选择不对
我们就撤销第 1 行的选择，尝试第 1 行的下一个位置
- 为什么需要回溯
假设我们正在尝试row=2,col=2：
我们先标记：col_used[2]=true, 对角线标记为 true
然后递归dfs(3)去尝试第 3 行
当dfs(3)返回时（无论成功找到解还是失败）
我们必须撤销刚才的标记，因为：
如果找到解：要继续找下一个解（不能总占着 col=2）（顿时想到自习室不把书拿走的人
如果没找到解：要尝试 row=2, col=3 等其他位置
3.子集枚举
1.洛谷P2036[COCI 2008/2009 #2] PERKET
题目：你有 n 种可支配的配料。对于每一种配料，我们知道它们各自的酸度 s 和苦度 b。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的苦度为每一种配料的苦度的总和。
众所周知，美食应该做到口感适中，所以我们希望选取配料，以使得酸度和苦度的绝对差最小。
另外，我们必须添加至少一种配料，因为没有任何食物是只以水为配料的。
先把代码实现扔上来
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
| #include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
int main(){
int n;
cin>>n;
vector<pair<int,int>> add(n);
for(int i=0;i<n;i++){
cin>>add[i].first>>add[i].second;
}
ll min_diff=1e18;
for(int i=1;i<(1<<n);i++){
ll sour=1;
ll bitter=0;
for(int j=0;j<n;j++){
if(i&(1<<j)){
sour*=add[j].first;
bitter+=add[j].second;
}
}
ll diff=abs(sour-bitter);
min_diff=min(diff,min_diff);
}
cout<<min_diff<<endl;
return 0;
}
|
分析
- 老生常谈的位运算
1 << n：计算 2ⁿ，左移运算
i & (1 << j)：检查第 i 位是否为 1（与运算）
i >> j & 1：另一种检查方式（右移后与运算）
因为一共有n种材料，也就是会有2^n个子集，而通过位运算就能列出来每一种子集的情况
- 暴力枚举/穷举搜索：
由于 n 最大只有 10（2¹⁰=1024 种可能），所以可以直接枚举所有情况（虽然这并不优雅
当然也可以用之前提及的递归回溯来实现
基本思路：
我们考虑每种配料有两种选择：
选：酸度乘以这种配料的酸度，苦度加上这种配料的苦度
不选：跳过这种配料
递归遍历所有配料，在每一步决定是否选择当前配料。
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
38
39
40
41
42
| #include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
ll min_diff=1e18;
int n;
vector<pair<int,int>> add;
void dfs(int idx,ll sour,ll bitter,bool selected){
if(idx==n){
if(selected){
ll diff=abs(sour-bitter);
min_diff=min(diff,min_diff);
}
return;
}
dfs(idx+1,sour,bitter,selected);
dfs(idx+1,sour*add[idx].first,bitter+add[idx].second,true);
}
int main(){
cin>>n;
add.resize(n);
for(int i=0;i<n;i++){
cin>>add[i].first>>add[i].second;
}
dfs(0,1,0,false);
cout<<min_diff<<endl;
return 0;
}
|
