传教士与野人问题是经典的AI搜索问题。3名传教士和3名野人要过河，只有一条船，船最多容纳2人。在任何岸边，如果野人数量多于传教士，传教士就会被吃掉。我们需要找到让所有6人安全过河的最少步数方案。
问题建模
将问题抽象为状态空间搜索：
– 状态用三元组 (M, C, B) 表示，其中 M 为左岸传教士数，C 为左岸野人数，B 为船位置（0左岸/1右岸）
– 初始状态：(3, 3, 0)，目标状态：(0, 0, 1)
– 每次船移动，可以载 1~2 人（至少1人划船）
– 约束条件：任何岸边野人不得多于传教士（除非传教士为0）
核心算法：BFS状态空间搜索
使用BFS遍历所有合法状态，保证找到最短路径。每个状态记录前驱状态以便回溯路径。
import java.util.*;
/**
* 传教士与野人问题求解器
* 使用BFS状态空间搜索找到最短安全过河方案
*/
public class MissionariesAndCannibals {
// 状态类，记录当前局面
static class State {
int m; // 左岸传教士数
int c; // 左岸野人数
int boat; // 船位置：0=左岸，1=右岸
State parent; // 前驱状态，用于回溯路径
String action; // 本次移动描述
State(int m, int c, int boat, State parent, String action) {
this.m = m;
this.c = c;
this.boat = boat;
this.parent = parent;
this.action = action;
}
// 状态唯一标识，用于判重
String key() {
return m + "," + c + "," + boat;
}
}
private final int totalM; // 传教士总数
private final int totalC; // 野人总数
private final int boatCap; // 船容量
public MissionariesAndCannibals(int m, int c, int cap) {
this.totalM = m;
this.totalC = c;
this.boatCap = cap;
}
/**
* 检查状态是否安全：任何岸边野人不得多于传教士（传教士为0除外）
*/
private boolean isValid(int leftM, int leftC) {
int rightM = totalM - leftM;
int rightC = totalC - leftC;
// 左岸安全：传教士为0 或 传教士 >= 野人
if (leftM > 0 && leftC > leftM) return false;
// 右岸安全
if (rightM > 0 && rightC > rightM) return false;
return true;
}
/**
* BFS搜索最短过河方案
*/
public List<String> solve() {
Queue<State> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
State start = new State(totalM, totalC, 0, null, "初始状态：全部在左岸");
queue.offer(start);
visited.add(start.key());
// 船可行的载客方案：(传教士数, 野人数)
int[][] moves = generateMoves();
while (!queue.isEmpty()) {
State cur = queue.poll();
// 到达目标状态
if (cur.m == 0 && cur.c == 0 && cur.boat == 1) {
return buildPath(cur);
}
// 尝试所有可行的移动
for (int[] move : moves) {
int dm = move[0]; // 传教士移动数
int dc = move[1]; // 野人移动数
State next;
if (cur.boat == 0) {
// 船在左岸，载人去右岸
next = new State(cur.m - dm, cur.c - dc, 1, cur,
String.format("%d传教士+%d野人 左->右", dm, dc));
} else {
// 船在右岸，载人回左岸
next = new State(cur.m + dm, cur.c + dc, 0, cur,
String.format("%d传教士+%d野人 右->左", dm, dc));
}
// 边界检查与安全性检查
if (next.m < 0 || next.m > totalM) continue;
if (next.c < 0 || next.c > totalC) continue;
if (!isValid(next.m, next.c)) continue;
if (visited.contains(next.key())) continue;
visited.add(next.key());
queue.offer(next);
}
}
return Collections.emptyList(); // 无解
}
/**
* 生成所有可行的船上载客方案
*/
private int[][] generateMoves() {
List<int[]> list = new ArrayList<>();
for (int dm = 0; dm <= boatCap; dm++) {
for (int dc = 0; dc <= boatCap; dc++) {
if (dm + dc >= 1 && dm + dc <= boatCap) {
list.add(new int[]{dm, dc});
}
}
}
return list.toArray(new int[0][]);
}
/**
* 从目标状态回溯到起点，构建路径
*/
private List<String> buildPath(State target) {
LinkedList<String> path = new LinkedList<>();
State cur = target;
while (cur != null) {
path.addFirst(String.format("[%d missionary, %d cannibal, boat=%s] -> %s",
cur.m, cur.c, cur.boat == 0 ? "左" : "右", cur.action));
cur = cur.parent;
}
return path;
}
public static void main(String[] args) {
MissionariesAndCannibals solver = new MissionariesAndCannibals(3, 3, 2);
List<String> solution = solver.solve();
System.out.println("=== 传教士与野人问题求解 ===");
if (solution.isEmpty()) {
System.out.println("无解！");
} else {
System.out.println("最短方案需 " + (solution.size() - 1) + " 次渡河：");
for (String step : solution) {
System.out.println(step);
}
}
}
}
复杂度分析
- 时间复杂度：
O(S)，其中S为合法状态总数。对于(M, C, B)三元组，最多(M+1)(C+1)*2个状态。本例中最多4*4*2 = 32个状态，BFS在极短时间内完成。 - 空间复杂度：
O(S)，用于存储已访问状态集合和BFS队列。 - 状态剪枝：通过安全性约束（两岸传教士不得被野人超过）和访问判重，有效剪除大量非法状态。
扩展思考
- 若传教士与野人数量不等，或船容量变化，只需调整参数即可复用算法。
- 可改用A*搜索，设计启发函数（如两岸总人数/船容量）加速搜索。
- 状态空间可扩展至更多经典过河问题，如狼羊菜问题。
总结
本文通过BFS状态空间搜索解决传教士与野人问题，展示了如何将逻辑谜题转化为图搜索问题。核心在于正确的状态编码、合法性约束判定以及路径回溯机制。
