传教士和野人问题（Missionaries and Cannibals） 传教士和野人问题是一个经典的智力游戏问题。在这个问题中，实际上隐含了这样一个条件：如果在河的某一岸只有野人，而没有传教士，也同样被认为是合法状态。在具体书写某些条件时，为了简便，这一点有时并没有考虑，但我们默认这个条件是被考虑了的。 有 N 个传教士和N 个野人来到河边准备渡河，河岸有一条船，每次至多可供 k人乘渡。问传教士为了安全起见，应如何规划摆渡方案，使得任何时刻，在河的两岸以及船上的野人数目总是不超过传教士的数目。即求解传教士和野人从左岸全部摆渡到右岸的过程中，任何时刻满足 M（传教士数）≥ C（野人数）和M＋C≤ k 的摆渡方案。 设 N＝3，k＝2，则给定的问题可用图 1.2表示，图中 L 和R 表示左岸和右岸，B＝1或 0 分别表示有船或无船。约束条件是：两岸上 M≥ C，船上 M＋C≤ 2。 图1.2 M－C 问题实例 由于传教士和野人数是一个常数，所以知道了一岸的情况，另一岸的情况也就知道了。因此为了简便起见，在描述问题时，只描述一岸--如左岸--的情况就可以了。 另外，该问题我们最关心的是在摆渡过程中，两岸状态的变化情况，因此船上的情况并不需要直接表达出来。在一次摆渡过程中，船上究竟有几个传教士和野人，可以通过两个相连的状态简单得到。这样表达更简练，突出了问题的重点。 （1）综合数据库：用三元组表示左岸的情况，即 （，，），其中0≤，≤3，∈{0，1}，其中表示在左岸的传教士人数，表示在左岸的野人数，＝1 表示船在左岸，＝0 表示船在右岸。则此时问题描述可以简化为： （3，3，1）→ （0，0，0） N＝3的M－C问题，状态空间的总状态数为4×4×2＝32，根据约束条件的要求，可以看出只有20 个合法状态。再进一步分析后，又发现有4 个合法状态实际上是不可能达到的。因此实际的问题空间仅由16 个状态构成。下表列出分析的结果： （ ） （ 0 0 1）达不到（传教士（ ） （ 0 0 0） 均在右，船在左） （ 0 1 1 ） （ 0 2 1 ） （ 0 3 1 ） （ 1 0 1 ）不合法（右岸野人多） （ 1 1 1 ） （ 1 2 1 ）不合法（左岸野人多） （ 1 3 1 ）不合法（左岸野人多） （ 2 0 1 ）不合法（右岸野人多） （ 2 1 1 ）不合法（右岸野人多） （ 2 2 1 ） （ 2 3 1 ）不合法（左岸野人多） （ 3 0 1 ）达不到 （ 3 1 1 ） （ 3 2 1 ）...
