必威体育Betway必威体育官网
当前位置:首页 > IT技术

八人过河问题详解(Java语言求解)

时间:2019-07-28 23:40:00来源:IT技术作者:seo实验室小编阅读:56次「手机版」
 

八人过河

八人过河问题详解(java语言求解)

在秋招面试搜狗数据开发岗位的时候,面试官给出了一个八个人过河的问题,后来自己查了之后发现这个是经典过河问题的一个变型。

网上也有其他求解这个问题的方法和代码。他们大多数是把所有的状态看作一个图数据,用矩阵表示,有的还需要提前把安全的状态判断出来,需要手动处理一些数据。我写的这个方法,不需要手动处理任何数据,直接就能运行出结果,最后为了更直观的展示,还会打印出找到的路径

问题描述:

现在有八个人需要划船到河的对面去。

8个人分别为:

1个父亲,带着2个儿子

1个母亲,带着2个女儿

1个警察带着1个犯人

开始时,8个人都是在左岸

四条规则:

  1. 只有警察、父母可以划船,其他人不可以
  2. 警察离开犯人,犯人就会伤害其他人
  3. 母亲不在时,父亲会伤害女儿;父亲不在时,母亲会伤害儿子。(这不是一家的)
  4. 船上一次最多只能坐两个人。

求出过河方案

分析:

每个人的状态有三种:左岸、船上、右岸。

其实这就是一个状态转移的问题。令1表示在左岸,0表示在右岸,船、警察、犯人、父亲、儿子1、儿子2、母亲、女儿1和女儿2的位置构成一个状态向量,那么就是求解从初始状态向量[1,1,1,1,1,1,1,1,1]到目标状态向量[0,0,0,0,0,0,0,0,0]的状态转移路径。

在求解这个问题的过程中,我利用了异或运算的特性。异或运算(java中操作符为^)的规则是“相同为假(0),相异为真(0)”。异或运算有一个重要的特性,[1, 0]与0异或的结果还是[1, 0],也就是和0做异或操作不会改变原来的值,但是[1,0]与1异或的结果是[0,1],也就是和1做异或操作会改变原来的结果。

由上面介绍的异或操作的特性,我设置的状态转移向量为9维的向量,如果那个人或船要改变位置,则把相应的位置设置为1,其余不改变位置的地方则设为0,例如,初始状态startState=[1,1,1,1,1,1,1,1,1],可以由警察带着犯人一起划船到对岸,那么状态转移向量就是move=[1,1,1,0,0,0,0,0,0],将startState和move对应位置做异或运算就可以得到转移后的状态为newState=[0,0,0,1,1,1,1,1,1]。

如果把每一个状态都看作是一个顶点,转移向量看作是边的化,其实这就是一个图数据,要求解从初始点到目标点的一条可行路径。可以采用深度优先遍历或广度优先遍历,我喜欢用递归来求解,所以其实是采用的深度优先遍历。在每一个状态下,都生成所有可行的状态转移向量,然后将状态与转移向量做异或运算得到新的状态。

在求解的过程中要注意:1

  1. 检查状态是否安全。不安全的话,则不能继续往下搜索。
  2. 防止状态循环。如果当前到达的状态已经出现过了,则不能在继续往下搜索,否则会出现状态循环问题的。

求解问题的java代码

public class PassRiver5 {

    private  static int[] end_states = {0,0,0,0,0,0,0,0,0};//目标状态
    //船、警察、犯人、父亲、儿子1、儿子2、母亲、女儿1、女儿2
    private  static String[] roles = {"船","警察","犯人","父亲","儿子1","儿子2","母亲","女儿1","女儿2"};
    public static void main(String[] args){

        // 1: 在左侧,0:在右侧
        int[] states = {1,1,1,1,1,1,1,1,1};//初始状态
        List<int[]> trace = new ArrayList<>();
        long startTime = system.currenttimemillis();
        pass(states, new int[]{0,0,0,0,0,0,0,0,0}, trace);
        long endTime = System.currentTimeMillis();
        System.out.println("process time : "+(endTime - startTime));
    }

    public static void pass(int[] start_state, int[] old_move, List<int[]> trace){
        if(Arrays.equals(start_state, end_states)){//人员全部到达了右岸
            System.out.println("找到了一条路径;");
            showTrace(trace);
            return ;
        }
        //0. 检查一下状态是否安全
        if(!checkSafe(start_state)){
//            System.out.println("状态不安全;");
            return ;//当前状态不安全,直接返回
        }
        //1.生成状态转移向量
        int[][] moves = createMoves(start_state);//2019-1-13

        //2. 执行状态状态转移
        for (int[] move:moves) {
            int[] new_state = transformState(start_state, move);
            //进行下一个状态的遍历
            //要防止状态出现循环
            if (!checkCircle2(new_state)){
                trace.add(move);
                pass(new_state, move, trace);
                trace.remove(trace.size()-1);
            }
        }

        /**
         * 总结:
         * 0,判断是否还可以往下面的搜索分支发展。
         * 1,生成所有可以搜索的分支
         * 2,递归的向接下来的分支发展。
         */
    }

    /**
     * 展示找到的状态转移路径
     * @param trace
     */
    private static void showTrace(List<int[]> trace) {
        for (int[] move : trace) {
            for (int people = POLICE; people < move.length; people++) {
                if(move[people] == 1){
                    System.out.print(roles[people]+",");
                }
            }
            System.out.println("坐船到对岸;");
        }
    }

    static List<int[]> state_record = new ArrayList<>();
    /**
     * 检查是否出现了状态循环,如果出现,那么就不能往下走了。
     * @param state  当前的状态
     * @return 当前状态state已经出现过了,返回true; 如果没有出现过,则返回false;
     */
    private static boolean checkCircle2(int[] state) {
        for (int[] record : state_record) {
            if(Arrays.equals(record, state)){//已经出现过了这个状态
                return true;
            }
        }
        state_record.add(state);
        return false;
    }

    /**
     *  检查是否出现了状态循环,如果出现,那么就不能往下走了。
     *  测试  通过
     * @param old_move 上一次状态转移时的move
     * @param new_move 本次状态转移时的move
     * @return 两个move相同,会造成循环,返回true;两个move不同,返回false.
     */
    private static boolean checkCircle(int[] old_move, int[] new_move) {
        for (int position = 0; position < old_move.length; position++) {
            if(old_move[position] != new_move[position]){
                return false;
            }
        }
        return true;
    }

    public static final int BOAT        = 0;
    public static final int POLICE      = 1;
    public static final int CRIMINAL    = 2;
    public static final int FATHER      = 3;
    public static final int SON_1       = 4;
    public static final int SON_2       = 5;
    public static final int MATHER      = 6;
    public static final int DAUGHTER_1  = 7;
    public static final int DAUGHTER_2  = 8;
    /**
     * 检查状态是不是安全的。
     * 注:该方法已经通过了测试,可以使用
     * @param start_state 当前状态
     * @return 安全,true; 不安全, false
     */
    private static boolean checkSafe(int[] start_state) {
        // 2) 警察离开犯人,犯人会伤害其他人
        if(start_state[POLICE] != start_state[CRIMINAL]){//警察离开了犯人
            for(int people=FATHER; people < start_state.length; people++){
                if(start_state[people] == start_state[CRIMINAL]){//此时有人与犯人在同一侧
                    return false;//犯人会伤害其他人
                }
            }
        }
        // 3) 母亲不在时,父亲会伤害女儿;父亲不在时,母亲会伤害儿子。(这不是一家的)
        if((start_state[MATHER] != start_state[DAUGHTER_1]) && (start_state[FATHER] == start_state[DAUGHTER_1]) ){
            //父亲会伤害女儿1
            return false;
        }
        if((start_state[MATHER] != start_state[DAUGHTER_2]) && (start_state[FATHER] == start_state[DAUGHTER_2])){
            //父亲会伤害女儿2
            return false;
        }
        if((start_state[FATHER] != start_state[SON_1]) &&  (start_state[MATHER] == start_state[SON_1])){
            //母亲会伤害儿子1
            return false;
        }
        if((start_state[FATHER] != start_state[SON_2]) && (start_state[MATHER] == start_state[SON_2])){
            //母亲会伤害儿子2
            return false;
        }
        return true;
    }

    /**
     * 执行状态转换
     * 测试了,没问题
     * @param start_state
     * @param move
     * @return 状态安全就返回true;要是状态不安全就返回false。
     */
    private static int[] transformState(int[] start_state, int[] move) {
        //注意,要对start_state进行复制,如果不进行复制的话,后面改变后,可能会发生其他的不期望的负作用
        int[] new_state = Arrays.copyOf(start_state, start_state.length);
        //按每一个位置进行异或操作
        for (int position = 0; position < new_state.length; position++) {
//            new_state[position] = new_state[position]==move[position] ? 0 : 1;
            new_state[position] = new_state[position] ^ move[position];
        }
        return  new_state;
    }

    /**
     * 在start_state情况下生成可以执行的状态转移向量
     * @param start_state 需要生成状态转移的一个初始状态
     * @return
     */
    private static int[][] createMoves(int[] start_state) {
        //考虑方面
        //1. 选择的人必须和船在同一侧
        //2. 可以选择一个人,也可以选择两个人,必须有一个人会划船
        //3. 不用考虑状态安全问题,有专门的函数检测状态是否安全。
        //4. 也不用考虑状态循环的问题,有专门的函数来处理状态循环问题。
        //注:只需要考虑这个函数createMoves所在的抽象层就行了,实现函数的功能,并且不要去产生副作用,以免后续分析时发现不了附带的问题。
        
        //1. 获取船的位置
        //int boat_position = start_state[BOAT];
        //2. 在和船的一侧的人中选择人
        List<int[]> moves_list = new ArrayList<>();
        //2.1 选择一个人
        List<int[]> moves_onePeople = moveByOnePeople(start_state);
        moves_list.addAll(moves_onePeople);

        //2.2 选择两个人
        List<int[]> moves_twoPeople = moveByTwoPeople(start_state);
        moves_list.addAll(moves_twoPeople);

        return moves_list.toArray(new int[][]{});
    }

    private static List<int[]> moveByOnePeople(int[] start_state) {
        //1. 获取船的位置
        int boat_position = start_state[BOAT];
        //2. 选择和船同侧的一个人
        List<int[]> moves_list = new ArrayList<>();
        for (int people =POLICE ; people < start_state.length; people++) {
            if(start_state[people] == boat_position){//和船在同一侧
                if(canRow(people)){//people可以划船
                    int[] move = new int[]{0,0,0,0,0,0,0,0,0};
                    move[BOAT]=1;
                    move[people]=1;
                    moves_list.add(move);
                }
            }
        }
        return moves_list;
    }

    private static List<int[]> moveByTwoPeople(int[] start_state) {
        //1. 获取船的位置
        int boat_position = start_state[BOAT];
        //2. 选择和船同侧的两个人
        List<int[]> moves_list = new ArrayList<>();
        for (int people1 = POLICE; people1 < start_state.length-1; people1++) {
            if(start_state[people1] == boat_position){//people1和船同侧
                for (int people2 = people1+1; people2 < start_state.length; people2++) {
                    if(start_state[people2] == boat_position){//people2和船同侧
                        if(canRow(people1) || canRow(people2)){//至少有一个人可以划船
                            int[] move =  new int[]{0,0,0,0,0,0,0,0,0};
                            move[BOAT]=1;
                            move[people1]=1;
                            move[people2]=1;
                            moves_list.add(move);
                        }
                    }
                }
            }
        }
        return moves_list;
    }

    /**
     * 判断people是否可以划船
     * @param people 要判断的人
     * @return 可以划船,true;不可以划船,false。
     */
    public static boolean canRow(int people){
        if(people == POLICE || people == FATHER || people == MATHER){//只有警察、父母可以划船
            return true;
        }else{//,其他人不可以
            return false;
        }
    }
}

运行结果:

找到了一条路径;
警察,犯人,坐船到对岸;
警察,坐船到对岸;
警察,儿子1,坐船到对岸;
警察,犯人,坐船到对岸;
父亲,儿子2,坐船到对岸;
父亲,坐船到对岸;
父亲,母亲,坐船到对岸;
母亲,坐船到对岸;
警察,犯人,坐船到对岸;
父亲,坐船到对岸;
父亲,母亲,坐船到对岸;
母亲,坐船到对岸;
母亲,女儿1,坐船到对岸;
警察,犯人,坐船到对岸;
警察,女儿2,坐船到对岸;
警察,坐船到对岸;
警察,犯人,坐船到对岸;
process time : 14

总结

网上也有其他求解这个问题的方法和代码。他们大多数是把所有的状态看作一个图数据,用矩阵表示,有的还需要提前把安全的状态判断出来,需要手动处理一些数据。我写的这个方法,不需要手动处理任何数据,直接就能运行出结果,最后为了更直观的展示,还会打印出找到的路径。

可以看到我是用数组来边时状态向量的,然后在一个元素一个元素的做异或运算,其实可以把状态向量编码成一个整数,例如初始状态[1,1,1,1,1,1,1,1,1]就可以看作是整数511,状态转移向量也可以做相应的处理。但是考虑到这个做的话,会存在编码与解码的问题,所以就没有采用。

还有一个问题就是,为了避免状态循环,我会把访问过的状态记录下来,保存在一个List中,这么做,在判断一个状态是否出现时是有点耗时的,如果你有更好的方法,请告诉我一下,谢谢。

参考资料

算法编程】过河问题:https://blog.csdn.net/tengweitw/article/details/25296257

用编程解决过河问题:https://blog.csdn.net/linghuainian/article/details/78148929?utm_source=blogxgwz3

360笔试题2013:https://blog.csdn.net/huangxy10/article/details/8066408

相关阅读

分享到:

栏目导航

推荐阅读

热门阅读