题目: 有三个容积分别是 8 升 5 升和 3 升的水桶, 其中容积为 8 升的水桶中有 8 升水, 其它两个水桶是空的三个水桶都没有刻度, 问如何在不借助其它工具的情况下只使用这三个桶把 8 升水等分
思路: 把某一时刻三个水桶的水量称之为一个状态, 则初始状态为 {8, 0, 0}, 结束状态为{4, 4, 0} 可以使用穷举法, 从初始状态开始, 根据状态变化的可能性 (引起状态变化的操作) 遍历所有可能的状态, 每当找到一个从初始状态到最终状态的路径, 即可认为找到了一个解对于引起状态变化的操作, 在本例中也就是倒水的动作, 可以使用一个动作来建模, 它包含三个要素: 从哪个水桶倒水, 倒进哪个水桶, 以及倒了多少水对于每个状态来说, 总共有 3x3 种倒水的方式(包含一些不合理的倒水, 比如向自己倒水), 因此对于每个状态仅需要循环这 3x3 种可能性然后递归地从下个状态进行搜索即可, 这在理论上来说是一个深度优先搜索
剪枝: 深度优先搜索可能会遇到重复状态引起的环路, 比如上一个步骤从1向2倒了5升水, 下一个步骤就从2向1倒了5升水, 还可能有一些比较复杂的环路, 所以需要把已经搜索过的状态添加到一个集合中去, 在搜索一个状态前先看看是否已经搜索过, 如果已经搜索过或者正在搜索则直接跳过即可
代码:
- import java.util.Arrays;
- import java.util.HashSet;
- import java.util.Set;
- import java.util.Stack;
- public class SplitWaterTo2x4 {
- Set<State> states = new HashSet<>(); // 用于存储已经搜索过的状态的集合
- Stack<State> order = new Stack<>(); // 用于存储已经搜索过的状态的顺序, 用于最后输出
- Stack<Action> actions = new Stack<>(); // 用于存储已经进行过的操作
- // 水桶的状态, 分别对应 8L5L 和 3L 的水桶
- Bucket[] buckets = {new Bucket(8), new Bucket(5), new Bucket(3)};
- public void search(final State s) {
- if (isFinalState(s)) {
- printAction();
- printOrder();
- return;
- }
- states.add(s);
- order.push(s);
- // 遍历所有可能的倒水动作
- for (int i = 0; i < 3; i++) {
- for (int j = 0; j < 3; j++) {
- if (!isLegal(i, j, s)) continue; // 判断从 i 桶向 j 桶倒水是否可行
- final State newState = update(i, j, s); // 如果可行则更新状态, 并将对应的操作入栈
- if (hasSearched(newState)) {
- actions.pop();
- continue; // 如果此状态已经搜索过则跳过, 避免状态陷入环路
- }
- search(newState);
- actions.pop();
- states.remove(newState); // 搜索完 newState 之后需要把它移出已经搜索过的状态的集合, 切记!!!
- }
- }
- order.pop();
- }
- private void printAction() {
- System.out.println();
- System.out.println();
- for (int i = 0; i < actions.size(); i++) {
- System.out.println(actions.elementAt(i));
- }
- System.out.println();
- System.out.println("-----------------------------------");
- }
- private void printOrder() {
- System.out.println();
- System.out.println();
- for (int i = 0; i < order.size(); i++) {
- System.out.println(order.elementAt(i));
- }
- // 由于最终状态没有 push 到 order 栈里面, 所以输出的时候补上
- System.out.println(new State(4, 4, 0));
- System.out.println();
- System.out.println("-----------------------------------");
- }
- private boolean hasSearched(State state) {
- return states.contains(state);
- }
- // 在现有的状态上更新, 并返回新状态
- private State update(int i, int j, State s) {
- final State newState = new State(s);
- Action action = new Action();
- action.from = i;
- action.to = j;
- if (s.ss[i] > buckets[j].capacity - s.ss[j]) { // 如果 i 中的水多于 j 中的剩余容量
- newState.ss[j] = buckets[j].capacity;
- action.water = buckets[j].capacity - s.ss[j];
- newState.ss[i] = s.ss[i] - action.water;
- } else { //i 中的水可以全部倒入 j 中
- newState.ss[j] = s.ss[j] + s.ss[i];
- newState.ss[i] = 0;
- action.water = s.ss[i];
- }
- actions.push(action);
- return newState;
- }
- // 判断在 s 状态下, 从 i 向 j 倒水是否合理
- private boolean isLegal(int i, int j, State s) {
- return i != j && s.ss[i] != 0 && s.ss[j] != buckets[j].capacity;
- }
- private boolean isFinalState(State state) {
- return state.ss[0] == 4 && state.ss[1] == 4 && state.ss[2] == 0;
- }
- public void printState(State state) {
- System.out.println("State now:" + state);
- }
- public static void main(String[] args) {
- new SplitWaterTo2x4().search(new State(8, 0, 0));
- }
- }
- class Action {
- int from;
- int to;
- int water; // 本次倒了多少水 i
- @Override
- public String toString() {
- return "Action{" +
- "from=" + from +
- ", to=" + to +
- ", water=" + water +
- '}';
- }
- }
- class Bucket {
- int capacity;
- public Bucket(int capacity) {
- this.capacity = capacity;
- }
- }
- class State {
- final int[] ss;
- public State(int... a) {
- ss = a;
- }
- public State(State s) {
- ss = Arrays.copyOf(s.ss, s.ss.length);
- }
- // 由于需要放入 Set 中, 所以重写 equals()和 hashcode()方法来判断两个 State 是否相同
- @Override
- public boolean equals(Object o) {
- if (this == o) return true;
- if (o == null || getClass() != o.getClass()) return false;
- State state = (State) o;
- return Arrays.equals(ss, state.ss);
- }
- @Override
- public int hashCode() {
- return Arrays.hashCode(ss);
- }
- @Override
- public String toString() {
- return "State{" + Arrays.toString(ss) + '}';
- }
- }
注意:
程序需要输出最后的倒水路径, 所以使用了一个栈来保存已经进行的操作, 顺便还保存了状态变化的路径, 另外栈这个数据结构本身也比较适合深度优先搜索
states 需要判断某个 State 是否包含其中, 所以类 State 重写了 equals()和 hashcode()方法
在 update()函数中将倒水操作入栈, 但是如果发现这个状态已经被搜索过则需要把操作出栈, 否则就等搜索过这个新状态之后再把操作出栈
在搜索完一个新状态 A 后需要把这个状态从 states 中删除, 因为可能有其它路径也能到达这个状态 A, 如果不把 A 从 states 中删除, 那么其它能到达 A 状态的操作路径都会少了一个正确答案
最好把类 State 设计成 Immutable 模式, 否则很容易在遍历的过程中不知不觉地修改了 State 的字段, 造成程序完全错误
来源: http://blog.csdn.net/Q_AN1314/article/details/79481024