当前位置：首页 > news >正文

NO.73十六届蓝桥杯备战|搜索算法-剪枝与优化-记忆化搜索|数的划分|小猫爬山|斐波那契数|Function|天下第一|滑雪(C++)

news 来源：原创 2025/8/24 3:52:13

剪枝与优化

剪枝，形象得看，就是剪掉搜索树的分⽀，从⽽减⼩搜索树的规模，排除掉搜索树中没有必要的分⽀，优化时间复杂度。
在深度优先遍历中，有⼏种常⻅的剪枝⽅法

排除等效冗余
如果在搜索过程中，通过某⼀个节点往下的若⼲分⽀中，存在最终结果等效的分⽀，那么就只需要搜索其中⼀条分⽀。
可⾏性剪枝
如果在搜索过程中，发现有⼀条分⽀是⽆论如何都拿不到最终解，此时就可以放弃这个分⽀，转⽽搜索其它的分⽀。
最优性剪枝
在最优化的问题中，如果在搜索过程中，发现某⼀个分⽀已经超过当前已经搜索过的最优解，那么这个分⽀往后的搜索，必定不会拿到最优解。此时应该停⽌搜索，转⽽搜索其它情况。
优化搜索顺序
在有些搜索问题中，搜索顺序是不影响最终结果的，此时搜索顺序的不同会影响搜索树的规模。
因此，应当先选择⼀个搜索分⽀规模较⼩的搜索顺序，快速拿到⼀个最优解之后，⽤最优性剪枝剪掉别的分⽀。
记忆化搜索
记录每⼀个状态的搜索结果，当下⼀次搜索到这个状态时，直接找到之前记录过的搜索结果。
记忆化搜索，有时也叫动态规划

P1025 [NOIP 2001 提高组] 数的划分 - 洛谷

搜索策略：

将[1, n]个数放在k 个坑⾥⾯，使的坑⾥⾯的所有数的总和是n ；
其中，不同的坑⾥⾯的数可能相同；
但是[1,2]与[2,1]是同⼀种分法，因此，应该是⼀种组合型枚举。针对每⼀个坑⾥⾯的数应该放谁的时候，应该从上⼀个坑⾥⾯的数开始枚举。
剪枝策略：
当我们填了cnt个坑时，此时总和是sum，如果后续坑位全部都填上最⼩值都会超过n。说明我们之前填的数太⼤了，导致后⾯怎么填都会超过n，直接剪掉
如果在进⼊递归之前剪枝，我们不会进⼊⾮法的递归函数中；
但是如果在进⼊递归之后剪枝，我们就会多进⼊很多不合法的递归函数中

#include <bits/stdc++.h>
using namespace std;int n, k;
int path, ret;void dfs(int pos, int begin)
{if (pos == k){if (path == n) ret++; return;}//可行性剪枝//if (path + begin * (k-pos) > n) return;for (int i = begin; i <= n; i++){//可行性剪枝if (path + i * (k-pos) > n) return;path += i;dfs(pos+1, i);path -= i;}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> k;dfs(0, 1); //填的位置和开始的数cout << ret << endl;return 0;
}

P10483 小猫爬山 - 洛谷

搜索策略：依次处理每⼀只猫，对于每⼀只猫，我们都有两种处理⽅式：

要么把这只猫放在已经租好的缆⻋上；
要么重新租⼀个缆⻋，把这只猫放上去。
剪枝：
在搜索过程中，我们⽤全局变量记录已经搜索出来的最⼩缆⻋数量。如果当前搜索过程中，已经⽤的缆⻋数量⼤于全局记录的最⼩缆⻋数量，那么这个分⽀⼀定不会得到最优解，剪掉。
优化枚举顺序⼀：从⼤到⼩安排每⼀只猫
- 重量较⼤的猫能够快速把缆⻋填满，较快得到⼀个最⼩值；
- 通过这个最⼩值，能够提前把分⽀较⼤的情况提前剪掉。
优化枚举策略⼆：先考虑把⼩猫放在已有的缆⻋上，然后考虑重新租⼀辆⻋
- 因为如果反着来，我们会先把缆⻋较⼤的情况枚举出来，这样就起不到剪枝的效果了

#include <bits/stdc++.h>
using namespace std;const int N = 20;
int n, w;
int c[N];int cnt; //统计车的数量
int s[N]; //统计每一辆车目前的总重int ret = N;bool cmp(int a, int b)
{return a > b;
}void dfs(int pos)
{//最优性剪枝if (cnt >= ret) return;if (pos > n){ret = cnt;return;}//先安排在已有的车上for (int i = 1; i <= cnt; i++){//可行性剪枝if (s[i] + c[pos] > w) continue;s[i] += c[pos];dfs(pos+1);s[i] -= c[pos]; //恢复现场}//重开一辆cnt++;s[cnt] = c[pos];dfs(pos+1);//恢复现场s[cnt] = 0;cnt--;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> w;for (int i = 1; i <= n; i++) cin >> c[i];//优化搜索顺序sort(c+1, c+n+1, cmp);dfs(1);cout << ret << endl;return 0;
}

记忆化搜索

也是⼀种剪枝策略。
通过⼀个"备忘录"，记录第⼀次搜索到的结果，当下⼀次搜索到这个状态时，直接在"备忘录"⾥⾯找结果。
记忆化搜索，有时也叫动态规划

509. 斐波那契数 - 力扣（LeetCode）

在搜索的过程中，如果发现特别多完全相同的⼦问题，就可以添加⼀个备忘录，将搜索的结果放在备忘录中。下⼀次在搜索到这个状态时，直接在备忘录⾥⾯拿值
递归解法

class Solution {
public:int dfs(int n){if (n == 1 || n == 0) return n;return dfs(n-1) + dfs(n-2);}int fib(int n) {return dfs(n);}
};

记忆化搜索

class Solution {int f[35];
public:int dfs(int n){if (f[n] != -1) return f[n];if (n == 1 || n == 0) return n;f[n] = dfs(n-1) + dfs(n-2);return f[n];}int fib(int n) {memset(f, -1, sizeof f);return dfs(n);}
};

题⽬叙述的⾮常清楚，我们仅需按照「题⽬的要求」把「递归函数」写出来即可。但是，如果不做其余处理的话，结果会「超时」。因为我们递归的「深度」和「⼴度」都⾮常⼤。
通过把「递归展开图」画出来，我们发现，在递归过程中会遇到⼤量「⼀模⼀样」的问题
比如求w(20,20,20)
因此，可以在递归的过程中，把每次算出来的结果存在⼀张「备忘录」⾥⾯。等到下次递归进⼊「⼀模⼀样」的问题之后，就「不⽤傻乎乎的展开计算」，⽽是在「备忘录⾥⾯直接把结果拿出来」，起到⼤量剪枝的效果

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 25;LL a, b, c;
LL f[N][N][N]; //备忘录LL dfs(LL a, LL b, LL c)
{if (a <= 0 || b <= 0 || c <= 0) return 1;if (a > 20 || b > 20 || c > 20) return dfs(20, 20, 20);if (f[a][b][c]) return f[a][b][c];if (a < b && b < c) return f[a][b][c] = dfs(a, b, c-1) + dfs(a, b-1, c-1) - dfs(a, b-1, c);else return f[a][b][c] = dfs(a-1, b, c) + dfs(a-1, b-1, c) + dfs(a-1, b, c-1) - dfs(a-1, b-1, c-1);
}int main()
{ios::sync_with_stdio(false);cin.tie(0);while (cin >> a >> b >> c){//不需要清空if (a == -1 && b == -1 && c == -1) break;printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, dfs(a, b, c));}return 0;
}

P5635 【CSGRound1】天下第一 - 洛谷

⽤递归模拟整个游戏过程：dfs(x, y) 的结果可以由dfs((x + y) % p, (x + y + y) % p) 得到。
因为测试数据是多组的，并且模数都是p，再加上递归的过程中会递归的相同的问题，所以可以把递归改写成记忆化搜索。其中：

f[x][y] = 1 ，表⽰cbw 赢；
f[x][y] = 2 ，表⽰zhouwc 赢；
f[x][y] = 3 表⽰这个位置已经被访问过，如果没被修改成1 或者2 ，那就表明平局。
注意事项：
这道题的数据范围很⼤，⽤int类型创建⼆维数组空间会溢出。但是我们的最终结果仅有三种情况，所以可以⽤char类型来存储最终结果，节省空间

#include <bits/stdc++.h>
using namespace std;const int N = 1e4 + 10;
int x, y, p;
char f[N][N]; //备忘录char dfs(int x, int y)
{if (f[x][y]) return f[x][y]; //剪枝f[x][y] = '3'; //这个状态已经访问过了if (x == 0) return f[x][y] = '1';if (y == 0) return f[x][y] = '2';return f[x][y] = dfs((x+y)%p, (x+y+y)%p);
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int T; cin >> T >> p;while (T--){cin >> x >> y;char ret = dfs(x, y);if (ret == '1') cout << 1 << endl;else if (ret == '2') cout << 2 << endl;else cout << "error" << endl;}return 0;
}

P1434 [SHOI2002] 滑雪 - 洛谷

暴⼒枚举：遍历整个矩阵，看看以当前位置为起点，最远能滑⾏多远的距离。在所有情况⾥⾯，取最⼤值即可。
如何求出以[i, j]为起点的最⼤距离？

从[i,y]位置上下左右瞅⼀瞅，如果能滑过去，就看看以下⼀个位置为起点，最远能滑⾏多远的距离；
找出四个⽅向上的最远距离，然后+1 。
因为出现相同⼦问题，所以可以⽤dfs来解决。⼜因为在搜索的过程中会遇到⼀模⼀样的问题，因此可以把递归改成记忆化搜索的⽅式

#include <bits/stdc++.h>
using namespace std;const int N = 110;int n, m;
int a[N][N];
int f[N][N]; //备忘录int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};int dfs(int i, int j)
{if (f[i][j]) return f[i][j];int len = 1;//上下左右找for (int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if (x < 1 || x > n || y < 1 || y > m) continue;if (a[i][j] <= a[x][y]) continue;len = max(dfs(x, y)+1, len);}return f[i][j] = len;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> a[i][j];int ret = 1;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)ret = max(ret, dfs(i, j));cout << ret << endl;return 0;
}

剪枝与优化

记忆化搜索

相关文章：