野人传教士问题java

野人传教士问题是一个经典的人工智能问题，可以使用深度优先搜索、广度优先搜索、A*算法等多种算法进行求解。下面是一个使用深度优先搜索算法求解野人传教士问题的Java代码示例：

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

public class MissionariesAndCannibals {

    private static final int NUM_MISSIONARIES = 3;
    private static final int NUM_CANNIBALS = 3;

    private static final int BOAT_CAPACITY = 2;

    private static final State INITIAL_STATE = new State(NUM_MISSIONARIES, NUM_CANNIBALS, true);

    public static void main(String[] args) {
        Deque<State> stack = new ArrayDeque<>();
        Set<State> visited = new HashSet<>();

        stack.push(INITIAL_STATE);
        visited.add(INITIAL_STATE);

        while (!stack.isEmpty()) {
            State currentState = stack.pop();

            if (currentState.isGoal()) {
                printPath(currentState);
                break;
            }

            for (State nextState : currentState.generateSuccessors()) {
                if (!visited.contains(nextState)) {
                    stack.push(nextState);
                    visited.add(nextState);
                }
            }
        }
    }

    private static void printPath(State state) {
        Deque<State> path = new ArrayDeque<>();
        while (state != null) {
            path.push(state);
            state = state.getParent();
        }

        while (!path.isEmpty()) {
            System.out.println(path.pop());
        }
    }

    private static class State {

        private final int numMissionariesLeft;
        private final int numCannibalsLeft;
        private final int numMissionariesRight;
        private final int numCannibalsRight;
        private final boolean boatOnLeftBank;
        private final State parent;

        public State(int numMissionariesLeft, int numCannibalsLeft, boolean boatOnLeftBank) {
            this.numMissionariesLeft = numMissionariesLeft;
            this.numCannibalsLeft = numCannibalsLeft;
            this.numMissionariesRight = NUM_MISSIONARIES - numMissionariesLeft;
            this.numCannibalsRight = NUM_CANNIBALS - numCannibalsLeft;
            this.boatOnLeftBank = boatOnLeftBank;
            this.parent = null;
        }

        private State(int numMissionariesLeft, int numCannibalsLeft, int numMissionariesRight, int numCannibalsRight,
                      boolean boatOnLeftBank, State parent) {
            this.numMissionariesLeft = numMissionariesLeft;
            this.numCannibalsLeft = numCannibalsLeft;
            this.numMissionariesRight = numMissionariesRight;
            this.numCannibalsRight = numCannibalsRight;
            this.boatOnLeftBank = boatOnLeftBank;
            this.parent = parent;
        }

        public boolean isValid() {
            if (numMissionariesLeft < 0 || numCannibalsLeft < 0 || numMissionariesRight < 0 || numCannibalsRight < 0) {
                return false;
            }
            if (numMissionariesLeft > 0 && numCannibalsLeft > numMissionariesLeft) {
                return false;
            }
            if (numMissionariesRight > 0 && numCannibalsRight > numMissionariesRight) {
                return false;
            }
            return true;
        }

        public boolean isGoal() {
            return numMissionariesLeft == 0 && numCannibalsLeft == 0;
        }

        public Set<State> generateSuccessors() {
            Set<State> successors = new HashSet<>();

            if (boatOnLeftBank) {
                for (int numMissionaries = 0; numMissionaries <= BOAT_CAPACITY; numMissionaries++) {
                    for (int numCannibals = 0; numCannibals <= BOAT_CAPACITY - numMissionaries; numCannibals++) {
                        if (numMissionaries + numCannibals == 0) {
                            continue;
                        }
                        State nextState = new State(numMissionariesLeft - numMissionaries, numCannibalsLeft - numCannibals,
                                numMissionariesRight + numMissionaries, numCannibalsRight + numCannibals, false, this);
                        if (nextState.isValid()) {
                            successors.add(nextState);
                        }
                    }
                }
            } else {
                for (int numMissionaries = 0; numMissionaries <= BOAT_CAPACITY; numMissionaries++) {
                    for (int numCannibals = 0; numCannibals <= BOAT_CAPACITY - numMissionaries; numCannibals++) {
                        if (numMissionaries + numCannibals == 0) {
                            continue;
                        }
                        State nextState = new State(numMissionariesLeft + numMissionaries, numCannibalsLeft + numCannibals,
                                numMissionariesRight - numMissionaries, numCannibalsRight - numCannibals, true, this);
                        if (nextState.isValid()) {
                            successors.add(nextState);
                        }
                    }
                }
            }

            return successors;
        }

        public State getParent() {
            return parent;
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + numCannibalsLeft;
            result = prime * result + numMissionariesLeft;
            result = prime * result + (boatOnLeftBank ? 1231 : 1237);
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            State other = (State) obj;
            if (numCannibalsLeft != other.numCannibalsLeft) {
                return false;
            }
            if (numMissionariesLeft != other.numMissionariesLeft) {
                return false;
            }
            if (boatOnLeftBank != other.boatOnLeftBank) {
                return false;
            }
            return true;
        }

        @Override
        public String toString() {
            if (boatOnLeftBank) {
                return numMissionariesLeft + "M" + numCannibalsLeft + "C |----------------| " + numMissionariesRight + "M" + numCannibalsRight + "C";
            } else {
                return numMissionariesLeft + "M" + numCannibalsLeft + "C |----------------| " + numMissionariesRight + "M" + numCannibalsRight + "C";
            }
        }

    }
}

这个代码实现了一个 `State` 类，它表示当前状态和操作的结果。 `State` 类具有以下方法：

- `isValid()` 方法用于检查当前状态是否有效。
- `isGoal()` 方法用于检查当前状态是否达到了目标状态。
- `generateSuccessors()` 方法用于生成所有可能的后继状态。
- `getParent()` 方法返回该状态的父状态，以便沿着路径回溯。

整个程序首先创建一个搜索栈和一个已访问状态的集合。然后将初始状态压入搜索栈并将其添加到已访问状态的集合中。在搜索期间，程序从搜索栈中弹出状态并检查它是否为目标状态。如果是，则程序打印路径并退出。否则，程序生成该状态的所有后继状态，并将未访问的状态压入搜索栈中。程序继续进行直到搜索栈为空或找到目标状态。

在这个示例中，我们使用深度优先搜索算法来解决野人传教士问题。如果您想尝试其他算法，请修改程序以使用其他搜索算法。