每日算法 — 使用java实现狼羊菜：状态空间BFS与经典约束满足问题

引言

“狼羊菜”过河问题是中国古代著名的智力题：一位农夫需要把狼、羊和白菜运到河对岸，但船每次只能载农夫和一样物品。如果农夫不在场，狼会吃羊，羊会吃菜。如何用最少次数将所有物品安全运过河？本文将用Java实现这个经典问题的完整求解，深入讲解状态空间建模、BFS最短路径搜索，以及约束满足问题的通用解法框架。

一、问题建模

1.1 状态表示

用四位二进制数表示系统状态，每一位代表一个对象所在河岸（0=左岸，1=右岸）：
– 第0位：农夫
– 第1位：狼
– 第2位：羊
– 第3位：菜

例如：状态0101(二进制)=5(十进制)表示农夫和羊在右岸，狼和菜在左岸。

1.2 约束条件

1. 船容量限制：农夫每次只能带0或1个物品过河
2. 安全约束：
3. 狼和羊不能独处（无农夫时不能同岸）
4. 羊和菜不能独处（无农夫时不能同岸）

1.3 状态转移

农夫可以单独过河，或带狼/羊/菜之一过河。每次转移后检查是否满足安全约束。

二、Java核心实现

import java.util.*;

/**
 * 过河问题状态类
 * 使用位运算高效表示和操作状态
 */
public class RiverCrossingState {
    // 位掩码定义
    public static final int FARMER = 1 << 0; // 0001 = 1
    public static final int WOLF   = 1 << 1; // 0010 = 2
    public static final int SHEEP  = 1 << 2; // 0100 = 4
    public static final int CABBAGE = 1 << 3; // 1000 = 8

    public static final int ALL_ITEMS = FARMER | WOLF | SHEEP | CABBAGE; // 1111 = 15
    public static final int START_STATE = 0; // 全部在左岸
    public static final int GOAL_STATE = ALL_ITEMS; // 全部在右岸

    private final int state; // 当前状态值

    public RiverCrossingState(int state) {
        this.state = state;
    }

    /**
     * 检查指定对象是否在右岸
     */
    public boolean isOnRightBank(int item) {
        return (state & item) != 0;
    }

    /**
     * 检查指定对象是否在左岸
     */
    public boolean isOnLeftBank(int item) {
        return (state & item) == 0;
    }

    /**
     * 获取当前状态值
     */
    public int getValue() {
        return state;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof RiverCrossingState)) return false;
        return state == ((RiverCrossingState) o).state;
    }

    @Override
    public int hashCode() {
        return state;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("State(").append(state).append("): ");
        sb.append("左岸[");
        if (isOnLeftBank(FARMER)) sb.append("农");
        if (isOnLeftBank(WOLF)) sb.append("狼");
        if (isOnLeftBank(SHEEP)) sb.append("羊");
        if (isOnLeftBank(CABBAGE)) sb.append("菜");
        sb.append("] 右岸[");
        if (isOnRightBank(FARMER)) sb.append("农");
        if (isOnRightBank(WOLF)) sb.append("狼");
        if (isOnRightBank(SHEEP)) sb.append("羊");
        if (isOnRightBank(CABBAGE)) sb.append("菜");
        sb.append("]");
        return sb.toString();
    }

    /**
     * 获取可携带的物品掩码（与农夫同岸的物品）
     */
    public int getAvailableItems() {
        int available = 0;
        if (isOnRightBank(FARMER)) {
            if (isOnRightBank(WOLF)) available |= WOLF;
            if (isOnRightBank(SHEEP)) available |= SHEEP;
            if (isOnRightBank(CABBAGE)) available |= CABBAGE;
        } else {
            if (isOnLeftBank(WOLF)) available |= WOLF;
            if (isOnLeftBank(SHEEP)) available |= SHEEP;
            if (isOnLeftBank(CABBAGE)) available |= CABBAGE;
        }
        return available;
    }
}

/**
 * 过河问题求解器
 * 使用BFS找到最少次数的解决方案
 */
public class RiverCrossingSolver {

    /**
     * 检查状态是否安全（没有物品被吃掉）
     * 不安全条件：
   * 1. 农夫不在左岸，且狼和羊都在左岸
     * 2. 农夫不在左岸，且羊和菜都在左岸
     * 3. 农夫不在右岸，且狼和羊都在右岸
   * 4. 农夫不在右岸，且羊和菜都在右岸
     */
    public static boolean isSafe(int state) {
        boolean farmerLeft = (state & RiverCrossingState.FARMER) == 0;
        boolean wolfLeft = (state & RiverCrossingState.WOLF) == 0;
        boolean sheepLeft = (state & RiverCrossingState.SHEEP) == 0;
        boolean cabbageLeft = (state & RiverCrossingState.CABBAGE) == 0;

        // 检查左岸安全性
        if (farmerLeft) {
            // 农夫在左岸，左岸安全
            // 检查右岸：狼羊不能独处，羊菜不能独处
            if (!wolfLeft && !sheepLeft && cabbageLeft) return false; // 右岸狼+羊
            if (!sheepLeft && !cabbageLeft && wolfLeft) return false; // 右岸羊+菜
        } else {
            // 农夫在右岸，右岸安全
            // 检查左岸
            if (wolfLeft && sheepLeft && !cabbageLeft) return false; // 左岸狼+羊
            if (sheepLeft && cabbageLeft && !wolfLeft) return false; // 左岸羊+菜
        }

        return true;
    }

    /**
     * 使用BFS求解最少过河次数
     * @return 包含完整状态转移路径的列表，若无解则返回null
     */
    public static List<RiverCrossingState> solveBfs() {
        Queue<Integer> queue = new LinkedList<>();
        Map<Integer, Integer> parent = new HashMap<>(); // 记录每个状态的前驱
        Map<Integer, Integer> action = new HashMap<>(); // 记录到达该状态的操作
        Set<Integer> visited = new HashSet<>();

        int start = RiverCrossingState.START_STATE;
        int goal = RiverCrossingState.GOAL_STATE;

        queue.add(start);
        visited.add(start);
        parent.put(start, null);

        while (!queue.isEmpty()) {
            int current = queue.poll();

            if (current == goal) {
                return reconstructPath(parent, start, goal);
            }

            // 生成所有可能的下一步状态
            List<Integer> nextStates = generateNextStates(current);

            for (int next : nextStates) {
                if (!visited.contains(next) && isSafe(next)) {
                    visited.add(next);
                    parent.put(next, current);
                    queue.add(next);
                }
            }
        }

        return null; // 无解
    }

    /**
     * 生成当前状态的所有合法后继状态
     */
    private static List<Integer> generateNextStates(int current) {
        List<Integer> nextStates = new ArrayList<>();
        boolean farmerRight = (current & RiverCrossingState.FARMER) != 0;

        // 农夫单独过河
        int next = current ^ RiverCrossingState.FARMER;
        nextStates.add(next);

        // 农夫带一个物品过河（只能带同岸的物品）
        int[] items = {RiverCrossingState.WOLF, RiverCrossingState.SHEEP, RiverCrossingState.CABBAGE};

        for (int item : items) {
            // 检查物品是否与农夫同岸
            boolean itemSameSide = ((current & RiverCrossingState.FARMER) != 0) == 
                                   ((current & item) != 0);
            if (itemSameSide) {
                // 农夫和该物品一起过河
                next = current ^ RiverCrossingState.FARMER ^ item;
                nextStates.add(next);
            }
        }

        return nextStates;
    }

    /**
     * 回溯重建路径
     */
    private static List<RiverCrossingState> reconstructPath(
            Map<Integer, Integer> parent, int start, int goal) {
        List<RiverCrossingState> path = new ArrayList<>();
        Integer current = goal;

        while (current != null) {
            path.add(new RiverCrossingState(current));
            current = parent.get(current);
        }

        Collections.reverse(path);
        return path;
    }

    /**
     * 打印带操作的解决方案
     */
    public static void printSolution(List<RiverCrossingState> path) {
        if (path == null) {
            System.out.println("无解！");
            return;
        }

        System.out.println("===== 最少次数解决方案 =====");
        System.out.println("总共需要 " + (path.size() - 1) + " 次渡河\n");

        for (int i = 0; i < path.size(); i++) {
            System.out.println("步骤 " + i + ": " + path.get(i));

            if (i < path.size() - 1) {
                String action = describeAction(path.get(i), path.get(i + 1));
                System.out.println("  操作: " + action);
                System.out.println();
            }
        }
    }

    /**
     * 描述从状态a到状态b的操作
     */
    private static String describeAction(RiverCrossingState from, RiverCrossingState to) {
        int diff = from.getValue() ^ to.getValue();
        boolean goingRight = !from.isOnRightBank(RiverCrossingState.FARMER);
        String direction = goingRight ? "从左岸到右岸" : "从右岸到左岸";

        StringBuilder carried = new StringBuilder();
        if ((diff & RiverCrossingState.WOLF) != 0) carried.append("狼");
        if ((diff & RiverCrossingState.SHEEP) != 0) carried.append("羊");
        if ((diff & RiverCrossingState.CABBAGE) != 0) carried.append("菜");

        if (carried.length() == 0) {
            return "农夫独自渡河 " + direction;
        } else {
            return "农夫带" + carried + "渡河 " + direction;
        }
    }

    /**
     * 查找所有可能的解决方案（不只是最短路径）
     */
    public static List<List<RiverCrossingState>> findAllSolutions(int maxDepth) {
        List<List<RiverCrossingState>> allSolutions = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        List<RiverCrossingState> currentPath = new ArrayList<>();

        dfsFindAll(RiverCrossingState.START_STATE, RiverCrossingState.GOAL_STATE,
                   visited, currentPath, allSolutions, maxDepth, 0);

        return allSolutions;
    }

    private static void dfsFindAll(int current, int goal, Set<Integer> visited,
                                    List<RiverCrossingState> path,
                                    List<List<RiverCrossingState>> solutions,
                                    int maxDepth, int depth) {
        if (depth > maxDepth) return;

        path.add(new RiverCrossingState(current));

        if (current == goal) {
            solutions.add(new ArrayList<>(path));
            path.remove(path.size() - 1);
            return;
        }

        visited.add(current);

        List<Integer> nextStates = generateNextStates(current);
        for (int next : nextStates) {
            if (!visited.contains(next) && isSafe(next)) {
                dfsFindAll(next, goal, visited, path, solutions, maxDepth, depth + 1);
            }
        }

        visited.remove(current);
        path.remove(path.size() - 1);
    }
}

三、通用约束满足框架

/**
 * 通用过河问题求解器
 * 可以处理任意数量的角色和约束
 */
public class GenericRiverSolver {

    /**
     * 约束接口：定义什么样的状态是安全的
     */
    interface Constraint {
        boolean isSafe(int state, int numItems);
    }

    /**
     * 经典的狼羊菜约束
     */
    static class ClassicConstraint implements Constraint {
        @Override
        public boolean isSafe(int state, int numItems) {
            // 狼(1)和羊(2)不能独处
            // 羊(2)和菜(3)不能独处
            boolean farmerRight = (state & 1) != 0;

            for (int bank = 0; bank <= 1; bank++) {
                boolean farmerHere = farmerRight == (bank == 1);
                if (farmerHere) continue; // 农夫在该岸，安全

                boolean wolfHere = ((state & 2) != 0) == (bank == 1);
                boolean sheepHere = ((state & 4) != 0) == (bank == 1);
                boolean cabbageHere = ((state & 8) != 0) == (bank == 1);

                if (wolfHere && sheepHere && !cabbageHere) return false;
                if (sheepHere && cabbageHere && !wolfHere) return false;
            }
            return true;
        }
    }

    /**
     * 传教士与食人族约束
     * 3传教士+3食人族，船载2人
     * 任何岸上食人族不能多于传教士（除非传教士为0）
     */
    static class MissionariesConstraint implements Constraint {
        @Override
        public boolean isSafe(int state, int numItems) {
            // 状态编码：低3位=右岸传教士(0-3)，中3位=右岸食人族(0-3)
            int missionariesRight = state & 7;
            int cannibalsRight = (state >> 3) & 7;
            int missionariesLeft = 3 - missionariesRight;
            int cannibalsLeft = 3 - cannibalsRight;

            // 检查两岸安全
            if (missionariesLeft > 0 && cannibalsLeft > missionariesLeft) return false;
            if (missionariesRight > 0 && cannibalsRight > missionariesRight) return false;

            return true;
        }
    }

    /**
     * 通用BFS求解
     */
    public static List<Integer> solveGeneric(int numItems, int boatCapacity,
                                              Constraint constraint, int goalState) {
        Queue<Integer> queue = new LinkedList<>();
        Map<Integer, Integer> parent = new HashMap<>();
        Set<Integer> visited = new HashSet<>();

        queue.add(0);
        visited.add(0);

        while (!queue.isEmpty()) {
            int current = queue.poll();

            if (current == goalState) {
                return reconstructPath(parent, 0, goalState);
            }

            // 生成所有合法操作
            List<Integer> moves = generateGenericMoves(current, numItems, boatCapacity);

            for (int next : moves) {
                if (!visited.contains(next) && constraint.isSafe(next, numItems)) {
                    visited.add(next);
                    parent.put(next, current);
                    queue.add(next);
                }
            }
        }

        return null;
    }

    /**
     * 生成通用移动
     */
    private static List<Integer> generateGenericMoves(int current, int numItems, int capacity) {
        List<Integer> moves = new ArrayList<>();
        boolean farmerRight = (current & 1) != 0;

        // 农夫必须过河
        int baseMove = current ^ 1;
        moves.add(baseMove); // 单独过河

        // 生成带0到capacity-1个物品的组合
        int[] items = new int[numItems - 1];
        for (int i = 0; i < numItems - 1; i++) {
            items[i] = 1 << (i + 1);
        }

        // 简化为只考虑带1个物品的情况（经典问题）
        for (int item : items) {
            boolean sameSide = ((current & 1) != 0) == ((current & item) != 0);
            if (sameSide) {
                moves.add(current ^ 1 ^ item);
            }
        }

        return moves;
    }

    private static List<Integer> reconstructPath(Map<Integer, Integer> parent, 
                                                  int start, int goal) {
        List<Integer> path = new ArrayList<>();
        Integer current = goal;
        while (current != null) {
            path.add(current);
            current = parent.get(current);
        }
        Collections.reverse(path);
        return path;
    }
}

四、完整运行示例

/**
 * 狼羊菜过河问题主程序
 */
public class WolfSheepCabbageApp {
    public static void main(String[] args) {
        System.out.println("===== 狼羊菜过河问题 =====\n");

        // BFS求解
        List<RiverCrossingState> solution = RiverCrossingSolver.solveBfs();
        RiverCrossingSolver.printSolution(solution);

        // 查找所有解法
        System.out.println("\n===== 查找所有解法（深度限制10） =====");
        List<List<RiverCrossingState>> allSolutions = 
            RiverCrossingSolver.findAllSolutions(10);
        System.out.println("找到 " + allSolutions.size() + " 种解法");

        if (!allSolutions.isEmpty()) {
            System.out.println("最短解法步数: " + (allSolutions.get(0).size() - 1));
        }

        // 可视化状态空间图
        System.out.println("\n===== 状态空间分析 =====");
        analyzeStateSpace();

        // 传教士与食人族问题
        System.out.println("\n===== 传教士与食人族问题 =====");
        solveMissionaries();
    }

    private static void analyzeStateSpace() {
        int totalStates = 16; // 2^4
        int safeStates = 0;
        int reachableStates = 0;

        System.out.println("所有可能状态分析：");
        for (int s = 0; s < totalStates; s++) {
            boolean safe = RiverCrossingSolver.isSafe(s);
            if (safe) safeStates++;

            RiverCrossingState state = new RiverCrossingState(s);
            System.out.println("  " + state + " -> " + (safe ? "安全" : "不安全"));
        }

        System.out.println("\n统计：");
        System.out.println("  总状态数: " + totalStates);
        System.out.println("  安全状态数: " + safeStates);
        System.out.println("  不安全状态数: " + (totalStates - safeStates));
    }

    private static void solveMissionaries() {
        // 3传教士+3食人族，状态编码：右岸传教士(0-3) + 右岸食人族(0-3) * 8
        GenericRiverSolver.Constraint constraint = new GenericRiverSolver.MissionariesConstraint();
        List<Integer> path = GenericRiverSolver.solveGeneric(4, 2, constraint, 0x3F); // 111111 = 全部到右岸

        if (path != null) {
            System.out.println("找到解决方案！步数: " + (path.size() - 1));
            for (int i = 0; i < path.size(); i++) {
                int state = path.get(i);
                int m = state & 7;
                int c = (state >> 3) & 7;
                System.out.println("步骤 " + i + ": 右岸(" + m + "传," + c + "食), 左岸(" + 
                                 (3-m) + "传," + (3-c) + "食)");
            }
        } else {
            System.out.println("无解！");
        }
    }
}

五、算法分析

六、总结与扩展

本文通过位运算高效实现了经典过河问题的状态表示和BFS求解，并提供了通用约束满足框架。位运算使状态操作的时间复杂度降至O(1)，非常适合小规模状态空间问题。

扩展方向：
1. 更多角色：增加狐狸、鸡、米等更多角色和约束
2. 多船问题：多条船同时渡河
3. 桥问题：多人在夜间过桥，每次最多两人，需手电筒
4. 图论建模：将状态空间显式建图后用Dijkstra求最短路径