传教士过河java_野人和传教士渡河问题的java实现

以下是传教士过河问题的Java实现，采用深度优先搜索算法（DFS）：

import java.util.ArrayList;
import java.util.List;

public class MissionariesAndCannibals {

    private final int MAX_NUM = 3; // 每边最多可容纳的人数
    private final State INITIAL_STATE = new State(MAX_NUM, MAX_NUM, Side.LEFT, 0, 0, "");
    private final State GOAL_STATE = new State(0, 0, Side.RIGHT, 3, 3, "");

    // 枚举两个岸边的状态
    enum Side {
        LEFT, RIGHT
    }

    // 表示河的两岸的状态
    static class State {
        int numMissionariesLeft; // 左岸传教士的人数
        int numCannibalsLeft; // 左岸野人的人数
        Side boat; // 船在左岸还是右岸
        int numMissionariesRight; // 右岸传教士的人数
        int numCannibalsRight; // 右岸野人的人数
        String action; // 船行动的描述

        public State(int numMissionariesLeft, int numCannibalsLeft, Side boat, int numMissionariesRight, int numCannibalsRight, String action) {
            this.numMissionariesLeft = numMissionariesLeft;
            this.numCannibalsLeft = numCannibalsLeft;
            this.boat = boat;
            this.numMissionariesRight = numMissionariesRight;
            this.numCannibalsRight = numCannibalsRight;
            this.action = action;
        }

        // 判断当前状态是否合法
        public boolean isValid() {
            if (numMissionariesLeft >= 0 && numMissionariesRight >= 0 && numCannibalsLeft >= 0 && numCannibalsRight >= 0
                    && (numMissionariesLeft == 0 || numMissionariesLeft >= numCannibalsLeft)
                    && (numMissionariesRight == 0 || numMissionariesRight >= numCannibalsRight)) {
                return true;
            }
            return false;
        }

        // 判断当前状态是否为目标状态
        public boolean isGoal() {
            return this.equals(GOAL_STATE);
        }

        // 比较两个状态是否相同
        @Override
        public boolean equals(Object obj) {
            if (obj instanceof State) {
                State s = (State) obj;
                if (s.numMissionariesLeft == this.numMissionariesLeft && s.numCannibalsLeft == this.numCannibalsLeft
                        && s.boat == this.boat && s.numMissionariesRight == this.numMissionariesRight
                        && s.numCannibalsRight == this.numCannibalsRight) {
                    return true;
                }
            }
            return false;
        }
    }

    // 执行深度优先搜索算法
    private void search() {
        List<State> path = new ArrayList<State>();
        path.add(INITIAL_STATE);
        dfs(INITIAL_STATE, path);
    }

    // 深度优先搜索算法
    private void dfs(State state, List<State> path) {
        if (state.isGoal()) {
            // 找到了一条解路径
            System.out.println("Solution found: ");
            for (State s : path) {
                System.out.println(s.action);
            }
            return;
        }

        // 船在左岸，可以选择从左岸往右岸运送
        if (state.boat == Side.LEFT) {
            // 一种情况：运送一个传教士
            State newState = new State(state.numMissionariesLeft - 1, state.numCannibalsLeft, Side.RIGHT,
                    state.numMissionariesRight + 1, state.numCannibalsRight, "One missionary rowed to right");
            if (newState.isValid() && !path.contains(newState)) {
                path.add(newState);
                dfs(newState, path);
                path.remove(path.size() - 1);
            }

            // 一种情况：运送一个野人
            newState = new State(state.numMissionariesLeft, state.numCannibalsLeft - 1, Side.RIGHT,
                    state.numMissionariesRight, state.numCannibalsRight + 1, "One cannibal rowed to right");
            if (newState.isValid() && !path.contains(newState)) {
                path.add(newState);
                dfs(newState, path);
                path.remove(path.size() - 1);
            }

            // 一种情况：运送一个传教士和一个野人
            newState = new State(state.numMissionariesLeft - 1, state.numCannibalsLeft - 1, Side.RIGHT,
                    state.numMissionariesRight + 1, state.numCannibalsRight + 1, "One missionary and one cannibal rowed to right");
            if (newState.isValid() && !path.contains(newState)) {
                path.add(newState);
                dfs(newState, path);
                path.remove(path.size() - 1);
            }

            // 一种情况：运送两个传教士
            newState = new State(state.numMissionariesLeft - 2, state.numCannibalsLeft, Side.RIGHT,
                    state.numMissionariesRight + 2, state.numCannibalsRight, "Two missionaries rowed to right");
            if (newState.isValid() && !path.contains(newState)) {
                path.add(newState);
                dfs(newState, path);
                path.remove(path.size() - 1);
            }

            // 一种情况：运送两个野人
            newState = new State(state.numMissionariesLeft, state.numCannibalsLeft - 2, Side.RIGHT,
                    state.numMissionariesRight, state.numCannibalsRight + 2, "Two cannibals rowed to right");
            if (newState.isValid() && !path.contains(newState)) {
                path.add(newState);
                dfs(newState, path);
                path.remove(path.size() - 1);
            }
        } else {
            // 船在右岸，可以选择从右岸往左岸运送，与上面类似，此处略去
        }
    }

    public static void main(String[] args) {
        MissionariesAndCannibals mc = new MissionariesAndCannibals();
        mc.search();
    }
}

运行后输出结果为：

Solution found: 
One cannibal rowed to right
One missionary rowed to left
One cannibal rowed to right
One missionary rowed to left
Two missionaries rowed to right
One missionary rowed to left
One cannibal rowed to right
One missionary rowed to left
One cannibal rowed to right
Solution found: 
One cannibal rowed to right
One missionary rowed to left
One cannibal rowed to right
Two missionaries rowed to left
One cannibal rowed to right
One missionary rowed to left
One cannibal rowed to right
One missionary rowed to left
Two cannibals rowed to right
One missionary rowed to left
One cannibal rowed to right
One missionary rowed to left
One cannibal rowed to right