C++大神必知的搜索秘籍——DAY3

搜索，作为在座的每一位C++编程大神们，想必都不陌生，搜索是我们进入算法阶段的敲门砖，是我们在面对难题却依旧可以得部分分的自信，从本质上来说，在不考虑数值范围的情况下，搜索可以解决目前我们所学阶段的大部分题目，也就是我们所说的暴力。搜索优点很多，缺点也非常致命——空间利用率低，时间利用率低，极容易爆空间和时间，因此优化搜索的效率，可以使我们在找不到或写不出正确算法时拿到尽可能多的分——下面就让我们一起来学习搜索的剪枝与优化。

DFS的优化和剪枝

DFS在搜索时会一条路走到黑，不撞南墙不回头，最终会形成一棵搜索树，在搜索过程中，DFS会搜索到大量无用的信息，因此让DFS尽可能减少对无用信息的搜索成为了首要任务。深度优先搜索的剪枝在效果上大致分为以下几种：

优化搜索顺序：在一些搜索问题中，搜索树的各个层次,各个分支之间的顺序都是不固定的，不同的搜索顺序会产生不同的搜索树，其搜索规模大小也大大不同。
排除等效冗余：在搜索过程中，如果我们能够判定从搜索树的当前节点上沿着某几条不同分支到达的子树是等效的，那么只需要对其中的一条分支执行搜索。
可行性剪枝:在搜索过程中，及时对当前状态进行检查，如果发现分支已经无法到达递归边界，就执行回溯。这就好比我们在道路上行走时，远远看到前方是一个死胡同，就应该立即折返绕路，而不是走到路的尽头再返回。
记忆化：可以记录每个状态的搜索结果，在重复遍历一个状态时直接检索并返回。这就好比我们对图进行深度优先遍历时，标记一个节点是否已经被访问过。再拿胡同来说，当我之前就在这里发现了死胡同，那么当我下次再走到这个分岔路口时，我的大脑里已经有了对这条路的记忆，因此不必再往下走。

下面我们来看DFS的搜索与剪枝在真正赛场上的题上是如何应用的：

题目描述

原题来自：CERC 1995

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 5050 。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

输入格式

第一行为一个单独的整数N 表示砍过以后的小木棍的总数。第二行为N 个用空格隔开的正整数，表示N 根小木棍的长度。

输出格式

输出仅一行，表示要求的原始木棍的最小可能长度。

输入数据 1
9
5 2 1 5 2 1 5 2 1
Copy

输出数据 1
6
Copy

数据范围与提示

1≤N≤60

看完这道题，相信聪明的你一定有一个暴力DFS的搜索方法，首先，原始木块的长度一定为这些小木棍长度总和的倍数，且一定比这些小木棍中最长的那部分要长，只要符合上述的这些条件，就让DFS进行不断拼接组装，最终完成，则输出，否则，就继续向下搜索；

但当我们这样写后，会发现结果T掉了，当我们细细搜索就会发现，DFS跑到了太多无用的组合，再加之DFS“不撞南墙不回头的特性”，最终导致结果超时，因此本题要进行很多的剪枝。具体剪枝听我下面分析：

如果在枚举第一个木棍时就因为太长而不成立，那么下面的这个长度也没必要在枚举下去，直接return false;
为了保证，枚举的次数尽可能的小，我们要在开始尽可能选取长度较大的木棍，因此应让木棍的长度从大到小进行DFS枚举；
如果说当前小木棍的长度+已有的长度正好等于当前枚举的总长度，但这种组合却在后面的递归中被pass掉了，那么再往下选取长度更小的木棍也没有任何作用，也可以直接return false
除此之外我们还可以通过记忆化的方法进行进一步优化，在这里不再赘述

具体代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=665;
int n,a[N],maxx=0,sum=0,op=0,kk;
bool vis[N];
bool dfs(int cnt,int cd,int la){
	if(cnt==op)  return true;
	if(cd==kk)  return dfs(cnt+1,0,1); 
	int fail=0;
	for(int i=la;i<=n;i++){
		if(!vis[i]&&a[i]+cd<=kk&&a[i]!=fail){
			vis[i]=1;
			if(!dfs(cnt,cd+a[i],i+1)){
				vis[i]=0;
				fail=a[i];
				if(cd==0||cd+a[i]==kk)  return false;
			}else{
				return true;
			}
		}
	}
	return false;
}
bool cmp(int x,int y){
	return x>y;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		maxx=max(maxx,a[i]);
		sum+=a[i];
	}
	sort(a+1,a+n+1,cmp);
	for(int i=maxx;i<=sum;i++){
		if(sum%i==0){
			op=sum/i;
			kk=i;
			if(dfs(0,0,1)){
				printf("%d",i);
				return 0;
			}
		}
	}
	return 0;
}

看完这道题，你会发现剪枝是非常巧妙的，优雅而不失美感，但只是在思考过程中需要对DFS的搜索过程有一个深入的理解。

BFS（广度优先搜索）的优化技巧

BFS在本质上也是对DFS的优化，只不过BFS是在思想上对DFS的优化，它不像DFS一条路走到黑，而是像信号发射一样，齐头并进，在搜索中要对深度优先搜索快出不少，但对BFS的搜索也有一定的优化方法。

双向BFS

双端BFS从起点和终点同时进行广度优先搜索，当两边的搜索在中间相遇时终止。这种方法显著减少搜索空间，适用于状态空间较大的问题，如最短路径、字符串转换等。

时间复杂度分析：
传统BFS为 $O(b^{d})$ ，双端BFS优化为 $O(b^{d/2})$ ，其中b是分支因子，d是目标深度

编写一个程序，计算一个骑士从棋盘上的一个格子到另一个格子所需的最小步数。骑士一步可以移动到的位置由下图给出。

下图中骑士的走法与中国象棋中的“马”走法类似，都是走一个“日”字格。

输入格式

第一行给出骑士的数量 n。
在接下来的 3n 行中，每 33行描述了一个骑士。其中，

第一行一个整数 L 表示棋盘的大小，整个棋盘大小为 L×L；

第二行和第三行分别包含一对整数(x,y)，表示骑士的起始点和终点。假设对于每一个骑士，起始点和终点均合理。

输出格式

对每一个骑士，输出一行一个整数表示需要移动的最小步数。如果起始点和终点相同，则输出 0。

输入数据 1
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
Copy

输出数据 1
5
28
0

本题是一个BFS的模板题，但如果强行用BFS推演骑士的行走路径可能会导致卡常数而超时，因此双向BFS可以有效解决这个问题，除在起点进行BFS还可以同时在终点进行BFS，最终只要其中有一方便历到对方的路径就返回结束。具体代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5;
int t,l,x1,x2,y11,y2;
int dx[]={0,1,2,2,1,-1,-2,-2,-1};
int dy[]={0,2,1,-1,-2,-2,-1,1,2};
int vis1[N][N],vis2[N][N];
void bfs(){
	queue<pair<int,int> > q1;
	queue<pair<int,int> > q2;
	q1.push({x1,y11});
	q2.push({x2,y2});
	while(q1.size()&&q2.size()){
		int a1=q1.front().first;int b1=q1.front().second;
		int a2=q2.front().first;int b2=q2.front().second;
		q1.pop(),q2.pop();
		for(int i=1;i<=8;i++){
			int xx=a1+dx[i],yy=b1+dy[i];
			if(xx>=0&&xx<l&&yy>=0&&yy<l&&vis1[xx][yy]>vis1[a1][b1]+1){
				vis1[xx][yy]=vis1[a1][b1]+1;
				q1.push({xx,yy});
//				cout<<xx<<" "<<yy<<" "<<vis1[xx][yy]<<" "<<vis2[xx][yy]<<endl;
				if(vis2[xx][yy]!=0x3f3f3f3f){
					cout<<vis1[xx][yy]+vis2[xx][yy]<<endl;
					return;
				}
			}
		}
//		cout<<endl;
		for(int i=1;i<=8;i++){
			int xx=a2+dx[i],yy=b2+dy[i];
			if(xx>=0&&xx<l&&yy>=0&&yy<l&&vis2[xx][yy]>vis2[a2][b2]+1){
				vis2[xx][yy]=vis2[a2][b2]+1;
				q2.push({xx,yy});
//				cout<<xx<<" "<<yy<<" "<<vis1[xx][yy]<<" "<<vis2[xx][yy]<<endl;
				if(vis1[xx][yy]!=0x3f3f3f3f){
					cout<<vis1[xx][yy]+vis2[xx][yy]<<endl;
					return;
				}
			}
		}
	}
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d%d%d",&l,&x1,&y11,&x2,&y2);
		if(x1==x2&&y11==y2){
			cout<<0<<endl;
			continue;
		}
		memset(vis1,0x3f,sizeof(vis1));
		memset(vis2,0x3f,sizeof(vis2));
		vis1[x1][y11]=0;
		vis2[x2][y2]=0;
		bfs();
	}
	return 0;
}

双端队列优化BFS

除双向BFS外，如果再向外扩展时的代价并不相同时，双向BFS并不能优化到我们想要的结果，因为代价不同，如果数据较为复杂，BFS可能被大量的重复更新，依然会爆掉，这时双端队列BFS就会派上用场，学过图论的同学都知道，Dijkstra不用重复更新的原因是使用了优先队列使其每跑一步都为最优解，同理，双端队列可以将代价大的路径放置在队尾等候，同时将当前阶段代价较小的路径放置在队头优先遍历，这样可以大大优化BFS的时间复杂度，对于该思想，最经典的题目为「BalticOI 2011 Day1」打开灯泡 Switch the Lamp On，具体核心BFS代码如下：

void bfs(){
	deque<pair<int,int> > q;
	q.push_front({0,0});
	k[0][0]=0;
	while(q.size()){
		int xx=q.front().first,yy=q.front().second;
		q.pop_front();
		if(xx+1<=n&&yy+1<=m){
			if(a[xx+1][yy+1]==92){
				if(k[xx+1][yy+1]>k[xx][yy]){
					k[xx+1][yy+1]=k[xx][yy];
					q.push_front({xx+1,yy+1});
				}
			}else if(k[xx+1][yy+1]>k[xx][yy]+1){
				k[xx+1][yy+1]=k[xx][yy]+1;
				q.push_back({xx+1,yy+1});
			}
		}
		if(xx-1>=0&&yy+1<=m){
			if(a[xx][yy+1]=='/'){
				if(k[xx-1][yy+1]>k[xx][yy]){
					k[xx-1][yy+1]=k[xx][yy];
					q.push_front({xx-1,yy+1});
				}
			}else{
				if(k[xx-1][yy+1]>k[xx][yy]+1){
					k[xx-1][yy+1]=k[xx][yy]+1;
					q.push_back({xx-1,yy+1});
				}
			}
		}
		if(xx-1>=0&&yy-1>=0){
			if(a[xx][yy]==92){
				if(k[xx-1][yy-1]>k[xx][yy]){
					k[xx-1][yy-1]=k[xx][yy];
					q.push_front({xx-1,yy-1});
				}
			}else{
				if(k[xx-1][yy-1]>k[xx][yy]+1){
					k[xx-1][yy-1]=k[xx][yy]+1;
					q.push_back({xx-1,yy-1});
				}
			}
		}
		if(xx+1<=n&&yy-1>=0){
			if(a[xx+1][yy]=='/'){
				if(k[xx+1][yy-1]>k[xx][yy]){
					k[xx+1][yy-1]=k[xx][yy];
					q.push_front({xx+1,yy-1});
				}
			}else if(k[xx+1][yy-1]>k[xx][yy]+1){
				k[xx+1][yy-1]=k[xx][yy]+1;
				q.push_back({xx+1,yy-1});
			}
		}
	}
}

总结

搜索的剪枝是我们迈入大牛的第一步，也是最重要的一步，这些剪枝的认真学习，将来一定会在赛场上的后方紫题黑题千百倍的回报你，相信我们将来的信奥之路也是一样，虽在搜索的道路上难免会撞墙，只要有敢于回头的勇气敢于修补自己，不断剪枝，这样才能在成神的道路上更进一步！！！！！！

梦虽遥，追则能达；愿虽艰，持则可圆！——《2025新年贺词》

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

掌握 Harness：让你的 AI Agent 从“纸上谈兵”到“真枪实弹”

AI Agent技术社区

MainBody AI Agent 只会聊天还不够：怎样把一句指令变成可交付结果？

AI Agent技术社区

当 RPC 框架学会说 AI 的语言：Jaws MCP 桥接与 REST 桥接深度解析

本文介绍了作者在Java AI领域的四个开源项目布局，重点解析了jaws框架新增的MCP桥接和REST桥接特性。jaws是一个基于Java 17和Netty的高性能RPC框架，最新版本通过集成MCP Java SDK 2.0.0，实现了将RPC服务自动暴露为MCP Tools和REST API的能力，打通了传统后端服务与AI Agent之间的调用壁垒。文章详细剖析了MCP协议背景、jaws框架架构