过桥问题是一个经典的逻辑谜题，也是算法面试中的常客。场景如下：夜晚，有四个人需要过一座桥，他们只有一只手电筒。桥每次最多容纳两人，且必须携带手电筒才能过桥。四个人的过桥时间分别为1分钟、2分钟、5分钟和10分钟。当两人一起过桥时，速度由较慢者决定。手电筒不能扔回，必须由某人带回来。问：四人全部过桥的最短总时间是多少？
直观上你可能认为答案显而易见，但最优解往往出人意料。本文将用Java实现过桥问题的通用求解器，讲解贪心策略的局限性，以及如何通过动态规划获得严格最优解。
问题分析：贪心为何可能失效
许多人首先想到的贪心策略是：让过桥最快的人（1分钟者）作为”摆渡人”，每次带一个人过桥并返回送手电筒。对于(1, 2, 5, 10)这个经典案例：
- 1和2过桥 → 2分钟
- 1返回 → 1分钟
- 1和5过桥 → 5分钟
- 1返回 → 1分钟
- 1和10过桥 → 10分钟
总时间 = 2 + 1 + 5 + 1 + 10 = 19分钟
但这并不是最优解！最优策略是：
- 1和2过桥 → 2分钟
- 1返回 → 1分钟
- 5和10过桥 → 10分钟
- 2返回 → 2分钟
- 1和2过桥 → 2分钟
总时间 = 2 + 1 + 10 + 2 + 2 = 17分钟
关键洞察是：让两个最慢的人一起过桥，虽然单次花费10分钟，但避免了分别由最快者陪同（5+10=15分钟）的更大开销。
状态表示：位掩码压缩
对于N个人的过桥问题，一个关键观察是：任意时刻，每个人要么在起始岸，要么在目标岸。因此可以用一个N位二进制数表示状态，第i位为1表示第i个人已过桥（在目标岸）。
/**
* 过桥问题求解器
* 使用位掩码表示状态，动态规划求解最优解
*/
public class BridgeCrossingSolver {
private final int[] times; // 每个人的过桥时间
private final int n; // 人数
private final int fullMask; // 全1掩码，表示所有人都已过桥
public BridgeCrossingSolver(int[] times) {
this.times = times.clone();
Arrays.sort(this.times); // 按过桥时间排序，方便处理
this.n = times.length;
this.fullMask = (1 << n) - 1;
}
动态规划状态转移
设 dp[mask] 表示从初始状态（所有人在起始岸）到状态 mask（mask中1表示已过桥的人）所需的最短时间。
由于手电筒可能在任意一岸，我们需要区分状态：设 dp[mask] 为手电筒在目标岸（即刚有人过桥到达）时，对应mask的最短时间。初始状态 dp[0] = 0。
状态转移有两种模式（假设手电筒在目标岸，即mask中1的人所在的一侧）：
-
模式A（最快者摆渡）：让目标岸最快的人带手电筒返回，然后起始岸选两人过桥。等价于从mask状态出发，选mask中的一个人返回，再选不在mask中的两人过桥。
-
模式B（次快者摆渡配合）：这是更巧妙的策略——起始岸最快的两人先过桥，最快者返回，目标岸最慢的两人过桥，次快者返回。这种策略在某些情况下优于模式A。
实际上，更简洁的DP思路是：设 dp[mask] 为手电筒在目标岸时的最短时间。要扩展状态，需要有人从目标岸带手电筒返回起始岸，然后起始岸选两人过桥。但由于状态数达到 2^N，对于N ≤ 15的情况完全可行。
/**
* 动态规划求解最优过桥时间
* dp[mask]：手电筒在目标岸，已过桥的人由mask表示时的最短时间
*/
public int solve() {
int[] dp = new int[1 << n];
Arrays.fill(dp, Integer.MAX_VALUE / 2);
dp[0] = 0; // 初始状态：无人过桥，手电筒在起始岸
// 使用BFS/DP按mask从小到大更新
for (int mask = 0; mask <= fullMask; mask++) {
if (dp[mask] == Integer.MAX_VALUE / 2) continue;
// 计算当前哪些人在起始岸（未过桥）
boolean[] onStart = new boolean[n];
for (int i = 0; i < n; i++) {
onStart[i] = (mask & (1 << i)) == 0;
}
// 手电筒在起始岸：选两人过桥 -> 到目标岸
// 或者手电筒在目标岸：选一人返回 -> 到起始岸
// 我们需要跟踪手电筒位置。简化：用dp[mask]表示手电筒在目标岸的最短时间
// 那么上一步一定是从起始岸两人过桥过来的
}
上面的思路有些混乱。让我采用更清晰的双状态DP：设 dp[mask][0] 为手电筒在起始岸的最短时间，dp[mask][1] 为手电筒在目标岸的最短时间。但这会浪费空间。
更好的方法：直接枚举每一步的具体操作。由于N很小，我们可以用记忆化搜索。
private int[][] memo;
/**
* 记忆化搜索
* @param mask 已过桥的人（在目标岸）
* @param torchAtGoal true表示手电筒在目标岸
* @return 从当前状态到全部过桥的最短剩余时间
*/
private int dfs(int mask, boolean torchAtGoal) {
if (mask == fullMask) return 0; // 所有人都已过桥
int key = mask | (torchAtGoal ? (1 << n) : 0);
if (memo[key] != -1) return memo[key];
int result = Integer.MAX_VALUE / 2;
if (torchAtGoal) {
// 手电筒在目标岸：选一人带手电筒返回起始岸
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) { // i已过桥
int newMask = mask ^ (1 << i);
result = Math.min(result, times[i] + dfs(newMask, false));
}
}
} else {
// 手电筒在起始岸：选两人带手电筒过桥到目标岸
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) continue; // i已过桥，不在起始岸
for (int j = i + 1; j < n; j++) {
if ((mask & (1 << j)) != 0) continue; // j已过桥
int newMask = mask | (1 << i) | (1 << j);
int crossTime = Math.max(times[i], times[j]);
result = Math.min(result, crossTime + dfs(newMask, true));
}
}
}
memo[key] = result;
return result;
}
完整求解器代码与路径重建
import java.util.*;
public class BridgeCrossingSolver {
private final int[] times;
private final int n;
private final int fullMask;
private int[][] memo;
public BridgeCrossingSolver(int[] times) {
this.times = times.clone();
Arrays.sort(this.times);
this.n = times.length;
this.fullMask = (1 << n) - 1;
}
public int solve() {
memo = new int[(1 << (n + 1))];
Arrays.fill(memo, -1);
return dfs(0, false);
}
private int dfs(int mask, boolean torchAtGoal) {
if (mask == fullMask) return 0;
int key = mask | (torchAtGoal ? (1 << n) : 0);
if (memo[key] != -1) return memo[key];
int result = Integer.MAX_VALUE / 2;
if (torchAtGoal) {
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
int newMask = mask ^ (1 << i);
result = Math.min(result, times[i] + dfs(newMask, false));
}
}
} else {
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) continue;
for (int j = i + 1; j < n; j++) {
if ((mask & (1 << j)) != 0) continue;
int newMask = mask | (1 << i) | (1 << j);
int crossTime = Math.max(times[i], times[j]);
result = Math.min(result, crossTime + dfs(newMask, true));
}
}
}
memo[key] = result;
return result;
}
/**
* 重建最优路径
*/
public List<String> getOptimalPath() {
List<String> path = new ArrayList<>();
int mask = 0;
boolean torchAtGoal = false;
int totalTime = 0;
while (mask != fullMask) {
int bestNext = -1;
int bestTime = Integer.MAX_VALUE / 2;
boolean nextTorch = !torchAtGoal;
if (torchAtGoal) {
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) == 0) continue;
int newMask = mask ^ (1 << i);
int candidate = times[i] + dfs(newMask, false);
if (candidate < bestTime) {
bestTime = candidate;
bestNext = i;
}
}
int newMask = mask ^ (1 << bestNext);
totalTime += times[bestNext];
path.add(String.format("%d号(%d分钟) 返回起始岸 [累计 %d分钟]",
bestNext + 1, times[bestNext], totalTime));
mask = newMask;
} else {
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) continue;
for (int j = i + 1; j < n; j++) {
if ((mask & (1 << j)) != 0) continue;
int newMask = mask | (1 << i) | (1 << j);
int crossTime = Math.max(times[i], times[j]);
int candidate = crossTime + dfs(newMask, true);
if (candidate < bestTime) {
bestTime = candidate;
bestNext = i | (j << 8);
}
}
}
int i = bestNext & 0xFF;
int j = (bestNext >> 8) & 0xFF;
int crossTime = Math.max(times[i], times[j]);
totalTime += crossTime;
path.add(String.format("%d号(%d分钟) 和 %d号(%d分钟) 过桥 -> %d分钟 [累计 %d分钟]",
i + 1, times[i], j + 1, times[j], crossTime, totalTime));
mask |= (1 << i) | (1 << j);
}
torchAtGoal = nextTorch;
}
return path;
}
public static void main(String[] args) {
int[] times = {1, 2, 5, 10};
BridgeCrossingSolver solver = new BridgeCrossingSolver(times);
int minTime = solver.solve();
System.out.println("最短过桥时间: " + minTime + " 分钟");
System.out.println("\n最优方案:");
for (String step : solver.getOptimalPath()) {
System.out.println(step);
}
}
}
贪心近似算法
对于人数较多的情况（N > 15），精确DP会因 2^N 的复杂度而失效。此时可以使用贪心策略获得近似解。核心思路是：每次让两个最慢的人过桥时，比较两种策略的开销，选择较小的：
- 策略1（最快者摆渡）：
t[0] + 2*t[1] + t[n-1] - 策略2（双慢同行）：
2*t[0] + t[n-2] + t[n-1]
/**
* 贪心近似算法，适用于大规模问题
*/
public int greedySolve() {
int[] t = times.clone();
Arrays.sort(t);
int total = 0;
int left = n;
while (left > 3) {
// 策略1: t[0]带t[n-1]过，t[0]回，t[0]带t[n-2]过，t[0]回
int strategy1 = t[0] + 2 * t[1] + t[left - 1];
// 策略2: t[0]带t[1]过，t[0]回，t[n-2]带t[n-1]过，t[1]回
int strategy2 = 2 * t[0] + t[left - 2] + t[left - 1];
total += Math.min(strategy1, strategy2);
left -= 2;
}
if (left == 3) {
total += t[0] + t[1] + t[2];
} else if (left == 2) {
total += t[1];
} else {
total += t[0];
}
return total;
}
复杂度分析
- 精确DP：时间复杂度 O(2^N × N^2)，空间复杂度 O(2^N)。适用于 N ≤ 20。
- 贪心近似：时间复杂度 O(N log N)，空间复杂度 O(1)。适用于大规模问题，对于经典案例(1,2,5,10)也能给出最优解17分钟。
总结
过桥问题深刻展示了贪心策略的陷阱：局部最优（每次让最快者返回）不一定导致全局最优。通过动态规划，我们可以系统地搜索所有可能的策略组合，找到严格的最优解。这个思想在任务调度、资源分配等领域有广泛应用。
