一个人带着狼山羊白菜在一条河的左岸

人、狼、羊、菜安全渡河问题安全渡河问题又称作“人狼羊菜”问题，其具体描述为：一个人带着一条狼、一只羊、一筐白菜过河但由于船太小，人一次只能带一样东西乘船过河。

狼和羊、羊和白菜不能单独留在同岸，否则羊或白菜会被吃掉。

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

问题分析根据题意，人不在场时，狼要吃羊，羊要吃菜，因此，人不在场时，不能将狼与羊、羊与菜留在河的任一岸。

可用四维向量v=（m，n，p，q）来表示状态，m表示人，n代表狼，p代表羊，q代表白菜，且m,n,p,q ∈{0,1},0代表在对岸，1代表在此岸。

例如，状态（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={v1,…, v10}中的顶点（按照上面的顺序编号）分别表示上述１０个可行状态，当且仅当对应的两个可行状态之间存在一个可行转移时两顶点之间才有边连接，并且对应的权重取为１，当两个顶点之间不存在可行转移时，可以把相应的权重取为∞。

因此问题变为在图Ｇ中寻找一条由初始状态（１,１,１,１）出发，经最小次数转移到达最终状态（０,０,０,０）的转移过程，即求从状态（１,１,１,１）到状态（０,０,０,０）的最短路径。

该问题难点在于计算邻接矩阵，由于摆渡一次就改变现有状态，为此再引入一个四维状态转移向量，用它来反映摆渡情况。

用１表示过河，０表示未过河。

例如，（１,１,０,０）表示人带狼过河。

状态转移只有四种情况，用如下向量表示：（１,０,０,０），（１,１,０,０），（１,０,１,０），（１,０,０,１）现在规定状态向量与转移向量之间的运算为0+0=0,1+0=1,0+1=1,1+1=0通过上面的定义，如果某一个可行状态加上转移向量得到的新向量还属于可行状态，则这两个可行状态对应的顶点之间就存在一条边。

第4章搜索策略部分参考答案有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右岸，但受到下列条件的限制：(1) 船太小，农夫每次只能带一样东西过河；(2)如果没有农夫看管，则狼要吃羊，羊要吃菜。

请设计一个过河方案，使得农夫、浪、羊都能不受损失的过河，画出相应的状态空间图。

题示：(1) 用四元组（农夫，狼，羊，菜）表示状态，其中每个元素都为0或1，用0表示在左岸，用1表示在右岸。

(2) 把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只有他可以划船。

解：第一步，定义问题的描述形式用四元组S=（f，w，s，v）表示问题状态，其中，f，w，s和v分别表示农夫，狼，羊和青菜是否在左岸，它们都可以取1或0，取1表示在左岸，取0表示在右岸。

第二步，用所定义的问题状态表示方式，把所有可能的问题状态表示出来，包括问题的初始状态和目标状态。

由于状态变量有4个，每个状态变量都有2种取值，因此有以下16种可能的状态：S0=(1,1,1,1)，S1=(1,1,1,0)，S2=(1,1,0,1)，S3=(1,1,0,0)S4=(1,0,1,1)，S5=(1,0,1,0)，S6=(1,0,0,1)，S7=(1,0,0,0)S8=(0,1,1,1)，S9=(0,1,1,0)，S10=(0,1,0,1)，S11=(0,1,0,0)S12=(0,0,1,1)，S13=(0,0,1,0)，S14=(0,0,0,1)，S15=(0,0,0,0)其中，状态S3，S6，S7，S8，S9，S12是不合法状态，S0和S15分别是初始状态和目标状态。

第三步，定义操作，即用于状态变换的算符组F由于每次过河船上都必须有农夫，且除农夫外船上只能载狼，羊和菜中的一种，故算符定义如下：L(i)表示农夫从左岸将第i样东西送到右岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。

由于农夫必须在船上，故对农夫的表示省略。

农夫过河——狼⽺菜问题
话说⼀位农夫带着⼀只狼、⼀只⽺和⼀个卷⼼菜过河，⽆奈船⼩，农夫每次只能运送⼀样东西，考虑到狼吃⽺、⽺吃菜，因此运送的顺序⾄关重要。

在现实世界⾥解决这个问题并不困难，相信很多⼈都已经有了答案，但是如何⽤程序来解决这⼀问题，就需要动动脑筋了。

这⼜是⼀个与移动物品有关的问题，在前⾯汉诺塔的例⼦中，我们已经领略了解决这类问题的⽅法，⼤致分为三个步骤：
1. 将现实问题转化为数学问题，即，建⽴模型；
2. 将数学问题转化为程序问题，即，给出数据结构及算法；
3. 编写程序解决问题。

下⾯我们就沿着这样的思路来寻找问题的答案。

阅读原⽂。

人狼羊菜安全渡河问题摘要安全渡河问题又称作“人狼羊菜” 问题，其具体描述为：一个人带着一条狼、一只羊、一筐白菜过河但由于船太小，人一次只能带一样东西乘船过河。

狼和羊、羊和白菜不能单独留在同岸，否则羊或白菜会被吃掉。

本文尝试应用运筹学中的图理论中的树知识来解决该问题。

问题分析设图的顶点 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）。

农夫、狼、⽺、菜问题【题⽬说明】⼀个农夫带着⼀只狼，牵着⼀只⽺，挑着⼀担菜去赶集，前⾯有⼀条河拦住了他，河边有⼀艘船但船太⼩⼀次只能载农夫和他所带的其中⼀种东西，农夫知道狼会吃⽺`⽺也会吃他所带的菜要在都不被吃的情况下农夫怎么过去？【思路】如果⽤⼀个四元组(Farmer,Wolf,Sheep,Veget)表⽰当前农夫、狼、⽺和菜所处的位置，其中每个元素可以是0或者1,0表⽰在左岸，1表⽰在右岸。

这样对四个元素的不同取值可以构成16种不同的状态，初始时的状态为(0,0,0,0),最终要到达的⽬标为(1,1,1,1).状态之间可以转换有下⾯四种情况：【程序代码】1 #include <stdio.h>2#define VEX_NUM 10 //最⼤顶点数3 typedef enum {FALSE, TRUE} Boolean;45//定义图的顶点类型6 typedef struct7 {8int Farmer, Wolf, Sheep, Veget;9 }VexType;1011 typedef struct12 {13int vexnum, e; //图当前顶点数和边数14 VexType vexs[VEX_NUM]; //顶点向量15int adj[VEX_NUM][VEX_NUM]; //邻接矩阵16 }AdjGraph;1718 Boolean visited[VEX_NUM];19int path[VEX_NUM];2021//查找顶点(F, W, S, V)在顶点向量中的位置22int locate(AdjGraph * G, int F, int W, int S, int V)23 {24int i;25for(i = 0; i < G->vexnum; i++)26if(G->vexs[i].Farmer == F && G->vexs[i].Sheep == S && G->vexs[i].Veget == V && G->vexs[i].Wolf == W)27return (i);28return -1;29 }3031//判断状态(F, W, S, V)是否安全32int is_safe(int F, int W, int S, int V)33 {34if(F != S && (W == S || S == V))35return0;36else37return1;38 }3940//检查第i个状态和第j个状态之间是否可以转换41int is_connected(AdjGraph * G, int i, int j)42 {43int k;44 k = 0;45if(G->vexs[i].Wolf != G->vexs[j].Wolf)46 k++;47if(G->vexs[i].Sheep != G->vexs[j].Sheep)48 k++;49if(G->vexs[i].Veget != G->vexs[j].Veget)50 k++;51if(G->vexs[i].Farmer != G->vexs[j].Farmer && k <= 1)52return1;53else54return0;55 }5657//创建邻接矩阵58void CreateG(AdjGraph *G)59 {60int i, j, F, W, S, V;61 i = 0;6263//形成所有的安全结点64for(F = 0; F <= 1; F++)65for(W = 0; W <= 1; W++)66for(S = 0; S <=1; S++)67for(V = 0; V <= 1; V++)68if(is_safe(F, W, S, V))69 {70 G->vexs[i].Farmer = F;71 G->vexs[i].Wolf = W;72 G->vexs[i].Sheep = S;73 G->vexs[i].Veget = V;74 i++;75 }76 G->vexnum = i;77for(i = 0; i < G->vexnum; i++)78for(j = 0; j < G->vexnum; j++)79if(is_connected(G, i, j))80 G->adj[i][j] = G->adj[j][i] = 1;81else82 G->adj[i][j] = G->adj[j][i] = 0;83return;84 }8586//输出u到v的简单路径87void print_path(AdjGraph * G, int u, int v)88 {89int k;90 k = u;91while(k != v)92 {93 printf("(%d,%d,%d,%d)\n", G->vexs[k].Farmer, G->vexs[k].Wolf, G->vexs[k].Sheep, G->vexs[k].Veget);94 k = path[k];95 }96 printf("(%d,%d,%d,%d)\n", G->vexs[k].Farmer, G->vexs[k].Wolf, G->vexs[k].Sheep, G->vexs[k].Veget);97 }9899//求u到v的简单路径100void DFS_path(AdjGraph* G, int u, int v)101 {102int j;103 visited[u] = TRUE;104for(j = 0; j < G->vexnum; j++)105if(G->adj[u][j] && !visited[j] && !visited[v])106 {107 path[u] = j;108 DFS_path(G, j, v);109 }110 }111112void main()113 {114int i, j;115 AdjGraph graph;116 CreateG(&graph);117for(i = 0; i < graph.vexnum; i++)118 visited[i] = FALSE;119 i = locate(&graph, 0, 0, 0, 0);120 j = locate(&graph, 1, 1, 1, 1);121 DFS_path(&graph, i, j);122if(visited[j])123 print_path(&graph, i, j);124125return;126 }View Code。

一道题过河救羊
这个题目是这样的：有一个人带着一只狼、一只羊、一棵白菜来到河边（我们假设狼是不吃人的）。

河边正好有一条空着的小船，渡河时，船很小只能允许主人带一样东西，如果带两样东西上船，船就会沉下去。

另一方面，如果没人照管，狼会吃掉羊，羊又会啃白菜，所以，狼与羊、羊与白菜在主人不在的情况下，是不能放在一起的。

问主人应当采取什么样的过河方案，才能把狼、羊、白菜都安全地带到对岸去呢？
这个问题的正确答案是这样的。

主人先带羊过河，因为狼不吃白菜，然后空船返回。

第二次带狼过河，到对岸后放下狼，带羊返回。

将羊放在此岸上后，把白菜带过河，然后空船返回。

第四次把岸上的羊带过河。

这时，主人把狼、羊、白菜都带过了河，可以继续走路了。