算法系列之深度优先搜索寻找妖怪和尚过河问题的所有方式

修己xj

发布于 2025-03-12 05:07:38

8600

代码可运行

文章被收录于专栏：修己xj修己xj

运行总次数：0

代码可运行

在算法学习中，深度优先搜索（DFS）是一种常用的图搜索算法，通过递归或栈实现，适合路径搜索、连通性、拓扑排序、回溯、生成、环路检测、强连通分量和可达性等问题。本文将介绍如何利用深度优先搜索解决“妖怪和尚过河问题”的所有方式。

问题描述

有三个妖怪和三个和尚需要过河。他们只有一条小船，且船最多只能载两人。在任何时候，无论是岸边还是船上，如果妖怪的数量多于和尚，和尚就会被吃掉。如何安排过河顺序，才能让所有妖怪和和尚安全过河？列出所有可能的解？

问题分析

首先，我们需要将建立状态和动作的数学模型，我们要明确问题的状态表示。我们用五个属性来表示状态，

//左岸和尚数量
int leftMonk;
//左岸妖怪数量
int leftMonster;
//右岸和尚数量
int rightMonk;
//右岸妖怪数量
int rightMonster;
//-1代表左岸，1代表右岸
int boatLocation;

结合船移动的方向，一共右10中过河动作可供选择，分别是

* 1、一个妖怪从左岸到右岸
* 2、一个和尚从左岸到右岸
* 3、两个妖怪从左岸到右岸
* 4、两个和尚从左岸到右岸
* 5、一个和尚一个妖怪从左岸到右岸
* 6、一个妖怪从右岸到左岸
* 7、一个和尚从右岸到左岸
* 8、两个妖怪从右岸到左岸
* 9、两个和尚从右岸到左岸
* 10、一个和尚一个妖怪从右岸到左岸

我们的目标是从初始状态 (3, 3, 0, 0, -1) 通过一系列合法的移动，达到目标状态 (0, 0, 3, 3, 1)。

Java使用DFS解决问题

深度优先搜索和广度优先搜索一样，都是对图进行搜索的算法，目的也都是从起点开始搜索，直到到达顶点。深度优先搜索会沿着一条路径不断的往下搜索，直到不能够在继续为止，然后在折返，开始搜索下一条候补路径。我们可以将每个状态看作图中的一个节点，合法的移动就是节点之间的边。通过DFS，我们可以列出所有能过河的方式。

算法步骤

初始化：将初始状态 (3, 3, 0, 0, -1) 作为递归的起始节点，并标记为已访问。
递归寻找可能的路径：

取出当前的状态。
生成所有可能的下一步状态。
检查这些状态是否合法（即不违反妖怪和和尚的数量限制）。
如果某个状态是目标状态，则将当前节点添加到过河方式的集合中，回溯的时候将当前节点从访问标记set中删除。
否则，继续递归求解，并标记为已访问。

递归完成后打印所有可能的过河方式

代码实现如下：


/**
 * 妖怪与和尚过河问题
 * 描述：
 * 有三个和尚和三个妖怪在河的左岸，他们需要过河到右岸。
 *
 * 只有一条小船，最多可以承载两个人。
 *
 * 在任何时候，无论是左岸还是右岸，如果和尚的数量少于妖怪的数量，和尚就会被妖怪吃掉。
 *
 * 列出所有可能的解
 */
public class DFSCrossRiver {

    /**
     * 状态类（数据模型）
     */
    public static class State{
        //左岸和尚数量
        int leftMonk;
        //左岸妖怪数量
        int leftMonster;
        //右岸和尚数量
        int rightMonk;
        //右岸妖怪数量
        int rightMonster;
        //-1代表左岸，1代表右岸
        int boatLocation;
        //前一状态，用于回溯打印路径
        State preState;

        public State(int leftMonk, int leftMonster, int rightMonk, int rightMonster, int boatLocation, State preState) {
            this.leftMonk = leftMonk;
            this.leftMonster = leftMonster;
            this.rightMonk = rightMonk;
            this.rightMonster = rightMonster;
            this.boatLocation = boatLocation;
            this.preState = preState;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            State state = (State) o;
            return leftMonk == state.leftMonk && leftMonster == state.leftMonster && rightMonk == state.rightMonk && rightMonster == state.rightMonster && boatLocation == state.boatLocation ;
        }

        @Override
        public int hashCode() {
            return Objects.hash(leftMonk, leftMonster, rightMonk, rightMonster, boatLocation);
        }
    }

    /**
     * 动作类，记录妖怪与和尚过河的动作
     */
    @Data
    public static class Action{
        int monkNum; //船上和尚数量
        int monsterNum;//船上妖怪数量
        int boatLocation;//船移动后位置

        public Action(int monkNum, int monsterNum, int boatLocation) {
            this.monkNum = monkNum;
            this.boatLocation = boatLocation;
            this.monsterNum = monsterNum;
        }
    }


    /**
     * 列举过河动作的可供选择
     * 共有十种情况
     * 1、一个妖怪从左岸到右岸
     * 2、一个和尚从左岸到右岸
     * 3、两个妖怪从左岸到右岸
     * 4、两个和尚从左岸到右岸
     * 5、一个和尚一个妖怪从左岸到右岸
     * 6、一个妖怪从右岸到左岸
     * 7、一个和尚从右岸到左岸
     * 8、两个妖怪从右岸到左岸
     * 9、两个和尚从右岸到左岸
     * 10、一个和尚一个妖怪从右岸到左岸
     *
     */
    public static List<Action> getActions(){
        List<Action> actions = new ArrayList<>();
        //一个妖怪从左岸到右岸
        actions.add(new Action(0,1,1));
        //两个妖怪从左岸到右岸
        actions.add(new Action(0,2,1));
        //一个和尚从左岸到右岸
        actions.add(new Action(1,0,1));
        //两个和尚从左岸到右岸
        actions.add(new Action(2,0,1));
        //一个和尚一个妖怪从左岸到右岸
        actions.add(new Action(1,1,1));
        //一个妖怪从右岸到左岸
        actions.add(new Action(0,1,-1));
        //两个妖怪从右岸到左岸
        actions.add(new Action(0,2,-1));
        //一个和尚从右岸到左岸
        actions.add(new Action(1,0,-1));
        //两个和尚从右岸到左岸
        actions.add(new Action(2,0,-1));
        //一个和尚一个妖怪从右岸到左岸
        actions.add(new Action(1,1,-1));
        return actions;

    }

    /**
     * 初始状态
     */
    public static State initState(){
        State state = new State(3,3,0,0,-1,null);
        return state;
    }

    /**
     * 生成所有可能的下一个状态
     */
    public static List<State> generateNextStates(State state){
        List<State> nextStates = new ArrayList<>();
        State nextState;
        for (Action action : getActions()) {
            if(state.boatLocation != action.boatLocation){
                nextState = new State(state.leftMonk - action.monkNum*action.boatLocation, state.leftMonster - action.monsterNum*action.boatLocation,
                        state.rightMonk + action.monkNum*action.boatLocation, state.rightMonster + action.monsterNum*action.boatLocation,
                        action.boatLocation, state);
                //有效则添加
                if(checkState(nextState)){
                    nextStates.add(nextState);
                }
            }
        }
        return nextStates;
    }

    /**
     * 检查状态是否有效,(无论是左岸还是右岸，和尚数量大于妖怪数量则有效)
     */
    public static boolean checkState(State state) {
        //任何一岸的和尚数量不能少于妖怪数量，除非和尚数量为0。
        if(state.leftMonk < 0 || state.leftMonster < 0 || state.rightMonk < 0 || state.rightMonster < 0){
            return false;
        }
        //不管是左岸还是右岸，和尚数量大于妖怪数量或者和尚全部在河对岸则有效,船也只能从对岸来回开
        return (state.leftMonk == 0 || state.leftMonk >= state.leftMonster)
                && (state.rightMonk == 0 || state.rightMonk >= state.rightMonster) && state.boatLocation !=state.preState.boatLocation;
    }

    /**
     * 判断是否成功
     */
    public static boolean isSuccess(State state){
        return state.leftMonk == 0 && state.leftMonster == 0;
    }


    /**
     * 深度优先搜索方式解决渡河问题
     * 添加所有可能的方式
     */
    public static void crossRiver(State state,Set<State> visited,List<State> resultStates){
        //每次递归之前都要检查是否成功，如果成功则添加到结果集合中，并返回。
        if(isSuccess(state)){
            resultStates.add(state);
            return ;
        }
        //递归深度优先搜索
        for(State nextState : generateNextStates(state)){
            if(!visited.contains(nextState)){
                //每种方式都要添加到已访问集合中，避免重复搜索
                visited.add(nextState);
                crossRiver(nextState,visited,resultStates);
                visited.remove(nextState);
            }
        }


    }

    /**
     * 递归打印路径
     */

    public static void  printPath(State state){
        if(state.preState == null){
            return;
        }
        printPath(state.preState);
        System.out.println("从"+(state.preState.boatLocation==-1?"左":"右")+"岸到"+(state.boatLocation==-1?"左":"右")+"岸");
        System.out.println("和尚："+state.leftMonk+" "+state.rightMonk);
        System.out.println("妖怪："+state.leftMonster+" "+state.rightMonster);
    }


    public static void main(String[] args) {
        State initState = initState();
        List<State> result = new ArrayList<>();
        Set<State> visited = new HashSet<>();
        visited.add(initState);
        crossRiver(initState,visited,result);
        int i =1;
        for(State state : result){
            System.out.println("--------------方式"+i+"---------------------------");
            printPath(state);
            i++;
        }

    }
}

执行结果如下：

--------------方式1---------------------------
从左岸到右岸
和尚：3 0
妖怪：1 2
从右岸到左岸
和尚：3 0
妖怪：2 1
从左岸到右岸
和尚：3 0
妖怪：0 3
从右岸到左岸
和尚：3 0
妖怪：1 2
从左岸到右岸
和尚：1 2
妖怪：1 2
从右岸到左岸
和尚：2 1
妖怪：2 1
从左岸到右岸
和尚：0 3
妖怪：2 1
从右岸到左岸
和尚：0 3
妖怪：3 0
从左岸到右岸
和尚：0 3
妖怪：1 2
从右岸到左岸
和尚：0 3
妖怪：2 1
从左岸到右岸
和尚：0 3
妖怪：0 3
--------------方式2---------------------------
从左岸到右岸
和尚：3 0
妖怪：1 2
从右岸到左岸
和尚：3 0
妖怪：2 1
从左岸到右岸
和尚：3 0
妖怪：0 3
从右岸到左岸
和尚：3 0
妖怪：1 2
从左岸到右岸
和尚：1 2
妖怪：1 2
从右岸到左岸
和尚：2 1
妖怪：2 1
从左岸到右岸
和尚：0 3
妖怪：2 1
从右岸到左岸
和尚：0 3
妖怪：3 0
从左岸到右岸
和尚：0 3
妖怪：1 2
从右岸到左岸
和尚：1 2
妖怪：1 2
从左岸到右岸
和尚：0 3
妖怪：0 3
--------------方式3---------------------------
从左岸到右岸
和尚：2 1
妖怪：2 1
从右岸到左岸
和尚：3 0
妖怪：2 1
从左岸到右岸
和尚：3 0
妖怪：0 3
从右岸到左岸
和尚：3 0
妖怪：1 2
从左岸到右岸
和尚：1 2
妖怪：1 2
从右岸到左岸
和尚：2 1
妖怪：2 1
从左岸到右岸
和尚：0 3
妖怪：2 1
从右岸到左岸
和尚：0 3
妖怪：3 0
从左岸到右岸
和尚：0 3
妖怪：1 2
从右岸到左岸
和尚：0 3
妖怪：2 1
从左岸到右岸
和尚：0 3
妖怪：0 3
--------------方式4---------------------------
从左岸到右岸
和尚：2 1
妖怪：2 1
从右岸到左岸
和尚：3 0
妖怪：2 1
从左岸到右岸
和尚：3 0
妖怪：0 3
从右岸到左岸
和尚：3 0
妖怪：1 2
从左岸到右岸
和尚：1 2
妖怪：1 2
从右岸到左岸
和尚：2 1
妖怪：2 1
从左岸到右岸
和尚：0 3
妖怪：2 1
从右岸到左岸
和尚：0 3
妖怪：3 0
从左岸到右岸
和尚：0 3
妖怪：1 2
从右岸到左岸
和尚：1 2
妖怪：1 2
从左岸到右岸
和尚：0 3
妖怪：0 3