算法·回溯
回溯和搜索的区别可以简单明确为回溯就是：搜索+剪枝优化
回溯解决问题的数量级:10
回溯的应用：
[*]分列问题：
[*]组合问题：
[*]剪枝优化：
回溯算法的套路
二维回溯
[*]两个变量，按照两层for循环的情势搜索全部大概，注意换行。
if(x>n){
return ;
}
int next_xx = y == n ? x + 1 : x;
int next_yy = y == n ? 1 : y + 1;
dfs(next_xx,next_yy,...);
[*]P1784 数独：尺度的例题
(80分代码)
void dfs(int x, int y) {
if (x > 9||y > 9) {
printsudo();
exit(0);
}
if (graph) {
if (y == 9)dfs(x + 1, 1);
else dfs(x, y + 1);
return;//防止回溯后篡改(x,y)
}
for (int k = 1; k <= 9; k++) {
if (isvalid(x, y, k)) {
graph = k;
if (y == 9)dfs(x + 1, 1);
else dfs(x, y + 1);
graph = 0;
}
}
}
[*]P2040 打开全部的灯:这里要注意到一个灯不会被开两次。(即使不是同时开关两次)。
void dfs(int x, int y, int times) {
if (isvalid()) {
ans = min(ans, times);
return;
}
if (x > n) {
return;
}
int next_xx = y == 3 ? x + 1 : x;
int next_yy = y == 3 ? 1 : y + 1;
dfs(next_xx, next_yy, times);//不点击
graph =graph==0?1:0;//1->0,0->1
for (int i = 0; i < 4; i++) {
int next_x = x + dir;
int next_y = y + dir;
if (next_x >= 1 && next_x <= n && next_y >= 1 && next_y <= n) {
graph=graph == 0 ? 1 : 0;
}
}
//cout << "x:" << x << " y:" << y << endl;
//printout();
dfs(next_xx, next_yy, times + 1);//点击
graph = graph == 0 ? 1 : 0;//1->0,0->1
for (int i = 0; i < 4; i++) {
int next_x = x + dir;
int next_y = y + dir;
if (next_x >= 1 && next_x <= n && next_y >= 1 && next_y <= n) {
graph = graph == 0 ? 1 : 0;
}
}
}
最后查抄
[*]利用DFS遍历全部结果，对每个结果只在最后收集时查抄。
[*]这个搜索次数过大，一样平常都会超时！
[*]P10386 [蓝桥杯 2024 省 A] 五子棋对弈：不设时间限定的题目，可以接纳这种思路。
前向查抄剪枝
[*]前向查抄就是提前清除下一个埋伏状态中不公道的值，减少搜索范围。有的时候不需要isvalid()作最后的查抄！
[*]P9241 [蓝桥杯 2023 省 B] 飞机降落：前向查抄优化
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]