温鸿航，任晓莉，温鸿翔

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

渡河问题的一般性描述是:有m个传教士与m个食人族欲利用最多载客n人的小船从河左岸过渡到右岸去，设每个人都会划船，要求其过程中在河两岸及船上均不得出现食人族人数多于传教士数目的情况，以免发生传教士受到攻击的危险。这类题目在数值较小时因其解路径较短，常常经逻辑推理及简单计算即可解得［1］。但考虑到将来可能应用于规划、管理等领域时，处理的数值较大，解路径变长，求解过程将趋于复杂化，且其中亦常含有智能搜索，需要借助于计算机来处理［2］。为此就有必要构建适当的数学表达方式及算法。基于此，提出了用岸态矩阵来表示求解过程中河岸上的人员组合状态，并引入表征船上人员的摆渡算子，采用迭代法来探寻由初始岸态逐步导向目标岸态的解路径。从而为应用计算机处理此类问题提供一种思路。

1 岸态矩阵及其构成

提出的岸态矩阵，是用于表征问题求解过程中任一时刻处于河流两岸的人员组合状态的。设:某一时刻滞留于河左岸的传教士和食人族的人数分别为x和y，同一时刻位于河右岸的传教士和食人族人数分别为x′和 y′;显然这里的 x、y 和 x′、y′都应为大等于零的整数。于是可以构造如下的岸态矩阵Sk

式(1)中第一行为河流左岸的人员组合状态向量(x，y)，第二行为同一时刻河右岸的人员组合状态向量(x′，y′);而矩阵的第一列为传教士在河流左右两岸的分布情况，第二列是此时食人族在左右两岸的分布。……