怎样将一头狼、一只羊和一篮白菜带过河

一位农夫带着一头狼、一只羊和一篮白菜过河。河边有一条船，但船上除了撑船的农夫以外，最多只能多放一件东西。如果农夫不在现场的话，狼会吃掉羊，而羊会吃掉白菜。农夫怎么才能将狼、羊和白菜都带过河呢？

要解决这种智力问题，最直接的方法就是不断尝试，但如果方法不适当的话，很容易在少数几种情况中不断兜圈。为了避免这种情况，我们需要进行系统全面的思考。

首先，假设农夫要带着东西从左岸来到右岸，因为船只能由农夫来撑，所以我们可以将农夫和船绑定。农夫、狼、羊和白菜要么在左岸，要么在右岸，他们之间可能出现的状态最多有24=16种组合。因为在没有农夫看管的情况下，狼和羊、羊和白菜不能留在岸的一边，扣去这种不应该出现的情况，只剩下如图所示的10种状态。

我们的目标是把所有东西从左岸带到右岸，也就是说从第一种状态（称为状态I）转换到最后一种状态（称为状态F）。农夫每次划船到对岸，都会使状态发生变化。如果农夫从某种状态A出发划船到对岸，能达到某种状态B的话，我们就在图上画一个从A指向B的箭头，意思是从状态A可以到达状态B。农夫每次只能带至多一种东西到对岸，所以我们可以轻易枚举出从A出发的所有箭头，也就是说从A出发通过农夫一次渡河可以到达的状态。这样，我们就得到如右图所示的状态图：

因为箭头表示了状态之间所有可能的转换，要找到从状态I到状态F的转换方法，也就是要找到沿着箭头方向从I到F的一条路径，这在图上一目了然。一种可能的路径是：农夫把羊带到对岸，自己返回；再把白菜带到对岸，将羊带回来；然后将狼带到对岸，自己返回；最后将羊带到对岸。在图上，这对应着（I→A→B→H→J→E→G→F）的路径。

事实上这道智力题有更简单的解法。我们注意到，因为农夫每次只能带一样东西，所以会出现将两种东西没有看管地放在同一边岸上的情况，而唯一允许的搭配就是狼和白菜。通过这种巧妙的观察，我们可以更快地得到答案。但状态图的方法更具有系统性和一般性，能解决更多类似的问题。

农夫渡河状态图

通过状态图，我们可以有效地表示状态之间的关系，并找到如何在状态之间转移的方法。在计算机科学中，特别是在系统设计、安全协议设计方面，状态图有着广泛的应用。另外，状态图可以表示一种被称为“有限自动机”的对象，而有限自动机在计算机科学中有着非常基础的地位。

另一方面，经过适当扩充的状态图是博弈论的基础工具之一。博弈论属于应用数学的分支，它主要研究多个个体之间的博弈，其中包括石头、剪子、布，井字棋甚至国际象棋等对抗性的游戏，也包含合作性的游戏。在博弈论中，经常使用状态图来表示一个游戏，将游戏的所有可能局面看成游戏的状态，将游戏参与者的行动看成状态的转移。通过游戏的状态图，就可以计算出相当一部分游戏的最优策略，因此状态图也是博弈论的重要研究方法之一。（方弦）

【实验场】夫妇过河

有三对夫妇要过河，河边只有一条仅能承载两人的小船。因为丈夫们的妒忌心很重，在自己不在场的情况下，他们不允许自己的妻子和其他男人单独待在一起。你能用状态图的方法找到一个让所有人过河的方法吗？

【微问题】如果有5个砝码，你能称出多少种重量？6个呢？

【关键词】状态图　砝码　最优策略