JAVA野人_Java实现传教士与野人过河问题

传教士与野人过河问题是一个经典的人工智能问题，可以使用Java来实现。

这个问题的基本思路是：有三个传教士和三个野人要过一条河，但是河上只有一条船，船只能装两个人，而且当传教士数量少于野人数量时，野人会吃掉传教士。现在要求设计一个算法，使得所有人都能安全过河。

解决这个问题的常用算法是深度优先搜索（DFS）。具体实现时，可以定义一个状态类，表示当前河岸的状态，然后从初始状态开始，进行深度优先搜索，直到找到一种方案使得所有人都能安全过河，或者搜索所有可能的状态都失败。

以下是Java代码的一个简单实现，仅供参考：

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

public class RiverCrossing {
    private int missionaryLeft;  // 左岸传教士数量
    private int cannibalLeft;    // 左岸野人数量
    private int missionaryRight; // 右岸传教士数量
    private int cannibalRight;   // 右岸野人数量
    private boolean boat;        // 船的位置，true表示在右岸，false表示在左岸

    public RiverCrossing(int missionaryLeft, int cannibalLeft, boolean boat, int missionaryRight, int cannibalRight) {
        this.missionaryLeft = missionaryLeft;
        this.cannibalLeft = cannibalLeft;
        this.boat = boat;
        this.missionaryRight = missionaryRight;
        this.cannibalRight = cannibalRight;
    }

    // 判断当前状态是否合法
    public boolean isValid() {
        if (missionaryLeft >= 0 && missionaryRight >= 0 && cannibalLeft >= 0 && cannibalRight >= 0
                && (missionaryLeft == 0 || missionaryLeft >= cannibalLeft)
                && (missionaryRight == 0 || missionaryRight >= cannibalRight)) {
            return true;
        }
        return false;
    }

    // 判断当前状态是否为目标状态
    public boolean isGoal() {
        if (missionaryLeft == 0 && cannibalLeft == 0) {
            return true;
        }
        return false;
    }

    // 获取当前状态的所有合法后继状态
    public List<RiverCrossing> getSuccessors() {
        List<RiverCrossing> successors = new ArrayList<RiverCrossing>();

        if (boat) { // 船在右岸
            if (missionaryRight > 0) {
                successors.add(new RiverCrossing(missionaryLeft, cannibalLeft, false, missionaryRight - 1, cannibalRight));
            }
            if (cannibalRight > 0) {
                successors.add(new RiverCrossing(missionaryLeft, cannibalLeft, false, missionaryRight, cannibalRight - 1));
            }
            if (missionaryRight > 0 && cannibalRight > 0) {
                successors.add(new RiverCrossing(missionaryLeft, cannibalLeft, false, missionaryRight - 1, cannibalRight - 1));
            }
            if (missionaryRight > 1) {
                successors.add(new RiverCrossing(missionaryLeft, cannibalLeft, false, missionaryRight - 2, cannibalRight));
            }
            if (cannibalRight > 1) {
                successors.add(new RiverCrossing(missionaryLeft, cannibalLeft, false, missionaryRight, cannibalRight - 2));
            }
        } else { // 船在左岸
            if (missionaryLeft > 0) {
                successors.add(new RiverCrossing(missionaryLeft - 1, cannibalLeft, true, missionaryRight, cannibalRight));
            }
            if (cannibalLeft > 0) {
                successors.add(new RiverCrossing(missionaryLeft, cannibalLeft - 1, true, missionaryRight, cannibalRight));
            }
            if (missionaryLeft > 0 && cannibalLeft > 0) {
                successors.add(new RiverCrossing(missionaryLeft - 1, cannibalLeft - 1, true, missionaryRight, cannibalRight));
            }
            if (missionaryLeft > 1) {
                successors.add(new RiverCrossing(missionaryLeft - 2, cannibalLeft, true, missionaryRight, cannibalRight));
            }
            if (cannibalLeft > 1) {
                successors.add(new RiverCrossing(missionaryLeft, cannibalLeft - 2, true, missionaryRight, cannibalRight));
            }
        }

        List<RiverCrossing> validSuccessors = new ArrayList<RiverCrossing>();
        for (RiverCrossing successor : successors) {
            if (successor.isValid()) {
                validSuccessors.add(successor);
            }
        }
        return validSuccessors;
    }

    // 打印当前状态
    public void print() {
        System.out.println("Left:" + missionaryLeft + "M " + cannibalLeft + "C");
        System.out.println("Right:" + missionaryRight + "M " + cannibalRight + "C");
        String boatSide = boat ? "Right" : "Left";
        System.out.println("Boat is at " + boatSide + " side.");
        System.out.println();
    }
}

然后，在主函数中，可以使用深度优先搜索来求解问题：

import java.util.HashSet;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        RiverCrossing initialState = new RiverCrossing(3, 3, false, 0, 0);
        Stack<RiverCrossing> stack = new Stack<RiverCrossing>();
        HashSet<RiverCrossing> visited = new HashSet<RiverCrossing>();
        stack.push(initialState);
        visited.add(initialState);

        while (!stack.isEmpty()) {
            RiverCrossing currentState = stack.pop();
            if (currentState.isGoal()) {
                currentState.print();
                break;
            }
            for (RiverCrossing successorState : currentState.getSuccessors()) {
                if (!visited.contains(successorState)) {
                    stack.push(successorState);
                    visited.add(successorState);
                }
            }
        }
    }
}

这样，就可以得到所有合法的状态，并输出最终的解法。