算法系列之深度/广度优先搜索解决水桶分水的最优解及全部解

int bucket3; //3升水桶的水量
int bucket5; //5升水桶的水量
int bucket8; //8升水桶的水量

/**
 * 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：
.....