传教士和野人问题（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
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 个合法状态实际上是不可能达到的
因此实际的问题空
