在算法学习中，广度优先搜索（BFS）适用于解决最短路径问题、状态转换问题等。深度优先搜索（DFS）适合路径搜索等问题。本文将介绍如何利用广度优先搜索解决寻找3 个 3、5、8 升水桶均分 8 升水的最优解及深度优先搜索寻找可以解决此问题的所有解决方案。
问题描述
我们有三个水桶，容量分别为 3 升、5 升和 8 升。初始状态下，8 升的水桶装满水，其他两个水桶为空。我们的目标是通过一系列倒水操作，最终使得 8 升水桶中的水被均分，即8升和5升的水桶中都有 4 升水。我们需要找到最少操作次数以及所有可能的操作路径。
问题分析
首先，我们需要明确每个水桶的容量和当前的水量。我们可以将每个状态表示为一个对象的三个属性(A, B, C)，其中A、B、C分别代表三个水桶中的水量。我们的目标是从(0, 0, 8)到(0, 4, 4)。
为了系统地解决这个问题，我们可以将状态变化看作是一个图搜索问题。每个状态是一个节点，从一个状态到另一个状态的合法倒水操作是边。我们的目标是从初始节点到目标节点找到一条路径。最短路径我们用广度优先搜索（BFS）实现,所有可能的操作我们用深度优先搜索（DFS）实现。
状态属性如下：
int bucket3; //3升水桶的水量
int bucket5; //5升水桶的水量
int bucket8; //8升水桶的水量
我们倒水一共有6中可能，bucket3->bucket5,bucket3->bucket8,bucket5->bucket3,bucket5->bucket8,bucket8->bucket3,bucket8->bucket5,且每次倒水桶中必须有水，接水桶中水没有满容量。每次操作完后倒水桶为空或者接水桶为满。
我们下图展示了一条分支的状态树结构：
代码实现
以下是Java实现的分水问题解决代码：
/**
* 3个水桶等分8升水的问题
*
* 问题描述：有3个容积分别为3升，5升，8升的水桶，初始时，只有8升水的水桶中装满了水，其他两个水桶是空的。
* 3个水桶都没有刻度，现在需要将8升水分成相等的两份，只能借助于另外两个水桶。
* 求解结果： 1、步骤最少的分水方案
* 2、所有能达成目标的分水方案
*
*/
public class WaterBucketSeparation {
/**
* 水桶状态类
*/
public static class BucketState {
int bucket3; //3升水桶的水量
int bucket5; //5升水桶的水量
int bucket8; //8升水桶的水量
BucketState prev; //上一个状态，用于回溯步骤
public BucketState(int bucket3, int bucket5, int bucket8) {
this.bucket3 = bucket3;
this.bucket5 = bucket5;
this.bucket8 = bucket8;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
BucketState that = (BucketState) o;
return bucket3 == that.bucket3 && bucket5 == that.bucket5 && bucket8 == that.bucket8 ;
}
@Override
public int hashCode() {
return Objects.hash(bucket3, bucket5, bucket8);
}
@Override
public String toString() {
return "[" + bucket3 +
", " + bucket5 +
", " + bucket8 +
"] ";
}
}
/**
* 判断分水是否成功，只有5升水桶和8升水桶都装4升水的时候，分水成功。
*/
public static boolean isSuccess(BucketState state) {
return state.bucket3 == 0 && state.bucket5 == 4 && state.bucket8 == 4;
}
/**
* 检查状态是否有效，3升水桶的水量[0,3],5升水桶的水量[0,5],8升水桶的水量[0,8]。
*/
public static boolean checkState(BucketState state){
return state.bucket3 >= 0 && state.bucket3 <= 3 &&
state.bucket5 >= 0 && state.bucket5 <= 5 &&
state.bucket8 >= 0 && state.bucket8 <= 8;
}
/**
* 生成下一步状态
* 一共有6种操作：
* 3->5,3->8,5->3,5->8,8->3,8->5,且每次倒水桶中必须有水，接水桶中水没有满容量。每次操作完后倒水桶为空或者接水桶为满。
*/
public static List<BucketState> generateNextStates(BucketState state) {
List<BucketState> nextStates = new ArrayList<>();
int bucket3 = state.bucket3;
int bucket5 = state.bucket5;
int bucket8 = state.bucket8;
// 3 -> 5
pourWater(bucket3, 3, bucket5, 5, bucket8, nextStates, state);
// 3 -> 8
pourWater(bucket3, 3, bucket8, 8, bucket5, nextStates, state);
// 5 -> 3
pourWater(bucket5, 5, bucket3, 3, bucket8, nextStates, state);
// 5 -> 8
pourWater(bucket5, 5, bucket8, 8, bucket3, nextStates, state);
// 8 -> 3
pourWater(bucket8, 8, bucket3, 3, bucket5, nextStates, state);
// 8 -> 5
pourWater(bucket8, 8, bucket5, 5, bucket3, nextStates, state);
return nextStates;
}
/**
* 倒水操作及状态判断
*/
private static void pourWater(int fromAmount, int fromCapacity, int toAmount, int toCapacity, int otherBucket, List<BucketState> nextStates, BucketState currentState) {
//倒水判断及下一个状态构建
if (fromAmount > 0 && toAmount < toCapacity) {
int pourAmount = Math.min(fromAmount, toCapacity - toAmount);
int newFromAmount = fromAmount - pourAmount;
int newToAmount = toAmount + pourAmount;
BucketState newState;
if (fromCapacity == 3) {
newState = new BucketState(newFromAmount, toCapacity == 5 ? newToAmount : otherBucket, toCapacity == 8 ? newToAmount : otherBucket);
} else if (fromCapacity == 5) {
newState = new BucketState(toCapacity == 3 ? newToAmount : otherBucket, newFromAmount, toCapacity == 8 ? newToAmount : otherBucket);
} else {
newState = new BucketState(toCapacity == 3 ? newToAmount : otherBucket, toCapacity == 5 ? newToAmount : otherBucket, newFromAmount);
}
//检查状态
if (checkState(newState)) {
newState.prev = currentState;
nextStates.add(newState);
}
}
}
/**
* 广度优先搜索求解最优解
*/
public static BucketState bfs(BucketState state){
Queue<BucketState> queue = new LinkedList<>();
Set<BucketState> visited = new HashSet<>();
queue.add(state);
while (!queue.isEmpty()) {
BucketState currentState = queue.poll();
visited.add(currentState);
if (isSuccess(currentState)) {
return currentState;
}
List<BucketState> nextStates = generateNextStates(currentState);
for (BucketState nextState : nextStates){
if (!visited.contains(nextState)) {
queue.add(nextState);
visited.add(nextState);
}
}
}
return null;
}
/**
* 深度优先搜索求解所有可能解
*/
public static void dfs(BucketState state,Set<BucketState> visited, List<BucketState> result){
if(isSuccess(state)){
result.add(state);
return;
}
//递归深度优先搜索
for(BucketState nextState : generateNextStates(state)){
if(!visited.contains(nextState)){
visited.add(nextState);
dfs(nextState,visited,result);
visited.remove(nextState);
}
}
}
/**
* 路径打印
*/
public static void printPath(BucketState state) {
Stack<BucketState> stack = new Stack<>();
while (state != null) {
stack.push(state);
state = state.prev;
}
int step = 1;
BucketState prevState = null;
while (!stack.isEmpty()) {
BucketState currentState = stack.pop();
if (prevState != null) {
System.out.println(step + "、" + prevState.toString() + "----->" + currentState.toString());
step++;
}
prevState = currentState;
}
}
public static void main(String[] args) {
BucketState initState = new BucketState(0, 0, 8);
// BFS 寻找最短路径
BucketState bfsResult = bfs(initState);
if (bfsResult == null) {
System.out.println("无法实现");
} else {
System.out.println("最短路径：");
printPath(bfsResult);
}
// DFS 寻找所有路径
List<BucketState> dfsResults = new ArrayList<>();
dfs(initState, new HashSet<>(), dfsResults);
System.out.println("\n共有"+dfsResults.size()+"种解");
System.out.println("\n所有路径：");
for (int i = 0; i < dfsResults.size(); i++) {
System.out.println("方式 " + (i + 1) + "：");
printPath(dfsResults.get(i));
}
}
}
最短路径：
1、[0, 0, 8] ----->[0, 5, 3]
2、[0, 5, 3] ----->[3, 2, 3]
3、[3, 2, 3] ----->[0, 2, 6]
4、[0, 2, 6] ----->[2, 0, 6]
5、[2, 0, 6] ----->[2, 5, 1]
6、[2, 5, 1] ----->[3, 4, 1]
7、[3, 4, 1] ----->[0, 4, 4]
共有23种解
所有路径：
方式 1：
1、[0, 0, 8] ----->[3, 0, 5]
2、[3, 0, 5] ----->[0, 3, 5]
3、[0, 3, 5] ----->[0, 0, 8]
4、[0, 0, 8] ----->[0, 5, 3]
5、[0, 5, 3] ----->[3, 2, 3]
6、[3, 2, 3] ----->[0, 2, 6]
7、[0, 2, 6] ----->[2, 0, 6]
8、[2, 0, 6] ----->[2, 5, 1]
9、[2, 5, 1] ----->[3, 4, 1]
10、[3, 4, 1] ----->[0, 4, 4]
方式 2：
.....
通过这段代码，我们总共找到了23种倒水的方式，最短操作的方式只有7步。
总结
通过 BFS\DFS 算法，我们可以有效地解决水桶均分问题，并找到所有可能的操作路径。这个方法不仅适用于 3、5、8 升水桶的问题，还可以推广到其他类似的最短路径及路径搜索等问题。
