vc++算法，狼羊白菜问题

1 先把羊从左岸带到右岸

2 当农夫回到左岸，带着白菜过去

3 当农夫把白菜带到右岸后,同时把羊带回左岸(因为这时羊会吃白菜必须带回)

4 当农夫把羊带回左岸后，同时把狼带到右岸(同上理带到右岸后狼不吃白菜)

5 当农夫把狼带到右岸后，回到左岸，把羊再带过来

设目的地为南 另一端为北

先把羊从北岸运到南岸，此时北岸剩狼和草，

然后人自行驾船回北岸，将草运装船运到南岸

到南岸之后将草卸下，载上羊返回北岸

到北岸卸下羊 装上狼，将狼载上运到南岸

到南岸卸下，此时南岸剩狼和草

空载驾船到北岸 装上羊 返回南岸

用0表示在左岸,1表示在右岸

用顶点序号的二进制码的0位表示农夫,1位表示狼,2位表示羊,3位表示菜

那么,总共可能有16个顶点0-15顶点0表示全在左岸,顶点15表示全在右岸

当然有些顶点是不允许存在的,比如顶点3,表示农夫和狼在右岸,羊和菜在左岸,羊会吃掉菜你要把所有这类的顶点去掉

在剩下的顶点中,你要找出所有的可能的边比如顶点5表示农夫和羊在右,狼和菜在左,顶点4表示羊在右,那么就存在顶点5到顶点4的有向边

至此,图已构造完毕,问题就转换成找到一条从顶点0到顶点15的合理路径

解：该问题可以使用图论中的最短路算法进行求解。

我们可以用四维向量来表示状态，其中第一分量表示人，第二分量表示狼，第三分量表

示羊，第四分量表示蔬菜；当人或物在此岸时相应分量取1，在对岸时则取0。

根据题意，人不在场时，狼要吃羊，羊要吃菜，因此，人不在场时，不能将狼与羊，羊

与蔬菜留在河的任一岸。例如，状态（0，1，1，0）表示人和菜在对岸，而狼和羊在此岸，

这时人不在场的情况下狼要吃羊，因此，这个状态是不可行的。

我们通过穷举法将所有可行的状态列举出来，可行的状态有

（1，1，1，1），（1，1，1，0），（1，1，0，1），（1，0，1，1），（1，0，1，0）

（0，1，0，1），（0，1，0，0），（0，0，1，0），（0，0，0，1），（0，0，0，0）

可行状态共有十种。每一次的渡河行为改变现有的状态。现构造赋权图G = (V, E,W) ，

其中集合V 中的顶点表示十个可行状态，当且仅当对应的两个可行状态之间存在一个可行

转移时两顶点之间才有线连接，并且对应的权重取为1，当两个顶点之间不存在可行转移时，

可以把相应的权重取为∞ 。

因此问题变为在图G 中寻找一条由初始状态（1，1，1，1）出发，经最小次数转移达到

最终状态（0，0，0，0）的转移过程，即求从状态（1，1，1，1）到状态（0，0，0，0）的

最短路径。这就将问题转化成了图论中的最短路问题。

下面首先计算邻接矩阵，由于摆渡一次就改变现有的状态，为此再引入一个四维状态转

移向量，用它来反映摆渡情况。用1 表示过河，0 表示未过河。例如，（1，1，0，0）表示

人带狗过河。状态转移只有四种情况，用如下的向量表示。

（1，0，0，0），（1，1，0，0），（1，0，1，0），（1，0，0，1）

现在规定状态向量与转移向量之间的运算为

0 + 0 =1，1+ 0 =1 ， 0 +1 =1 ，1+1 =1

通过上面的定义，如果某一个可行状态加上转移向量得到的新向量还属于可行状态，则这两

个可行状态对应的顶点之间就存在一条边。用计算机编程时，我们可以利用普通的向量运算

与模2 运算实现。

源程序联系我 我发给你

以上就是关于vc++算法，狼羊白菜问题全部的内容，包括:vc++算法，狼羊白菜问题、数学建模，人狼羊草过河问题、农夫狼羊过河图论等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！