八人过河
八人过河问题详解（java语言求解）
在秋招面试搜狗大数据开发岗位的时候，面试官给出了一个八个人过河的问题，后来自己查了之后发现这个是经典过河问题的一个变型。
网上也有其他求解这个问题的方法和代码。他们大多数是把所有的状态看作一个图数据，用矩阵表示，有的还需要提前把安全的状态判断出来，需要手动处理一些数据。我写的这个方法，不需要手动处理任何数据，直接就能运行出结果，最后为了更直观的展示，还会打印出找到的路径。
问题描述：
现在有八个人需要划船到河的对面去。
8个人分别为：
1个父亲，带着2个儿子
1个母亲，带着2个女儿
1个警察带着1个犯人
开始时，8个人都是在左岸
四条规则：
- 只有警察、父母可以划船，其他人不可以
- 警察离开犯人，犯人就会伤害其他人
- 母亲不在时，父亲会伤害女儿；父亲不在时，母亲会伤害儿子。（这不是一家的）
- 船上一次最多只能坐两个人。
求出过河方案
分析:
每个人的状态有三种：左岸、船上、右岸。
其实这就是一个状态转移的问题。令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
- 检查状态是否安全。不安全的话，则不能继续往下搜索。
- 防止状态循环。如果当前到达的状态已经出现过了，则不能在继续往下搜索，否则会出现状态循环问题的。
求解问题的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