温鸿航，温鸿翔，任晓莉

(1.西安电子科技大学通信工程学院，陕西西安 710071;2.陕西广电网络(集团)有限公司，陕西西安 710075;3.西安交通大学城市学院，陕西西安 710018)

“渡河问题”作为人们熟知的经典趣味性智力题目之一，在各种智能训练、测试和数学建模比赛中常会遇到［1］。而对其进行较为深入的一般性系统讨论尚不多见。文献［2］虽对此作了较详细的讨论，给出了应用计算机进行智能求解的方法;但该方法对数学要求较高，不利于教学普及。见于此，文中在文献［1］的启发下，应用简单直观的图解法对渡河问题作初步探讨，以期为编拟该类智能题目提供参考依据以及求解的思路。

1 渡河问题两种常见的描述

为利于今后讨论的一致性，先将渡河问题简述如下(括号内的“或m”、”或n”用于作一般性讨论时来替代前面的具体数字):

问题1 传教士与食人族渡河问题。

在河流的左岸现有3位(或m位)传教士和3个(或m个)食人族，他们欲利用左岸边最多可乘坐2人(或n人)的小舟渡到河右岸去。假设每个人都会划船;其限制是:无论是在左岸、船上还是右岸的场合下，都不得出现食人族人数多于传教士数目的不安全情况，因这样可能发生食人族攻击传教士的危险。

问题2 阿拉伯夫妇渡河问题。

即有3对阿拉伯夫妇欲利用能载客2人的小船从河左岸过渡到右岸去，已知每个人都会划船。其限制是:按照习俗任一位妻子都不得在其丈夫不在场陪伴的场合下与别的男子碰面。

上述表述中各有两个限制(约束条件):