三通水桶均分问题
假设A为容积为8升的水桶，B为容积为3升的空桶，C为容积为5升的空桶。
因为要分为两个4升，B<4<C<A,所以最后肯定是在A桶和C桶的。
经过演算很容易就能得到：
1． A->C // A=3,C=5,B=0;
2． C->B //C=2,B=3,A=3;
3． B->A //A=6,B=0,C=2;
4． C->B //A=6,B=2,C=0;
5． A->C //A=1,B=2,C=5;
6． C->B //A=1,B=3,C=4;
7． B->A //A=4,B=0,C=4;
想着写个源码，卡了半天，无奈百度喽，学到很多，就写篇博客了
本题有初始状态和最终需要的状态，那么中间的操作怎么进行呢？采用穷举法的话，从初始状态开始，根据某种状态变化的规则搜索全部可能的状态，每当找到一个从初始状态到最终状态的变化路径，就可以理解为找到了一种答案。这样的状态变化搜索的结果通常是得到一棵状态搜索树，根节点是初始状态，叶子节点可能是最终状态，也可能是某个无法转换到最终状态的中间状态，状态树有多少个最终状态的叶子节点，就有多少种答案。
1.建立算法的状态模型；
2.确定状态树的搜索·算法及状态转换的规则
3.提高算法的效率
建立状态模型是整个算法的关键，这个状态模型不仅要能描述静止状态，还要能描述并记录状态转换动作，尤其是对状态转换的描述。所谓的静止状态，就是某个时刻三个水桶中存水的容量，如果采用长度为3的一维向量来描述这个状态。这组向量的三个值分别是容量为8升，5升，3升的桶中的水量。因此算法的初始状态就可以描述为【8,0,0】,则最终状态为【4,4,0】。
对状态转换的描述就是在两个状态之间建立联系，在本算法中这个关联就是一个合法的倒水动作。某时刻三个水桶的存水状态，经过某个倒水动作演变到一个新的存水状态，这是对状态转换的文字描述，然后可以写个伪代码。那么对算法；来讲呢，倒水状态描述就是“静止状态”+“倒水动作”。我们用一个三元组来描述倒水动作：{from ,to,water},from是指从哪个桶中倒水，to是指将水倒向哪个桶，water是此倒水动作所倒的水量。本模型的特例就是第一个状态如何得到，也就是[8, 0, 0]这个状态对应的倒水动作如何描述？我们用-1表示未知的水桶编号（上帝水桶），因此第一个状态对应的倒水动作就是{-1, 1, 8}。应用本模型对前面提到的第一种解决方法进行状态转换描述，整个过程如图（1）所示
状态树搜索算法
确定了状态模型后，就需要解决算法面临的第二个问题：状态树的搜索算法。一个静止状态结合不同的倒水动作会迁移到不同的状态，所有状态转换所展示的就是一棵以状态[8, 0, 0]为根的状态搜索树，图（2）画出了这个状态搜索树的一部分，其中一个用不同颜色标识出来的状态转换过程（状态树的一个分支）就是本问题的一个解：
状态树的搜索就是对整个状态树进行遍历，这中间其实暗含了状态的生成，因为状态树一开始并不完整，只有一个初始状态的根节点，当搜索（也就是遍历）操作完成时，状态树才完整。树的遍历可以采用广度优先遍历算法，也可以采用深度优先遍历算法，就本题而言，要求解所有可能的等分水的方法，暗含了要记录从初始状态到最终状态，所以更适合使用深度优先遍历算法。状态树的遍历暗含了一个状态生成的过程，就是促使状态树上的一个状态向下一个状态转换的驱动过程，这是一个很重要的部分，如果不能正确地驱动状态变化，就不能实现状态树的遍历（搜索）。
建立状态模型一节中提到的动作模型，就是驱动状态变化的关键因子。对一个状态来说，它能转换到哪些新状态，取决于它能应用哪些倒水动作，一个倒水动作能够在原状态的基础上“生成”一个新状态，不同的倒水动作可以“生成”不同的新状态。由此可知，状态树遍历的关键是找到三个水桶之间所有合法的倒水动作，用这些倒水动作分别“生成”各自相应的新状态。遍历三个水桶的所有可能动作，就是对三个水桶任取两个进行全排列（常用的排列组合算法可以参考《排列组合算法》一文），共有6种水桶的排列组合，也就是说有6种可能的倒水动作。将这6种倒水动作依次应用到当前状态，就可以“生成”6种新状态，从而驱动状态发生变化（有些排列并不能组合出合法的倒水动作，关于这一点后面“算法优化”部分会介绍）。
算法优化和避免状态循环
从图中可以看出来，对于三个水桶这样小规模的题目，其整个状态树的规模也是相当大的，更何况是复杂一点的情况，因此类似本文这样对搜索整个状态树求解问题的算法都不得不面对一个算法效率的问题，必须要考虑如何进行优化，减少一些明显不必要的搜索，加快求解的过程。
前文讲过，状态搜索的核心是对三个水桶进行两两排列组合得到6种倒水动作，但是并不是每种倒水动作都是合法的，比如，需要倒出水的桶中没有水的情况和需要倒进水的桶中已经满的情况下，都组合不出合法的倒水动作。除此之外，因为水桶是没有刻度的，因此倒水动作也是受限制的，也就是说合法的倒水动作只能有两种结果：需要倒出水的桶被倒空和需要倒进水的桶被倒满。加上这些限制之后，每次组合其实只有少数倒水动作是合法的，可以驱动当前的状态到下一个状态。利用这一点，就可以对状态树进行“剪枝”，避免对无效（非法）的状态分支进行搜索。
除了通过“剪枝”提高算法效率，对于深度优先的状态搜索还需要防止因状态的循环生成造成深度优先搜索无法终止的问题。状态的循环生成有两种表现形式：一种是在两个桶之间互相倒水；另一种就是图中展示的一个例子，[3, 5, 0] -> [3, 2, 3] -> [6, 2, 0] -> [3, 5, 0]形成一个状态环。要避免出现状态环，就需要记录一次深度遍历过程中所有已经搜索过的状态，形成一个当前搜索已经处理过的状态表，每当生成一个新状态，就先检查是否是状态表中已经存在的状态，如果是则放弃这个状态，回溯到上一步继续搜索。如果新状态是状态表中没有的状态，则将新状态加入到状态表，然后从新状态开始继续深度优先遍历。在这个过程中因重复出现被放弃的状态，可以理解为另一种形式的“剪枝”，可以使一次深度优先遍历很快收敛到初始状态。
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> bucket_size;
struct action {
int from;
int to;
int water;
};
//每个桶状态和倒水动作(倒水动作是由上一个状态到这个状态的倒水动作)
struct bucket_states {
vector<int> states_vector;
action ac;
bucket_states(int a, int b, int c, int from, int to, int water) {
states_vector.resize(3);
states_vector[0] = a;
states_vector[1] = b;
states_vector[2] = c;
ac.from = from;
ac.to = to;
ac.water = water;
}
bucket_states(){
states_vector.resize(3);
}
void set_action(int dump_water, int from, int to) {
ac.from = from;
ac.to = to;
ac.water = dump_water;
}
bool is_empty(int bucket_idx) {
if(bucket_idx > 2) {
return false;
}
return (states_vector[bucket_idx] == 0);
}
bool is_full(int bucket_idx) {
return (states_vector[bucket_idx] >= bucket_size[bucket_idx]);
}
bool is_final() {
return (states_vector[0] == 4 && states_vector[1] == 4);
}
bool dump_water(int from, int to, bucket_states& next) {
vector<int> bucket_water(this->states_vector);
//倒水数目是to桶剩余的空间
int dump_water = bucket_size[to] - states_vector[to];
//如果from中的水大于to桶剩余的空间，则倒出dunp_water的水量
if(bucket_water[from] >= dump_water) {
bucket_water[to] += dump_water;
bucket_water[from] -= dump_water;
} else {//否则倒出from桶中的所有水
dump_water = bucket_water[from];
bucket_water[to] += dump_water;
bucket_water[from] = 0;
}
if(dump_water > 0) {
next.states_vector = bucket_water;
next.set_action(dump_water, from, to);
return true;
}
return false;
}
};
void print_states(bucket_states& bucket){
cout << "bucket_states : " << bucket.states_vector[0] << " " <<
bucket.states_vector[1] << " " << bucket.states_vector[2] <<
" from " << bucket.ac.from << " to " << bucket.ac.to <<
" dump " << bucket.ac.water << "L water." << endl;
}
//禁止给自己倒水，禁止从空桶取水，禁止给满桶倒水
bool is_action_valid(bucket_states& cur, int from, int to) {
if((from != to) && !cur.is_empty(from) && !cur.is_full(to))
return true;
return false;
}
bool is_loop(vector<bucket_states>& states, bucket_states& next) {
int i = 0;
for(; i < states.size(); ++i) {
if(equal(next.states_vector.begin(), next.states_vector.end(),
states[i].states_vector.begin()))
return true;
}
return false;
}
//搜索算法
void DFS(vector<bucket_states>& states, int& cnt, int& shortest) {
bucket_states cur = states.back();
//判断是否是最终状态, 打印倒水过程，记录方案数目以及需要最少操作的数目
if(cur.is_final()) {
++cnt;
shortest = min(shortest, static_cast<int>(states.size()));
for_each(states.begin(), states.end(), print_states);
cout << "=====================" << endl;
return;
}
for(int i = 0; i < 3; ++i)
for(int j = 0; j < 3; ++j) {
if(is_action_valid(cur, i, j)) {
bucket_states next_states;
//进行状态转移，执行倒水动作，并判断倒水动作是否有效
bool is_dump = cur.dump_water(i, j, next_states);
//检查倒水动作是否可以驱动到下一个有效状态，以及下一个状态是否已经重复
if(is_dump && !is_loop(states, next_states)) {
states.push_back(next_states);
DFS(states, cnt, shortest);
states.pop_back();
}
}
}
}
int main() {
bucket_size.push_back(8);
bucket_size.push_back(5);
bucket_size.push_back(3);
vector<bucket_states> states;
bucket_states start(8, 0, 0, -1, 0, 8);
states.push_back(start);
int cnt = 0, shortest = INT_MAX;
DFS(states, cnt, shortest);
cout << "result size : " << cnt << " shortest : " << shortest <<endl;
}
数据结构课上老师给我们提出了这样的一个问题，于是我就思考有没有一种算法能直接得到所有可能结果，然后小弟不才，未能写出源码，好在度娘有大佬~~思想和代码都看得很明白！！！真的大佬，不过让我自己来敲的话，可能还是太弱了，得尽快学习DFS和BFS了。算法真的挺优美的，有血有肉，哈哈哈
投递OPPO等公司10个岗位 >