摆渡过河分析
摆渡过河
问题重述:
是山羊和卷心菜,都不能在无人监视的情况下留在一起。问摆渡人应怎样把它们运过河去
问题分析:
由题意知人划船一次只能运三者之一或者自己独自划船,且无论在河的左岸还是右岸都要保证无人情况下狼和山羊,山羊和卷心菜不能单独在一起。在这里,羊所受的限制条件是最多的,所以羊只能独处或在船上被带走,因此,
A:人首先只能把山羊带去河的对岸(右岸),将山羊放在右岸;
B:人自己回来,可以带狼过去也可以带卷心菜过去,若带卷心菜去对岸, 因为卷心菜不能与山羊在一起,所以人回来时要将山羊再带回左岸;
C:人将山羊留在左岸,带狼去对岸,将狼放在右岸;
D:人自己回来再将山羊带去对岸。
用图论方法:对于人,狼,山羊,卷心菜的位置状态,可用1表示在左岸,用0表示不在左岸,则由无人情况下狼和山羊,山羊和卷心菜不能单独在一起,列出可以存在的状态如下表:
状态点 名字 | 人 | 狼 | 山羊 | 卷心菜 |
A | 1 | 1 | 1 | 1 |
B | 0 | 1 | 0 | 1 |
C | 1 | 1 | 0 | 1 |
D | 0 | 1 | 0 | 0 |
E | 左岸右岸1 | 1 | 1 | 0 |
F | 0 | 0 | 1 | 0 |
G | 1 | 0 | 1 | 0 |
H | 1 | 0 | 1 | 1 |
I | 0 | 0 | 0 | 1 |
J | 0 | 0 | 0 | 0 |
注释:
A表示人,狼,山羊,卷心菜都在河的左岸;
B表示狼和卷心菜在河的左岸,人和山羊在河的对岸(右岸)
将上表中各种状态作为顶点,将两个可以转变的状态点之间连一条有向边,可得到下图
摆渡人把他们运过河去,最优方案是从上面有向图中到一条从A点到J 点的最短路径。即ABCIHFGJ或者ABCDEFGJ.
发布评论