【BFS】熊熊采蜜

题目描述

熊熊正在采蜜，他需要编写一个AI来帮助他高效地采集蜂蜜。在采蜜的过程中，熊熊会遇到三个蜂巢，每个蜂巢都有一定数量的蜂蜜。当熊熊发动采集时，他可以选择最多三个不同的蜂巢进行采集，这里选择的顺序不限制：
第一个被采集的蜂巢将失去 a 点蜂蜜。
第二个被采集的蜂巢（如果有）将失去 b 点蜂蜜。
第三个被采集的蜂巢（如果有）将失去 c 点蜂蜜。
如果一个蜂巢的蜂蜜数量降到 0 或以下，它就会被完全采集。注意，熊熊在一次采集中不能对同一个蜂巢采集两次。现在，给定三个蜂巢的蜂蜜数量，请帮助熊熊计算，最少需要多少次采集才能完全采集所有蜂巢。

样例

输入：
5 6 7
10 5 2
输出：
2

思路分析

为什么想到BFS？什么时候用BFS？它和DFS相比的优劣是？

这道题需要一步一步向前推进，并且每一步都有不同选择，那么显然它可以通过DFS或BFS解决。而分析过程中这道题有一个最重要的特点：某些状态是重复的。

具体来说，由于每次采集的蜂蜜a b c是不变的，如果当前蜂巢的蜂蜜数量分布重复，那么它后续的所有搜索过程都会重复。此时BFS能够对这种情况剪枝，极大优化效率

换句话说，我的理解里，搜索中的BFS相比DFS最大的优势就是能够对重复路径剪枝。

举个例子，初始蜂巢是4 4 4，采蜜量为1 2 2。那么以1 2 2顺序采蜜和以2 2 1 顺序采蜜，最终都会得到2 2 3 的蜂巢分布，于是它们的结果实际上是同样的子问题，只需要解决一个即可。

实现

首先我们要明确本题BFS中每一层的意义是什么？进入下一层的不同方向是什么？如何剪枝重复结点？

获取搜索方向

容易知道，本题对任何一个蜂巢分布每次有六种不同的采蜜方式，也就是a b c 的全排列。所以开始搜索之前我们可以将这六个方向先算出来：

vector<int> v1 = {a,b,c};
sort(v1.begin(),v1.end());

vector<vector<int>> perms;
do {
	vector<int> tv = v1;
	perms.pb(tv);
} while(next_permutation(v1.begin(),v1.end()));

其中next_permutation 用于求序列的下一个字典序更高的排列。因此我们首先排序使v1本身字典序最小。当v1已经是最大字典序时，next_permutation 将返回false ，否则返回true 。

BFS搜索本体

既然是BFS，就一定需要队列辅助维护遍历顺序。暂时不考虑剪枝，大体逻辑是：


vector<int> v2 = {H1,H2,H3};
//队列每一个元素代表一个状态结点<操作步数(搜索层数),蜂巢分布>
deque<pair<int,vector<int>>> q;
//将初始状态结点入队
q.push_back({0,v2});

while(!q.empty()) {
	int cnt = q.size();
		
	for(int i = 0; i < cnt; i++) {
        //获取当前状态结点
		auto p = q.front(); q.pop_front();
        //当前操作步数和当前蜂巢分布
		int step = p.first; vector<int> pv = p.second;

        //isValid用于判断当前蜂巢是否已经满足题意
        //如果已经满足，当前就是最优结果，结束即可
		if(isValid(pv)) {
			cout << step;
            return 0;
		}
        //对六个方向的下一个状态结点挨个入队

		for(vector<int> t : perms) {
			vector<int> tv = pv;
            //计算按该方向前进后的蜂巢分布
			for(int k = 0; k < 3; k++) {
				if(tv[k] > 0) {
					tv[k] -= t[k];
				}
			}
		}
	}
}

对重复结点的剪枝核心思路

这里一个关键思路是：一个状态结点由<操作步数,蜂巢分布> 确定，也就是说这两项都相同时，它们就是相同的状态结点，那后续搜索过程将会完全一致

于是我们考虑从这个角度去重，可以定义一个set<pair<int,vector<int>>> st ,后续每次想要入队一个新状态结点，就在st中查询是否存在，存在就不入队，从而实现剪枝。

但是仔细想想，由于我们是按层级遍历的，如果出现蜂巢分布相同而层数不同的状态结点，一定是丢弃后来的那个，因为后来的状态结点步数一定大于等于先来的状态结点。于是set中其实不需要存储操作步数，只需要对蜂巢分布去重即可。

因此set的结构可以简化为set<vector<int>> st ，由于set底层由红黑树实现，这个改动能优化近十倍效率。红黑树的基础结构一旦复杂，性能上的损耗是巨大的。

在哪个位置进行剪枝？

其实在代码的哪个步骤剪枝都可以，最重要的是思路清晰。一般有两个选择：

从队列中取出结点时检查set中是否重复
生成下一层结点时检查set中是否重复

无论哪一种方式，都需要在检查之后立刻将刚刚检查的状态结点插入到set中

最终代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAX 0x7fffffff
#define pb push_back

//检查v是否全为0，即是否符合题目要求
int isValid(vector<int>& v) {
	for(int i = 0; i < 3; i++) {
		if(v[i] > 0) {
			return 0;
		}
	}
	return 1;
}


signed main() {
	int a,b,c;
	cin >> a >> b >> c;
	int H1,H2,H3;
	cin >> H1 >> H2 >> H3;
	vector<int> v1 = {a,b,c};
	vector<int> v2 = {H1,H2,H3};
    //队列每一个元素代表一个状态结点<操作步数(搜索层数),蜂巢分布>
	deque<pair<int,vector<int>>> q;
    //剪枝set
	set<vector<int>> st;
    //将初始状态结点入队
	q.push_back({0,v2});
    
    //先排序，令v1初始字典序最小 
	sort(v1.begin(),v1.end());
    
    //获取六个搜索方向
	vector<vector<int>> perms;
	do {
		vector<int> tv = v1;
		perms.pb(tv);
	} while(next_permutation(v1.begin(),v1.end()));
    

	while(!q.empty()) {
		int cnt = q.size();
		//按层遍历
		for(int i = 0; i < cnt; i++) {
			auto p = q.front();
			q.pop_front();
			int step = p.first;
			vector<int> pv = p.second;

			if(isValid(pv)) {
				ans = step;
				q.clear();
				break;
			}

			for(vector<int> t : perms) {
				vector<int> tv = pv;
				for(int k = 0; k < 3; k++) {
					if(tv[k] > 0) {
						tv[k] -= t[k];
					}
				}
				//如果重复则跳过
				if(st.find(tv) == st.end()) {
					st.insert(tv);
					q.push_back({step+1,tv});
				}
			}
		}
	}
	cout << ans;
	return 0;
}