如何通过编程来解决农夫过河问题?

关于农夫过河问题,想必大家都听说过,这样我就不细讲了,如果没有听说那就百度一下。这个问题曾经困扰我很长世间,自己一直想通过编程的方法解决,不过都没成功。后来一段时间自己就没怎么放在心上了,直到最近突然想起来这个问题。 自己也想了一个思路,就是分别将河两岸的“货物”看作两个集合,农夫的往返相当于两个集合之间进行差集、并集运算。但是的话,有些运算是无法进行的,比如你将兔子运过去后,不能立刻运回来(不…
关注者
60
被浏览
2821

4 个回答

首先,有四样“货物”,人,狼,羊,白菜。因此在左岸,可能有16种状态,我们可以用一个二进制数来表示,比如 1111b表示都在左岸,0110b 表示狼和羊在左岸。显然当左岸为sate时,右岸为15-state(如果在船上,我们也算在右岸)。这里要明确状态的意义。

下面就是构造状态转移矩阵。
在这一步,我们要弄清楚一个状态,可能变为哪些状态。如果两个状态可以互相转换,我们就将矩阵对应的位置设为1。
先考虑人不在左岸,也就是state<8的情况,下一时刻,可能有哪些状态呢?
显然下一时刻,必然是船从右侧过来,船上有人,还可能有另外一个在右岸的货物。
注意我们可以只考虑左岸没有人的状态,因为左岸与右岸是相反的。
#define HUMAN_BIT   8
#define WOLF_BIT    4
#define SHEEP_BIT   2
#define CABBAGE_BIT 1

#define HUMAN(state)    ((state) & HUMAN_BIT)
#define WOLF(state)     ((state) & WOLF_BIT)
#define SHEEP(state)    ((state) & SHEEP_BIT)
#define CABBAGE(state)  ((state) & CABBAGE_BIT)

int matrix[16][16] = {0};

void CreateStateTransitionMatrix()
{
    for(int i=0; i<8; i++)
    {
        int j = i | HUMAN_BIT;
        matrix[i][j]       = matrix[j][i] = 1;
        if (!WOLF(i))       matrix[i][j|WOLF_BIT]       = matrix[j|WOLF_BIT][i] = 1;
        if (!SHEEP(i))      matrix[i][j|SHEEP_BIT]      = matrix[j|SHEEP_BIT][i] = 1;
        if (!CABBAGE(i))    matrix[i][j|CABBAGE_BIT]    = matrix[j|CABBAGE_BIT][i] = 1;
    }
}
这实际上就是一个图的邻接矩阵,每个状态就是图的一个结点。我们可以画出来看看
H表示人 W为狼 S为羊 C为白菜。均表示左岸的状态。
比如 人带着羊过河,那么就由 H W S C变为 W C.

但是要注意,因为狼不能和羊在一起,羊不能和白菜在一起,也就是说 0110 0011 0111以及它们的补数,是无效的状态,是不能达到的,因此要把这些状态去掉。
void RemoveOneInvalidState(int state)
{
    for(int i=0; i<16; i++)
    {
        matrix[i][state] = matrix[state][i] = 0;
        matrix[i][15-state] = matrix[15-state][i] = 0;
    }
}

void RemoveInvalidState()
{
    // 人不在时,狼羊不能共存,羊菜不能共存,狼羊菜也不能共存
    // 即 0110 0011 0111 三种为无效状态
    RemoveOneInvalidState(6);
    RemoveOneInvalidState(3);
    RemoveOneInvalidState(7);
}
此时的邻接矩阵为
现在的问题就是找一条路径从 H W S C 到 NULL。这就是一个图的搜索问题了。