狼羊菜过河问题深入学习分析——Java语言描述版

前言

这个问题的抛出,是几个星期之前的算法课程。老师分析了半天,最后的结论是:其实就是图的遍历。那时候挺懵逼的,不管是对于图,还是遍历,或者是数据结构,心里面都没有一个十足的概念,所以搁置了这么久的问题,现在就来好好研究清楚。

问题描述:

一个农夫在河边要过河,但是他带着一匹狼、一只羊和一颗白菜。他需要用船将这三样东西运至对岸,然而,这艘船的空间有限,只容得下他自己和另一样东西(或狼或羊或白菜)。若他不在场看管的话,狼就会吃羊,羊就会去吃白菜。此人如何才能过河。

问题分析:

抛开算法,把这个题当成是一个简单的逻辑题的话还是挺好解的,你过不了多久你就会发现几个关键的问题:

  • 1.你要时刻注意农夫的位置,因为农夫不在地时候狼会吃羊,羊会吃菜
  • 2.第一步只能把羊带走
  • 3.最后一步只能是把羊从河对岸带过来

你会发现羊其实是问题的关键,只要保证羊和狼和白菜隔离开来,那么就很容易解这个问题。下面是这道题的答案:

①把羊带到河对岸 -> 把狼带到河对岸,再把羊带回来 -> 把白菜带到河对岸 -> 把羊带到河对岸
②把羊带到河对岸 -> 把白菜带到河对岸,再把羊带回来 -> 把狼带到河对岸 -> 把羊带到河对岸

算法分析:

过河问题,其实质就是一种状态的改变,就像这个问题说的,农夫狼羊菜都要从河的这边到对岸去,也就对应了两个状态,一个是没过河的状态,一个是过了河的状态。

状态的改变

所以很自然的联想到了用0和1来表示他们的状态,并且每时每刻,农夫狼羊菜的状态都对应一个特定的状态,比如没过河的状态是0000,四个都没有过河,而过河的状态是1111。这样做的好处是将问题抽象成了计算机能够处理的数据。

你当然可以选择暴力穷举法,列出所有可能并找出合理的,这是屡试不爽而且行之有效(对于自己来说)的方法。

但这并不是聪明的做法。如果学习数据结构学习得好的同学(不包括我),会想到用图的V来描述每一种状态,用E来描述状态之间的对应关系,最后进行图的遍历就能找到答案了。反正当时我是想不到的..

图形简单回顾

图是一种很重要的数据结构,这里就简单用相邻矩阵表示法来简单回顾并描述一下图吧。

1.下图是一个无向图,有五个顶点,所以我们使用5x5的数组存放图形。

无向图

2.在上图中,先找和①相邻的顶点有哪些,把和①相邻的顶点2和顶点5的坐标填入1:

找和①相邻的顶点

3.其他顶点以此类推可以得到相邻矩阵:

相邻矩阵

至此我们就利用一个二维数组来描述了一个图形,0表示没有边连接,1表示有边。

继续分析问题

上面提到可以用0,1来表示某一时刻特定的状态,很简单的分析可以得到只存在以下10种情况(右边表示河对岸):

农夫狼羊菜 | (空)
农夫羊菜 | 狼_________农夫狼菜 | 羊_________农夫狼羊 | 菜
狼菜 | 农夫羊_________农夫羊 | 狼菜
狼 | 农夫羊菜_________羊 | 农夫狼菜_________菜 | 农夫狼羊
(空) | 农夫狼羊菜

所以抽象成01可以这样表示:

0000
0100_________0010_________0001
1010_________0101
1011_________1101_________1110
1111

这样就得到了我们的顶点集合,这些顶点包含了各个对象的状态,所以我们需要创建一个Vertex类来表示顶点,里面或许会要再需要一个ObjState类来描述对象各自的状态。然后我们需要一个二维数组来表示相邻矩阵。

再思考

思考:我们现在有了:

  • 一个顶点类,里面包含了描述各个对象状态的ObjState类。
  • 一个用来描述边集的空的二维数组(里面还没有数据)

我们程序的最终目的,是要找到过河的方案,至少得要输出整个过程吧,因为Vertex本身描述的就是一个特定的状态,所以可以加入一个String类型的字符串来描述这样的状态,例如:0000描述为“最开始的状态",0100描述为”农夫羊菜 | 狼“。

顶点连通的条件

我们有了这样的一些拥有自身状态信息的顶点,还需要判断他们的连通性,也就是找“边”。仔细思考一下你就会发现,其实两个状态的连通就只有两个条件:

1.man的状态不一样:
这是因为要保证完成过河的动作,因为过河的这个动作保证了行动的进行,只有过河才能改变现在的状态到下一个状态,这是过程进行的必然条件。
2.最多只有一个其他对象的状态不一样:
除了保证man的状态不一样,也要保证狼羊菜这三个对象中,最多只有1个对象的状态不一样。

所以我们只要判断两两点之间,是否满足以上状态,如果满足,则把相邻矩阵的对应位置置为1即可。

遍历图的条件

我们现在有了描述顶点的Vertex类,有了一个表示边集的二维数组,那么就要遍历图来寻找满足条件的路径了。

我们需要注意的是,如何防止路径的重复查找,也就是在一条路上走来走去的情况,我们需要引入一个额外的描述当前点是否访问过的一维数组visited[],默认的值应该小于等于0,如果该点访问了,则把对应的visited置为访问该点的点的编号,例如点2访问点5,那么visited[4] = 2,这样做的好处是,输出的时候就能很方便的遍历出相应的路径。

要多多分析问题

多多分析问题,更能帮助我们分析清楚问题,也能帮助我们找到比较好的编程实现方法,会少走许多弯路,总之就是要多多分析问题,对于编程来说,这是比磨刀不误砍柴工还要高上几个级别的事。

总之就是要多分析问题,再开始写代码。

写代码:

ObjState类:

首先创建一个描述对象属性的类:

class ObjState{
    // 对象类,保存了对象的状态
    public int man;
    public int wolf ;
    public int sheep;
    public int vegetable;
}

其中定义了int类型的四种对象(其实就是四个变量,来简单模拟四个对象)。
初始化的工作可以交给Vertex类:

Vertex类:

顶点类,包含了ObjState类,保存了顶点对象的状态以及输出时的信息。

class Vertex {
    ObjState objState = new ObjState();     // 对象状态信息
    String outputMessage;                   // 输出时要显示的信息
    public Vertex(int manState, int wolfState, int sheepState,
                  int vegetableState, String outputMessage){
        // 初始化工作
        objState.man = manState;
        objState.wolf = wolfState;
        objState.sheep = sheepState;
        objState.vegetable = vegetableState;
        this.outputMessage = outputMessage;
    }
}

Tester主类:

1.首先在main函数外边定义三个全局变量:

public static int[][] arr = new int[10][10];    // 保存了相邻矩阵信息
public static ArrayList<Vertex> arrayList = new ArrayList<>();  // 顶点集
public static int[] visited = new int[10];      // 用来保存是否遍历

2.然后在main函数中添加进我们的是个顶点:

arrayList.add(new Vertex(0, 0, 0, 0, "初始状态"));
arrayList.add(new Vertex(0, 1, 0, 0, "农夫羊菜 | 狼"));
arrayList.add(new Vertex(0, 0, 1, 0, "农夫狼菜 | 羊"));
arrayList.add(new Vertex(0, 0, 0, 1, "农夫狼羊 | 菜"));
arrayList.add(new Vertex(1, 0, 1, 0, "狼菜 | 农夫羊"));
arrayList.add(new Vertex(0, 1, 0, 1, "农夫羊 | 狼菜"));
arrayList.add(new Vertex(1, 0, 1, 1, "狼 | 农夫羊菜"));
arrayList.add(new Vertex(1, 1, 0, 1, "羊 | 农夫狼菜"));
arrayList.add(new Vertex(1, 1, 1, 0, "菜 | 农夫狼羊"));
arrayList.add(new Vertex(1, 1, 1, 1, "已经全部过河"));

3.初始化我们的相邻矩阵数组:

for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
        arr[i][j] = 0;
    }
}   // for循环结束初始化数组

4.找边:
因为我们定义的状态为int类型,所以判断第二个条件时,需要加上绝对值,看不懂多看两边就看懂了。

for (int i = 0; i < 10; i++) {
   // 满足两个条件:①man的状态不一样②有且仅有最多一个狼羊菜中的一个对象状态不一样    int temp_i_Man = arrayList.get(i).objState.man;
    int temp_i_Wolf = arrayList.get(i).objState.wolf;
    int temp_i_Sheep = arrayList.get(i).objState.sheep;
    int temp_i_Vegetable = arrayList.get(i).objState.vegetable;
    for (int j = 0; j < 10; j++) {
        int temp_j_Man = arrayList.get(j).objState.man;
        int temp_j_Wolf = arrayList.get(j).objState.wolf;
        int temp_j_Sheep = arrayList.get(j).objState.sheep;
        int temp_j_Vegetable = arrayList.get(j).objState.vegetable;
        if (temp_i_Man != temp_j_Man && (Math.abs(temp_i_Wolf - temp_j_Wolf) +
                        Math.abs(temp_i_Sheep - temp_j_Sheep) +
                        Math.abs(temp_i_Vegetable - temp_j_Vegetable) <= 1)) {
            arr[i][j] = 1;          // 满足以上条件则满足连通性,置为1
        }
    }
}

5.可以试着输出相邻矩阵:

for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
        System.out.printf("%2d", arr[i][j]);
    }
    System.out.println();   // 换行操作
}

编写dfs方法来遍历图:

记得在调用这个方法之前要把visited[0]置为1,因为我们使从第一个点出发的。

public static void dfs(int start, int end) {
    if (start == end) {
        print(end);    // 调用print()方法输出结果
        System.out.println();
    }

    for (int i = 0; i < 10; i++) {
        if (arr[start-1][i] > 0 && visited[i] == 0) {
            // 有边且没有被访问
            visited[i] = start;
            dfs(i+1, end);
            visited[i] = 0; // 回溯时置为0
        }
    }
}

编写print类来输出结果:

public static void print(int end) {
    // 从最后往前遍历,然后正序输出
    int[] temp = new int[10]; // 保存了倒叙输出的顺序
    int num = 0;    // num表示要输出的个数
    int i = end;    // i表示当前是第几个数
    while (i != 1) {
        // 当i不是第一个数字时,则继续往前找
        temp[num] = visited[i - 1];
        i = temp[num];
        num++;      // num加1
    }
    for (int j = num - 1; j > 0; j--) {
        System.out.println(arrayList.get(temp[j] - 1).outputMessage);
    }
    // 输出最终状态
    System.out.println(arrayList.get(9).outputMessage);
}


最后的结果:

0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0
0 0 0 0 1 0 1 0 1 0
0 0 0 0 0 0 1 1 0 0
1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 1
0 0 1 1 0 0 0 0 0 0
0 1 0 1 0 1 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
初始状态
狼菜 | 农夫羊
农夫狼菜 | 羊
狼 | 农夫羊菜
农夫狼羊 | 菜
羊 | 农夫狼菜
已经全部过河

初始状态
狼菜 | 农夫羊
农夫狼菜 | 羊
菜 | 农夫狼羊
农夫羊菜 | 狼
羊 | 农夫狼菜
已经全部过河

完整的程序:

package wudi.lt;

import java.util.ArrayList;

/**
 * ★狼羊菜问题详细学习
 * 欢迎转载,转载请注明出处:
 * 简书地址:http://www.jianshu.com/u/a40d61a49221
 * CSDN地址:http://blog.csdn.net/qq939419061
 *
 * ★如果有任何的问题,欢迎给我留言,本程序只供学习使用,谢谢!
 *
 * @author:我没有三颗心脏
 * @create:2017-09-25-15:25
 */
class ObjState{
    // 对象类,保存了对象的状态
    public int man;
    public int wolf ;
    public int sheep;
    public int vegetable;
}
class Vertex {
    ObjState objState = new ObjState();     // 对象状态信息
    String outputMessage;                   // 输出时要显示的信息
    public Vertex(int manState, int wolfState, int sheepState,
                  int vegetableState, String outputMessage){
        // 初始化工作
        objState.man = manState;
        objState.wolf = wolfState;
        objState.sheep = sheepState;
        objState.vegetable = vegetableState;
        this.outputMessage = outputMessage;
    }
}

public class Tester1 {
    public static int[][] arr = new int[10][10];    // 保存了相邻矩阵信息
    public static ArrayList<Vertex> arrayList = new ArrayList<>();  // 顶点集
    public static int[] visited = new int[10];      // 用来保存是否遍历

    public static void main(String[] args) {
        arrayList.add(new Vertex(0, 0, 0, 0, "初始状态"));
        arrayList.add(new Vertex(0, 1, 0, 0, "农夫羊菜 | 狼"));
        arrayList.add(new Vertex(0, 0, 1, 0, "农夫狼菜 | 羊"));
        arrayList.add(new Vertex(0, 0, 0, 1, "农夫狼羊 | 菜"));
        arrayList.add(new Vertex(1, 0, 1, 0, "狼菜 | 农夫羊"));
        arrayList.add(new Vertex(0, 1, 0, 1, "农夫羊 | 狼菜"));
        arrayList.add(new Vertex(1, 0, 1, 1, "狼 | 农夫羊菜"));
        arrayList.add(new Vertex(1, 1, 0, 1, "羊 | 农夫狼菜"));
        arrayList.add(new Vertex(1, 1, 1, 0, "菜 | 农夫狼羊"));
        arrayList.add(new Vertex(1, 1, 1, 1, "已经全部过河"));
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                arr[i][j] = 0;
            }
        }   // for循环结束初始化数组

        for (int i = 0; i < 10; i++) {
            int temp_i_Man = arrayList.get(i).objState.man;
            int temp_i_Wolf = arrayList.get(i).objState.wolf;
            int temp_i_Sheep = arrayList.get(i).objState.sheep;
            int temp_i_Vegetable = arrayList.get(i).objState.vegetable;
            for (int j = 0; j < 10; j++) {
                int temp_j_Man = arrayList.get(j).objState.man;
                int temp_j_Wolf = arrayList.get(j).objState.wolf;
                int temp_j_Sheep = arrayList.get(j).objState.sheep;
                int temp_j_Vegetable = arrayList.get(j).objState.vegetable;
                if (temp_i_Man != temp_j_Man && (Math.abs(temp_i_Wolf - temp_j_Wolf) +
                        Math.abs(temp_i_Sheep - temp_j_Sheep) +
                        Math.abs(temp_i_Vegetable - temp_j_Vegetable) <= 1)) {
                    // 满足两个条件:①man的状态不一样②有且仅有最多一个狼羊菜中的一个对象状态不一样
                    arr[i][j] = 1;          // 满足以上条件则满足连通性,置为1
                }
            }
        }


        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                System.out.printf("%2d", arr[i][j]);
            }
            System.out.println();   // 换行操作
        }

        visited[0] = 1;
        dfs(1, 10);         // 从第一个点找最后一个点
    }

    public static void dfs(int start, int end) {
        if (start == end) {
            print(end);    // 调用print()方法输出结果
            System.out.println();
        }

        for (int i = 0; i < 10; i++) {
            if (arr[start-1][i] > 0 && visited[i] == 0) {
                // 有边且没有被访问
                visited[i] = start;
                dfs(i+1, end);
                visited[i] = 0; // 回溯时置为0
            }
        }
    }

    public static void print(int end) {
        // 从最后往前遍历,然后正序输出
        int[] temp = new int[10]; // 保存了倒叙输出的顺序
        int num = 0;    // num表示要输出的个数
        int i = end;    // i表示当前是第几个数
        while (i != 1) {
            // 当i不是第一个数字时,则继续往前找
            temp[num] = visited[i - 1];
            i = temp[num];
            num++;      // num加1
        }
        for (int j = num - 1; j > 0; j--) {
            System.out.println(arrayList.get(temp[j] - 1).outputMessage);
        }
        // 输出最终状态
        System.out.println(arrayList.get(9).outputMessage);
    }
}

写在最后

因为平时都是在用为知笔记在记录这些学习笔记,所以想要直接腾写过来发现很费功夫,格式不太兼容,还正在想办法解决这种事...

欢迎转载,转载请注明出处!
简书ID:@我没有三颗心脏
github:wmyskxz
欢迎关注公众微信号:wmyskxz_javaweb
分享自己的Java Web学习之路以及各种Java学习资料

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,468评论 5 473
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,620评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,427评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,160评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,197评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,334评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,775评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,444评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,628评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,459评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,508评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,210评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,767评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,850评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,076评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,627评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,196评论 2 341

推荐阅读更多精彩内容

  • 一个农夫在河边,需要把狼、羊、菜和自己运到河对岸去,只有农夫能够划船,而且船比较小,除农夫之外每次只能运一种东西,...
    _阿南_阅读 1,638评论 1 0
  • 狼羊勿语(上篇) 她听过他的许多的故事。 他曾经撞死过头狼。 他无数次带领羊群度过数次危机。 他被誉为羊族...
    死神末翼阅读 1,118评论 9 8
  • 用二进制数 记录状态1 1 1 1 1A岸 狼 菜 羊 农...
    _弓长_大人阅读 4,050评论 0 1
  • 住院第21天,签字外出。 今天去广福寺烧香了。 告诉自己,自律,自重,做一个有用之人。 要相信自己,要感恩父母,感...
    白贝壳黑珍珠阅读 176评论 0 0