算法·回溯

回溯和搜索的区别

   可以简单明确为回溯就是：搜索+剪枝优化

  回溯解决问题的数量级:10

回溯的应用：

• 分列问题：
  
• 组合问题：
  
• 剪枝优化：
  

回溯算法的套路

二维回溯

• 两个变量，按照两层for循环的情势搜索全部大概，注意换行。
  

1.         if(x>n){
2.                 return ;
3.         }
4.         int next_xx = y == n ? x + 1 : x;
5.         int next_yy = y == n ? 1 : y + 1;
6.         dfs(next_xx,next_yy,...);

复制代码

• P1784 数独：尺度的例题
  

(80分代码)

1. void dfs(int x, int y) {
2.         if (x > 9||y > 9) {
3.                 printsudo();
4.                 exit(0);
5.         }
7.         if (graph[x][y]) {
8.                 if (y == 9)dfs(x + 1, 1);
9.                 else dfs(x, y + 1);
10.                 return;//防止回溯后篡改(x,y)
11.         }
12.        
13.         for (int k = 1; k <= 9; k++) {
14.                 if (isvalid(x, y, k)) {
15.                         graph[x][y] = k;
16.                         if (y == 9)dfs(x + 1, 1);
17.                         else dfs(x, y + 1);
18.                         graph[x][y] = 0;
19.                 }
20.         }
21. }

复制代码

• P2040 打开全部的灯:这里要注意到一个灯不会被开两次。(即使不是同时开关两次)。
  

1. void dfs(int x, int y, int times) {
2.         if (isvalid()) {
3.                 ans = min(ans, times);
4.                 return;
5.         }
6.         if (x > n) {
7.                 return;
8.         }
9.         int next_xx = y == 3 ? x + 1 : x;
10.         int next_yy = y == 3 ? 1 : y + 1;
11.         dfs(next_xx, next_yy, times);//不点击
12.        
14.         graph[x][y] =graph[x][y]==0?1:0;//1->0,0->1
15.         for (int i = 0; i < 4; i++) {
16.                 int next_x = x + dir[i][0];
17.                 int next_y = y + dir[i][1];
18.                 if (next_x >= 1 && next_x <= n && next_y >= 1 && next_y <= n) {
19.                         graph[next_x][next_y]=graph[next_x][next_y] == 0 ? 1 : 0;
20.                 }
21.         }
22.         //cout << "x:" << x << " y:" << y << endl;
23.         //printout();
25.         dfs(next_xx, next_yy, times + 1);//点击
26.         graph[x][y] = graph[x][y] == 0 ? 1 : 0;//1->0,0->1
27.         for (int i = 0; i < 4; i++) {
28.                 int next_x = x + dir[i][0];
29.                 int next_y = y + dir[i][1];
30.                 if (next_x >= 1 && next_x <= n && next_y >= 1 && next_y <= n) {
31.                         graph[next_x][next_y] = graph[next_x][next_y] == 0 ? 1 : 0;
32.                 }
33.         }
34.        
36. }

复制代码

最后查抄

• 利用DFS遍历全部结果，对每个结果只在最后收集时查抄。
  
• 这个搜索次数过大，一样平常都会超时！
  
• P10386 [蓝桥杯 2024 省 A] 五子棋对弈：不设时间限定的题目，可以接纳这种思路。
  

前向查抄剪枝

• 前向查抄就是提前清除下一个埋伏状态中不公道的值，减少搜索范围。有的时候不需要isvalid()作最后的查抄！
  
• P9241 [蓝桥杯 2023 省 B] 飞机降落：前向查抄优化
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。