人、狼、羊、菜安全渡河问题摘要安全渡河问题又称作“人狼羊菜”问题，其具体描述为：一个人带着一条狼、一只羊、一筐白菜过河但由于船太小，人一次只能带一样东西乘船过河。狼和羊、羊和白菜不能单独留在同岸，否则羊或白菜会被吃掉。本文尝试应用运筹学中的图理论中的树知识来解决该问题。问题分析设图的顶点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-1-1-1）（0，-1,0，-1）（1，-1,1，-1）（0，-1,1，-1）（0,0,1，-1）（1,1,1，-1）(0,1,0,-1)(-1,1,-1,-1)(0,1-1,0)(0,-1,1,0)(1,-1,1,1)(0,-1,0,1)(-1,-1,-1,1)(0,0,-1,1)(1,1,-1,1)(0,1,-1,1)(-1,1,-1,1)(0,1,0,1)(1,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