引言
过河问题（Bridge and Torch / Missionaries and Cannibals）是经典的约束满足与状态空间搜索问题。在漆黑的夜晚，若干人需要借助唯一的手电筒过桥，桥每次最多承载两人，且必须有人携带手电筒。不同的人过桥速度不同，两人同行时以较慢者速度为准。目标是让所有人安全过桥，且总耗时最短。
本文将用 Java 完整实现过河问题的 BFS 状态空间搜索，讲解状态表示、约束检查、最优解回溯等核心算法。
问题建模
状态表示
用二进制位表示每个人在桥的哪一侧：
– 0 表示在起始岸
– 1 表示在对岸
状态还需要记录手电筒位置（0 或 1），以及已用时间。
状态 = (人员位置位掩码, 手电筒位置, 已用时间)
约束条件
- 每次移动必须携带手电筒
- 每次最多移动 1~2 人
- 总时间最小化
核心算法：BFS + 优先队列
由于需要求最短时间，使用 Dijkstra 风格的优先队列 BFS：
– 每次取出当前时间最短的状态
– 尝试所有合法的人员移动组合
– 用访问集合去重
完整 Java 实现
import java.util.*;
/**
* 过河问题求解器
* 经典约束满足问题：多人在限定条件下过桥，求最短时间
*/
public class BridgeCrossingSolver {
// 每个人的过桥时间（分钟）
private final int[] crossingTimes;
private final int n;
public BridgeCrossingSolver(int[] crossingTimes) {
this.crossingTimes = crossingTimes.clone();
this.n = crossingTimes.length;
Arrays.sort(this.crossingTimes); // 排序便于处理
}
/**
* 状态类：记录人员位置、手电筒位置、已用时间
*/
static class State implements Comparable<State> {
// 位掩码：第i位为1表示第i个人在对岸
int mask;
// 手电筒位置：0=起始岸，1=对岸
int torch;
// 已用总时间
int time;
// 前驱状态（用于回溯路径）
State prev;
// 本次移动的人员列表
List<Integer> moved;
State(int mask, int torch, int time) {
this.mask = mask;
this.torch = torch;
this.time = time;
}
@Override
public int compareTo(State other) {
return Integer.compare(this.time, other.time);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof State)) return false;
State state = (State) o;
return mask == state.mask && torch == state.torch;
}
@Override
public int hashCode() {
return Objects.hash(mask, torch);
}
}
/**
* 使用优先队列BFS求解最短时间
* 时间复杂度: O(2^n * n^2)，空间复杂度: O(2^n)
*/
public Result solve() {
// 优先队列：按已用时间排序（Dijkstra）
PriorityQueue<State> pq = new PriorityQueue<>();
// 访问集合：记录(mask, torch)的最小时间
Map<String, Integer> visited = new HashMap<>();
// 初始状态：所有人都在起始岸，手电筒在起始岸，时间=0
State start = new State(0, 0, 0);
pq.offer(start);
visited.put(key(0, 0), 0);
while (!pq.isEmpty()) {
State cur = pq.poll();
// 终止条件：所有人都在对岸
if (cur.mask == (1 << n) - 1 && cur.torch == 1) {
return buildResult(cur);
}
// 如果当前状态不是最优，跳过
String k = key(cur.mask, cur.torch);
if (visited.get(k) < cur.time) continue;
// 生成所有合法移动
List<State> nextStates = generateMoves(cur);
for (State next : nextStates) {
String nk = key(next.mask, next.torch);
Integer existing = visited.get(nk);
if (existing == null || next.time < existing) {
visited.put(nk, next.time);
pq.offer(next);
}
}
}
return null; // 无解（理论上不会发生）
}
/**
* 从当前状态生成所有合法下一步状态
*/
private List<State> generateMoves(State cur) {
List<State> moves = new ArrayList<>();
// 手电筒在哪侧，就从哪侧选人过桥
int side = cur.torch;
// 找出在手电筒所在侧的所有人员
List<Integer> peopleOnSide = new ArrayList<>();
for (int i = 0; i < n; i++) {
int personSide = (cur.mask >> i) & 1;
if (personSide == side) {
peopleOnSide.add(i);
}
}
// 尝试所有1人或2人组合
int size = peopleOnSide.size();
for (int i = 0; i < size; i++) {
// 1人过桥
int p1 = peopleOnSide.get(i);
addMove(moves, cur, List.of(p1), crossingTimes[p1]);
// 2人过桥
for (int j = i + 1; j < size; j++) {
int p2 = peopleOnSide.get(j);
int cost = Math.max(crossingTimes[p1], crossingTimes[p2]);
addMove(moves, cur, List.of(p1, p2), cost);
}
}
return moves;
}
private void addMove(List<State> moves, State cur, List<Integer> people, int cost) {
int newMask = cur.mask;
for (int p : people) {
// 翻转该人员的位置
newMask ^= (1 << p);
}
int newTorch = 1 - cur.torch; // 手电筒移动到另一侧
int newTime = cur.time + cost;
State next = new State(newMask, newTorch, newTime);
next.prev = cur;
next.moved = new ArrayList<>(people);
moves.add(next);
}
private String key(int mask, int torch) {
return mask + "," + torch;
}
/**
* 从终止状态回溯构建结果
*/
private Result buildResult(State end) {
List<Step> steps = new ArrayList<>();
Deque<State> stack = new ArrayDeque<>();
// 回溯到起点
State cur = end;
while (cur != null) {
stack.push(cur);
cur = cur.prev;
}
// 构建步骤列表
State prev = null;
while (!stack.isEmpty()) {
cur = stack.pop();
if (prev != null && cur.moved != null) {
String direction = cur.torch == 1 ? "→" : "←";
List<String> names = new ArrayList<>();
for (int p : cur.moved) {
names.add("P" + p + "(" + crossingTimes[p] + "min)");
}
steps.add(new Step(direction, names, cur.time - prev.time, cur.time));
}
prev = cur;
}
return new Result(end.time, steps);
}
/**
* 结果类
*/
static class Result {
final int totalTime;
final List<Step> steps;
Result(int totalTime, List<Step> steps) {
this.totalTime = totalTime;
this.steps = steps;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("最短总时间: ").append(totalTime).append(" 分钟\n");
sb.append("详细步骤:\n");
for (int i = 0; i < steps.size(); i++) {
Step s = steps.get(i);
sb.append(String.format("%d. %s %s, 耗时=%dmin, 累计=%dmin\n",
i + 1, s.direction, String.join(", ", s.people), s.cost, s.cumulative));
}
return sb.toString();
}
}
static class Step {
final String direction;
final List<String> people;
final int cost;
final int cumulative;
Step(String direction, List<String> people, int cost, int cumulative) {
this.direction = direction;
this.people = people;
this.cost = cost;
this.cumulative = cumulative;
}
}
public static void main(String[] args) {
// 经典问题：4人过桥，时间分别为1, 2, 5, 10 分钟
// 最优解：17分钟
int[] times1 = {1, 2, 5, 10};
BridgeCrossingSolver solver1 = new BridgeCrossingSolver(times1);
Result result1 = solver1.solve();
System.out.println("=== 经典4人问题 ===");
System.out.println(result1);
// 5人过桥问题
int[] times2 = {1, 2, 5, 10, 12};
BridgeCrossingSolver solver2 = new BridgeCrossingSolver(times2);
Result result2 = solver2.solve();
System.out.println("\n=== 5人问题 ===");
System.out.println(result2);
// 6人过桥问题
int[] times3 = {1, 2, 5, 10, 12, 15};
BridgeCrossingSolver solver3 = new BridgeCrossingSolver(times3);
Result result3 = solver3.solve();
System.out.println("\n=== 6人问题 ===");
System.out.println(result3);
}
}
算法解析
状态空间分析
对于 n 个人，每个人有 2 种位置，手电筒有 2 种位置，总状态数为 n * 2^(n+1)。当 n=4 时仅 128 个状态，BFS 可以轻松处理。
为什么用 Dijkstra 而不是普通 BFS
普通 BFS 适用于无权图的最短路径。过河问题中，每条边（每次过桥）的”权重”不同（取决于谁过桥），因此需要用优先队列维护按时间排序的状态，这就是 Dijkstra 算法的核心思想。
最优性证明
优先队列保证每次扩展的都是当前时间最短的状态。当第一次到达目标状态时，其时间必然是最小的——这与 Dijkstra 算法的最优性证明完全一致。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(2^n × n²) | 状态数 × 每状态转移数 |
| 空间复杂度 | O(2^n) | 访问集合与优先队列 |
| 实际性能 | n≤10 毫秒级 | 状态空间随 n 指数增长 |
扩展思考
- 传教士与野人问题：增加约束（任何一侧野人不超过传教士），只需在状态转移时增加约束检查即可。
- 多桥问题：如果有多个桥，状态空间扩展为多维。
- A* 优化：使用启发函数（如剩余最慢者过桥时间的下界）加速搜索。
总结
过河问题完美展示了状态空间搜索的范式：定义状态 → 确定转移规则 → 添加约束 → 选择搜索策略 → 回溯最优解。掌握这一框架，可解决绝大多数组合优化类问题。
