问题描述
过河问题是经典的算法教学案例：一位农夫需要带着狼、羊和白菜过河。船上只能容纳农夫和一件物品。如果农夫不在场，狼会吃羊，羊会吃白菜。如何设计一个安全的过河方案？
本文将这一问题抽象为状态空间搜索问题，使用BFS（广度优先搜索）寻找最短可行解，并通过安全性约束判定确保每一步都不会导致物品被吃掉。
核心算法思路
状态表示
用四位二进制数表示状态，每一位分别代表农夫、狼、羊、白菜是否在起始岸（1）或对岸（0）。例如状态 1111 表示所有角色都在起始岸，0000 表示全部到达对岸。
安全性约束
一个状态是安全的，当且仅当不满足以下任一条件：
– 狼和羊在同一岸，且农夫不在该岸
– 羊和白菜在同一岸，且农夫不在该岸
BFS搜索
从初始状态 1111 出发，枚举农夫可以携带的物品（不携带、狼、羊、白菜），生成所有合法的新状态，使用BFS逐层扩展直到到达目标状态 0000。记录每个状态的前驱状态以重构路径。
Java实现
import java.util.*;
/**
* 过河问题求解器
* 使用BFS状态空间搜索寻找最短安全过河方案
*/
public class RiverCrossingSolver {
// 状态位定义：农夫(3)、狼(2)、羊(1)、白菜(0)
private static final int FARMER = 3;
private static final int WOLF = 2;
private static final int SHEEP = 1;
private static final int CABBAGE = 0;
// 角色名称映射
private static final String[] NAMES = {"白菜", "羊", "狼", "农夫"};
/**
* 判断当前状态是否安全
* @param state 4位二进制状态
* @return 安全返回true
*/
public boolean isSafe(int state) {
boolean farmerHere = ((state >> FARMER) & 1) == 1;
boolean wolfHere = ((state >> WOLF) & 1) == 1;
boolean sheepHere = ((state >> SHEEP) & 1) == 1;
boolean cabbageHere = ((state >> CABBAGE) & 1) == 1;
// 农夫不在此岸时，检查危险组合
if (!farmerHere) {
// 狼和羊单独在一起
if (wolfHere && sheepHere) return false;
// 羊和白菜单独在一起
if (sheepHere && cabbageHere) return false;
}
// 检查对岸（农夫不在对岸时）
boolean farmerThere = !farmerHere;
boolean wolfThere = !wolfHere;
boolean sheepThere = !sheepHere;
boolean cabbageThere = !cabbageHere;
if (!farmerThere) {
if (wolfThere && sheepThere) return false;
if (sheepThere && cabbageThere) return false;
}
return true;
}
/**
* 获取农夫可以携带的物品列表
* @param state 当前状态
* @return 可携带物品的位掩码列表
*/
public List<Integer> getPossibleMoves(int state) {
List<Integer> moves = new ArrayList<>();
boolean farmerHere = ((state >> FARMER) & 1) == 1;
// 农夫可以单独过河
moves.add(0);
// 检查其他角色是否与农夫同岸
for (int item = 0; item <= 2; item++) {
boolean itemHere = ((state >> item) & 1) == 1;
if (itemHere == farmerHere) {
moves.add(1 << item);
}
}
return moves;
}
/**
* 执行状态转移
* @param state 当前状态
* @param move 携带的物品掩码
* @return 新状态
*/
public int applyMove(int state, int move) {
// 农夫和携带的物品都翻转状态
int newState = state ^ (1 << FARMER);
if (move != 0) {
// 找到move中唯一的1的位
for (int i = 0; i <= 2; i++) {
if ((move & (1 << i)) != 0) {
newState ^= (1 << i);
break;
}
}
}
return newState;
}
/**
* BFS搜索最短过河方案
* @return 状态转移路径，无解返回空列表
*/
public List<int[]> solve() {
int start = 0b1111; // 15
int goal = 0b0000; // 0
if (!isSafe(start)) return new ArrayList<>();
Queue<Integer> queue = new LinkedList<>();
Map<Integer, Integer> parent = new HashMap<>();
Map<Integer, Integer> parentMove = new HashMap<>();
Set<Integer> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
parent.put(start, -1);
parentMove.put(start, -1);
while (!queue.isEmpty()) {
int current = queue.poll();
if (current == goal) {
return reconstructPath(parent, parentMove, current);
}
for (int move : getPossibleMoves(current)) {
int next = applyMove(current, move);
if (!visited.contains(next) && isSafe(next)) {
visited.add(next);
parent.put(next, current);
parentMove.put(next, move);
queue.offer(next);
}
}
}
return new ArrayList<>(); // 无解
}
/**
* 重构路径
*/
private List<int[]> reconstructPath(Map<Integer, Integer> parent,
Map<Integer, Integer> parentMove,
int goal) {
List<int[]> path = new ArrayList<>();
int current = goal;
while (current != -1) {
int move = parentMove.getOrDefault(current, -1);
path.add(new int[]{current, move});
current = parent.getOrDefault(current, -1);
}
Collections.reverse(path);
return path;
}
/**
* 打印路径
*/
public void printSolution(List<int[]> path) {
if (path.isEmpty()) {
System.out.println("无解！");
return;
}
System.out.println("=== 过河方案 ===");
for (int i = 0; i < path.size(); i++) {
int[] step = path.get(i);
int state = step[0];
int move = step[1];
System.out.printf("步骤 %d: ", i);
printState(state);
if (i < path.size() - 1) {
System.out.print(" -> 携带: ");
if (move == 0) {
System.out.println("农夫独自过河");
} else {
for (int j = 0; j <= 2; j++) {
if ((move & (1 << j)) != 0) {
System.out.println(NAMES[j]);
break;
}
}
}
}
}
System.out.println("\n总共需要 " + (path.size() - 1) + " 次渡河");
}
private void printState(int state) {
StringBuilder here = new StringBuilder("起始岸: [");
StringBuilder there = new StringBuilder("对岸: [");
for (int i = 3; i >= 0; i--) {
boolean isHere = ((state >> i) & 1) == 1;
if (isHere) {
if (here.length() > 5) here.append(", ");
here.append(NAMES[i]);
} else {
if (there.length() > 4) there.append(", ");
there.append(NAMES[i]);
}
}
here.append("]");
there.append("]");
System.out.println(here + " | " + there);
}
public static void main(String[] args) {
RiverCrossingSolver solver = new RiverCrossingSolver();
List<int[]> path = solver.solve();
solver.printSolution(path);
}
}
算法复杂度分析
- 时间复杂度：$O(2^n)$，其中 $n=4$ 为角色数量。实际搜索空间远小于 $2^4=16$，因为安全性约束剪枝了大量非法状态。
- 空间复杂度：$O(2^n)$，用于存储访问标记和前驱状态。
扩展思考
- 通用化：若有 $n$ 个角色和 $m$ 组危险关系，可将问题建模为图论中的独立集问题，状态空间会指数级增长。
- 最优性：BFS保证找到步数最少的解。若需要最小化运输成本，可将BFS替换为Dijkstra算法。
- 双向BFS：对于更大规模的状态空间，可从起始状态和目标状态同时搜索，降低时间复杂度。
总结
过河问题将现实场景抽象为状态空间搜索模型，通过BFS系统性地探索所有合法状态转移，安全性约束作为剪枝条件有效缩小了搜索范围。这种建模方法可广泛应用于路径规划、调度优化和博弈求解等领域。
