传教士与食人族：岸上不能让食人族占优

题目

3 名传教士和 3 名食人族要到对岸，只有一条船，每次最多载 2 人。约束：任何一岸，若食人族人数多于传教士（且传教士人数 >0），传教士就会被吃。如何全员安全过河？

答案与解析

这是经典的**传教士与食人族（Missionaries and Cannibals）**状态搜索题。记 $(m,c,b)$ 为左岸传教士、食人族数及船在左(1)/右(0)。合法状态要求每岸 $c\le m$ 或 $m=0$。

一种 11 步解法（去6回5）：

1. 2 食人族过 → 右有(0,2)
2. 1 食人族回
3. 2 食人族过
4. 1 食人族回（右岸剩 3 食人族，左岸 3 传教士）
5. 2 传教士过
6. 1 传教士+1 食人族回
7. 2 传教士过（左剩0传教，右3传教3食人中的…）继续 8–11. 用食人族把船摆渡，逐步运回剩余食人族。

最终 11 次渡河全员抵达，且每步都满足约束。

背后的数学

与狼羊菜同属状态空间 BFS 问题，但约束更密，状态图更丰富。它是人工智能早期（1950–60 年代）检验规划与搜索算法的标准基准，也是“安全性和不变式约束”教学的起点——现代多智能体调度、机器人编队避碰，逻辑骨架与此一脉相承。