狼羊菜过河问题深入学习分析——Java语言描述版
狼羊菜过河问题深入学习分析——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);
}
}写在最后
因为平时都是在用为知笔记在记录这些学习笔记，所以想要直接腾写过来发现很费功夫，格式不太兼容，还正在想办法解决这种事...