[科普中国]-摆渡问题

摆渡问题(ferry problem)是一类组合优化问题，在一条河的一边岸上有一只狼、一只羊和一棵白菜，已知狼吃羊和羊吃白菜，在河中只有一条小舟且每次只能载它们三者之一，问如何用最少的次数将它们安全摆渡到对岸?这就是所谓摆渡问题，也可将它推广到一般的情形1。

基本介绍中世纪，英国数学家阿尔昆(Alcuin，735-804)在其《益智集》(Problems for the Quickening of the Mind)中提出：有人携带一只狼、一只羊、一篮白菜渡河。唯一的工具是一条小船。小船一次只能载他自己和三样东两中的一样。如果只留下羊和白菜在一起，羊就会吃掉白菜；如果留下羊和狼在一起，狼就会吃掉羊。问这个人如何安排摆渡，方能使白菜、羊和狼都平安抵达对岸?

可以利用路径的概念解此问题。

解：河左岸允许出现的情况有以下10种情况：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及窄(各物品已安全渡河)。把这10种状态视为10个点，若一种状态通过一次摆渡后变为另一种状态，则在两种状态(点)之间画一直线，得到图1。

这样摆渡问题就转化成在图中找出以“人狼羊菜”为起点，以“空”为终点的简单路径。容易看出，只有两条简单路径符合要求，即

(1)人狼羊菜、狼菜、人狼菜、菜、人羊菜、羊、人羊、空：

(2)人狼羊菜、狼菜、人狼菜、狼、人狼羊、羊、人羊、空。

对于简单路径(1)的安排为：人带羊过河；人刚来；带狼过河；放下狼再将羊带回；人再带菜过河；人回来；带羊过河。

对于简单路径(2)的安排为：人带羊过河；人回来；带菜过河；放下菜再将羊带回；人再带狼过河；人回来；带羊过河。

上述的两种方案都是去4次、回3次，且不会再有比这更少次数的渡河办法了2。

摆渡问题的推广与变形16世纪，意大利数学家塔塔格里亚(N.Tartaglia，1499-1557)将摆渡问题设计成一个新版本3：

三位美丽的新娘和她们爱吃醋的先生一同旅行。他们来到了一条河边，但只有一条小船，小船一次至多只能载二人。为了避免有人吃醋，他们约定：除非自己的先生在身旁，否则任一女士不得和其他男子在一起。问怎样安排渡河?

答案是往返1 1次。如果只有两对夫妇，则往返5次就够了；如果有四对或更多对夫妇，那么问题无解。该问题后来又被推广成：

(1)n对夫妻用一条船过河，该船仅可由一人来划，至多可载 个人，条件仍是任一女士除非自己的先生在身旁，否则不得和其他男子在一起。问至少需要往返几次?(设摆渡次数为y，则 时， ； 时， ； 时， 。)

(2)问一条船至少能载几个(X)人时，才能使11对夫妻可乘它渡河，而任一女士除非自己的先生在身边，否则不得和别的男子在一起；假设船仅可由一人来划。并求往返摆渡的最小次数(y)。结果见表1。

|| || 表1 摆渡问题的解

与摆渡问题相类似的是火车转轨问题。图2中有一火车头L和两节货车车厢 ，DA是 所在侧线的公共部分，长度足够停放 ，但不能同时容下这两节车厢，也容小下火车头L。这样，停在DA上的车厢可以转轨到侧线上。工程师的工作是转换 的位置。问如何完成?这个问题并不难，但如果有更多的车厢(如在铁路货物分类站)，要按车厢目的地先后顺序进行排列，那么__：I二程师就需要有很高的数学水平才能完成职责了3。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所