江民钦的博客

show me code

算法学习笔记-妖怪与和尚过河问题

有三个和尚（或传教士）和三个妖怪（或食人怪）过河，只有一条能装下两个人（和尚或妖怪）的船，在河的任何一方或者船上，如果妖怪的人数大于和尚的人数，那么和尚就会有被吃掉的危险。你能不能找出一种安全的渡河方法呢？

这是一个很有意思的智力题，但是并不难，每次可以选择一个人或者两个人过河，只要保证河的任何一边的和尚数量总是大于或等于妖怪的数量即可。这里先给出一种过河方法：

两个妖怪先过河，一个妖怪回来；

再两个妖怪过河，一个妖怪回来；

两个和尚过河，一个妖怪和一个和尚回来；

两个和尚过河，一个妖怪回来；

两个妖怪过河，一个妖怪回来；

两个妖怪过河。

总共要过河11次

过河的方法其实不止这一种，本文给出了一种求解全部过河方法的算法程序，可以通过穷举（状态树搜索）的方法得到全部四种过河方法。

解决问题的思路

题目的初始条件是三个和尚和三个妖怪在河的一边（还有一条船），解决问题后的终止条件是三个和尚和三个妖怪安全地过到河的对岸，如果把任意时刻妖怪和和尚的位置看作一个“状态”，则解决问题就是找到一条从初始状态变换到终止状态的路径。从初始状态开始，每选择一批妖怪或和尚过河（移动一次小船），就会从原状态产生一个新的状态，如果以人类思维解决这个问题，每次都会选择最佳的妖怪与和尚组合过河，使得它们过河后生成的新状态更接近最终状态，不断重复上述过程，直到得到最终状态。
用计算机解决妖怪与和尚过河问题的思路也是通过状态转换，找到一条从初始状态到结束状态的转换路径。计算机不会进行理性分析，不知道每次如何选择最佳的过河方式，但是计算机擅长快速计算且不知疲劳，既然不知道如何选择过河方式，那就干脆把所有的过河方式都尝试一遍，找出所有可能的结果，当然也就包括成功过河的结果。

c++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream> 
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
//抽象过河状态 
struct State{
    int local_monk=3;
    int local_monster=3;
    int remote_monk=0;
    int remote_monster=0;
    int i_boat=0;
};
int c=0;  //计算次数 
int m=999;
int boat=0;   //船的位置 0在原岸 1在对岸 
int action[10][3]={{0,-1,0},{0,-2,0},{0,0,-1},{0,0,-2},{0,-1,-1},{1,1,0},{1,2,0},{1,0,1},{1,0,2},{1,1,1}};  //定义行动数组 
vector<State> vi;
//打印结果
void printResullt(){
    cout<<endl;
    for(int i=0;i<vi.size();i++){
        State s=vi[i];
        cout<<s.i_boat<<"     "<<s.local_monk<<"  "<<s.local_monster<<"  "<<s.remote_monk<<"   "<<s.remote_monster<<endl;
    }
    cout<<endl;
}
bool isFinalState(State state){
    if(state.local_monk==0 && state.local_monster==0 && state.remote_monk==3 && state.remote_monster==3){
        printResullt();     //输出结果集合里边的所有状态 
        if(c<m){
            m=c;
        }
        return true;
    }else{
        return false;
    }
}
bool isEffective(State state){
    if((state.local_monk>=state.local_monster && state.remote_monk>=state.remote_monster) || state.local_monk==0 || state.remote_monk==0){
        return true;
    }else{
        return false;
    }
}
bool isEmpty(State st){
    int n=0;
    for(int i=0;i<vi.size();i++){
        State s=vi[i];
        if(s.local_monk==st.local_monk && s.local_monster==st.local_monster && s.remote_monk==st.remote_monk && s.remote_monster==st.remote_monster && s.i_boat==st.i_boat){
            n++;
        }
    }
    if(n>=2){
        return true;
    }
    return false;
}
void search(){
    State state=vi.back();
    if(isEmpty(state) && vi.size()>1){
        return;
    }
    if(isFinalState(state)){
        return;
    }
    for(int i=0;i<10;i++){
        state=vi.back();
        if(action[i][0]==boat){
            if((boat==0 && state.local_monk>=abs(action[i][1]) && state.local_monster>=abs(action[i][2])) || (boat==1 && state.remote_monk>=abs(action[i][1]) && state.remote_monster>=abs(action[i][2]))){
                state.local_monk+=action[i][1];
                state.local_monster+=action[i][2];
                state.remote_monk-=action[i][1];
                state.remote_monster-=action[i][2];
                
                    if(isEffective(state)){
                        boat=(++boat)%2;
                        state.i_boat=boat;
                        vi.push_back(state);
                        c++;
                        search();
                        vi.pop_back();
                        boat=(++boat)%2;
                        c--;
                    }
                
            }
        }
    }
}
int main(){
    State state;
    vi.push_back(state);
    search();
    cout<<"最少过河次数为："<<m<<endl;
}

在这道题中，过河这种动作共有5种动作，加上船在不同的两岸，所以需要乘2，一共10种情况。可利用深度优先进行遍历每一种状态生产状态树，不过由于深度优先可能会陷入状态回路中，所以需要从每次加入状态的集合里边判断是否有相同状态，对了，值得注意的是，船的状态也要判断，由于本人之前没判断船的状态，结果一直陷入调BUG中。

算法状态树