人狼羊菜安全渡河问题

摘要

安全渡河问题又称作“人狼羊菜” 问题， 其具体描述为： 一个人带着一条狼、 一只羊、 一筐白菜过河但由于船太小， 人一次只能带一样东西乘船过河。 狼和羊、 羊和白菜不能单独留在同岸， 否则羊或白菜会被吃掉。 本文尝试应用运筹学中的图理论中的树知识来解决该问题。

问题分析

设图的顶点 v=（m， n， p， q）， m 表示人， n 代表狼， p 代表羊， q 代表白菜， 且m, n, p, q ∈{-1, 0, 1} , -1 代表此岸， 0 代表船上， 1 代表彼岸。 根据题意， 问题变成了 找出从顶点（-1， -1， -1， -1） 到顶点（1, 1, 1, 1） 路径（即是一棵以（-1， -1，-1， -1） 为根结点， （1, 1, 1, 1, ） 为叶子结点的树） 的问题。

通过分析问题知道：

顶点 v 必须满足以下条件：

1， 当 m≠0 时， n, p, q≠0 因为乘船时必须有人在上面;

2， 当 m≠p 时， n≠p, q≠p 即当人与羊不在一起时， 必羊和狼不在一起，羊和菜不在一起;

3, 当 n、 p、 q 中有一个为 0 时其余两个都不能为 0.

设相邻顶点 Vi=（m1， n1, p1, q1） , Vj=(m2, n2, p2, q2) . 设Tm=m2-m1, Tn=n2-n1, Tp=p2-p1, Tq=q2-q1, 易见 T∈(-1, 0, 1) ， 因为状态必须是渐变的， 不能逾越中间一个状态。

路径应该满足以下条件：

1， | Tm| ≠0， 即人前后的状态必须改变；

2， | Tn| +| Tp| +| Tq| =0 或=1， 因为最多仅能有一个物品随人转移， 可以为0 是因为允许人一个物品都不带；

3， 当| Tn| +| Tp| +| Tq| =1 时设状态改变的物品为 x， 必有 Tx=Tm， 因为物体状态的改变必是人状态改变的结果， 且与人的改变方向一致。

根据上述规则建立符合条件的树：

1， 用穷举法产生 81 个顶点；

2， 由顶点法则排除不合理点， 还剩 k 个可行点；

3， 用（-1， -1， -1， -1） 和（1， 1， 1， 1） 分别作为根结点和叶子结点；

4， 用路径法则选取正确点： 从（-1， -1， -1， -1） 为起点开始从剩下的k-1-1 个可行顶点中找到合理点， 再以此点为新的起点从剩下的 k-1-1-1 个可行点中按路径法则找合理点. . . . . . 以此类推找到最后一个合理点为（1， 1， 1， 1）。

参考文献

[1]郭强， 孙浩.运筹学原理与算法[M]西安:西北工业大学出版社， 2006.

[2]严蔚敏,吴伟民.数据结构[M].北京： 清华大学出版社， 2002.

[3]俞涛.“船运狼， 羊， 菜” 问题的新解法[J].河北师范大学学报:自然科学版， 1996,20（4）： 27-29.

[4]王家华,王祥波， 李美丽， 曹春祥， 王晓燕.安全渡河问题的图解新法[J].西安石油大学学报:自然科学版，22-4,2007,7