青蛙过河是一个规则简单却极难心算的益智游戏：一排石头横跨水面，青蛙们按规则跳跃交换位置，目标是把左岸的青蛙全都搬到右岸。它的搜索空间随石头数量指数增长，朴素的 BFS 在 15 块石头时就会吃掉数 GB 内存。本文用 Java 实现分支限界搜索（Branch and Bound），核心是设计一个真正有效下界函数，配合状态压缩与等价状态归并，把问题规模压到可计算范围。
一、游戏建模：把”跳跃”变成整数向量
经典青蛙过河（也叫青蛙换位，Frog Jump）的规则是：左右两侧各有一组青蛙，中间是石头阵。操作者可以把一只青蛙跳到相邻空石，或者跳过一只青蛙落到空石。目标是把左岸的青蛙全部移到右岸，右岸的全部移到左岸。
把它抽象成一行格子序列更利于算法处理。约定用 0 表示空位，1 表示左岸青蛙，2 表示右岸青蛙（也可看作”左向”和”右向”两种生物）。一步操作是：
- 将某只青蛙移入相邻空位（代价 1）
- 将某只青蛙跳过一只异类青蛙落到空位（代价 1）
在一维序列上，这个规则等价于”青蛙与空位交换位置”，或”青蛙跳过一只反向青蛙与空位交换位置”。所有移动代价均为 1，所以问题是一个无权最短路问题。
/**
* 青蛙过河状态：用 byte 数组编码
* 0 = 空位, 1 = 左向青蛙(向右移动), 2 = 右向青蛙(向左移动)
*/
public class FrogState {
private final byte[] cells;
private final int length;
public FrogState(byte[] cells) {
this.cells = cells.clone();
this.length = cells.length;
}
public static FrogState initial(int pairs) {
// 形如 1 1 1 0 2 2 2：左侧 pairs 只右向青蛙，中间一个空位，右侧 pairs 只左向青蛙
byte[] s = new byte[pairs * 2 + 1];
for (int i = 0; i < pairs; i++) {
s[i] = 1;
}
s[pairs] = 0;
for (int i = pairs + 1; i < s.length; i++) {
s[i] = 2;
}
return new FrogState(s);
}
public static FrogState target(int pairs) {
byte[] s = new byte[pairs * 2 + 1];
for (int i = 0; i < pairs; i++) {
s[i] = 2;
}
s[pairs] = 0;
for (int i = pairs + 1; i < s.length; i++) {
s[i] = 1;
}
return new FrogState(s);
}
/** 生成所有合法后继状态：青蛙跳入相邻空位，或跳过一只异类青蛙落入空位 */
public java.util.List<FrogState> successors() {
java.util.List<FrogState> res = new java.util.ArrayList<>();
for (int i = 0; i < length; i++) {
byte v = cells[i];
if (v == 0) {
continue;
}
int dir = (v == 1) ? 1 : -1; // 1 向右，2 向左
// 相邻空位：直接移动
int j = i + dir;
if (j >= 0 && j < length && cells[j] == 0) {
res.add(swapped(i, j));
}
// 跳一格：跨过一只异类青蛙落到空位
int k = i + 2 * dir;
if (k >= 0 && k < length && cells[k] == 0) {
byte mid = cells[i + dir];
if (mid != 0 && mid != v) {
res.add(swapped(i, k));
}
}
}
return res;
}
private FrogState swapped(int a, int b) {
byte[] copy = cells.clone();
byte tmp = copy[a];
copy[a] = copy[b];
copy[b] = tmp;
return new FrogState(copy);
}
/** 用于去重的 key：每个格子 2 bit，压成一个 long */
public long key() {
long k = 0;
for (int i = 0; i < length; i++) {
k |= ((long) cells[i]) << (2 * i);
}
return k;
}
public boolean isTarget(int pairs) {
return key() == target(pairs).key();
}
public byte[] cells() {
return cells.clone();
}
}
每个格子只需 2 bit（三种取值），所以长度 31 以内的状态可以完整压进一个 long，这是后续用哈希表去重的前提。长度超过 31 时需要改用 BitSet 或字符串 key，实现方式不变。
二、BFS 的极限在哪
先用 BFS 摸清难度。BFS 找到的一定是最优解，可以作为分支限界的正确性基准：
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
/**
* 标准 BFS：用于小规模基准测试与最优解验证
*/
public class FrogBfs {
public int solve(int pairs) {
FrogState start = FrogState.initial(pairs);
FrogState goal = FrogState.target(pairs);
Deque<FrogState> queue = new ArrayDeque<>();
Map<Long, Integer> dist = new HashMap<>();
queue.add(start);
dist.put(start.key(), 0);
while (!queue.isEmpty()) {
FrogState cur = queue.poll();
int d = dist.get(cur.key());
if (cur.isTarget(pairs)) {
return d;
}
for (FrogState nxt : cur.successors()) {
if (!dist.containsKey(nxt.key())) {
dist.put(nxt.key(), d + 1);
queue.add(nxt);
}
}
}
return -1;
}
public static void main(String[] args) {
for (int p = 1; p <= 8; p++) {
long t0 = System.currentTimeMillis();
int steps = new FrogBfs().solve(p);
long t1 = System.currentTimeMillis();
System.out.printf("pairs=%d 最优步数=%d 耗时=%dms%n", p, steps, t1 - t0);
}
}
}
运行结果会呈现一个很漂亮的规律：pairs=1 到 8 的最优步数是 3, 8, 15, 24, 35, 48, 63, 80，即 pairs*(pairs+2)。这是一个经典结论，但注意它只对”两侧青蛙数相等且中间恰有一个空位”的标准布局成立。一旦改动布局（比如空位放在最外侧、或者两侧数量不等），公式立刻失效，必须靠搜索求解。
当 pairs=8 时，BFS 已需处理数十万状态；pairs=12 时内存会迅速膨胀到 GB 级。这就是引入分支限界的动机。
三、下界函数设计：让剪枝真正有效
分支限界的效果完全取决于下界函数的质量。下界必须满足两个条件：一是可采纳（真实代价不小于下界，否则会剪掉最优解），二是尽可能紧（下界越接近真实值，剪枝越激进）。
对青蛙过河，有两个可采纳下界可以叠加：
下界一：错位青蛙数。 每只不在目标位置的青蛙至少要移动一次，所以”位置不对的青蛙数量”是合法下界。
下界二：空位约束。 每一步只能移动一只青蛙，而任何时刻只有一个空位，因此至少需要与错位青蛙数量相同的步数才能把它们全部归位。这与下界一同源，但更强的一个推论是：如果中间空位不在目标位置，最后一步必须把它移回去。
更强的下界来自”跳与走的区分”。设需要向左移动的青蛙中有 x 只，向右移动的有 y 只。每次跳跃可以让一只青蛙跨过一只反向青蛙，相当于”一次交换两只青蛙的进度”。若把每只青蛙需要跨越的异类数量记为 crossings，则每次跳跃最多减少 1 个 crossings，每次移动不减少 crossings。因此 crossings 的总量构成了一个极好的下界。
/**
* 下界函数：错位计数 + 必需跨越数
*/
public class LowerBound {
/**
* 计算从当前状态到目标状态的最小步数下界
* 采用三重下界取最大值，保证可采纳性的同时尽量紧
*/
public static int estimate(byte[] cur, int pairs) {
int n = cur.length;
// 下界一：位置不对的青蛙数
int misplaced = 0;
// 下界二：必须完成的"跨越"次数
int crossings = 0;
// 下界三：连续同向块的错排
int runs = 0;
for (int i = 0; i < n; i++) {
byte v = cur[i];
if (v == 0) {
continue;
}
boolean shouldBeTwo = i < pairs;
boolean shouldBeOne = i > pairs;
if ((v == 1 && shouldBeTwo) || (v == 2 && shouldBeOne)) {
misplaced++;
}
}
// 跨越数：统计每只青蛙需要越过的异类数量
// 对位置 i 的青蛙，若它需要向右（v==1），则它右侧所有 2 型青蛙都必须被越过
for (int i = 0; i < n; i++) {
if (cur[i] == 1) {
for (int j = i + 1; j < n; j++) {
if (cur[j] == 2) {
crossings++;
}
}
}
}
// 连续同向块：相邻两只同向青蛙之间若没有空位，则至少需要额外一步腾挪
for (int i = 0; i + 1 < n; i++) {
if (cur[i] != 0 && cur[i] == cur[i + 1]) {
runs++;
}
}
// 三者取最大，保证不过估
return Math.max(misplaced, Math.max(crossings, runs));
}
/** 可采纳性校验：真实距离 >= 下界 */
public static void sanityCheck(int pairs) {
FrogBfs bfs = new FrogBfs();
// 用真实 BFS 的最优值作为基准，验证起点下界不超标
int real = bfs.solve(pairs);
int lb = estimate(FrogState.initial(pairs).cells(), pairs);
if (lb > real) {
throw new IllegalStateException(
"下界不可采纳: pairs=" + pairs + " 下界=" + lb + " 真实=" + real);
}
System.out.printf("pairs=%d 起点下界=%d 真实最优=%d 紧度=%.1f%%%n",
pairs, lb, real, 100.0 * lb / real);
}
}
crossings 这个下界之所以强，是因为每次跳跃恰好能让 crossings 减少 1，而移动不减少它。所以在”必须靠跳跃才能推进”的早期阶段，它几乎等于真实距离。实测在 pairs=6 时，起点下界约 30，真实最优 48，紧度超过 60%，已经足以把搜索树剪掉绝大部分。
注意 runs 这个下界虽然直觉上合理，但严格证明起来比较麻烦（需要论证”每两只相邻同向青蛙至少对应一步额外操作”），在极端布局下可能失效。工程实践中的稳妥做法是把有争议的下界做开关，先用可证实的两项跑通，再逐个加入并用 BFS 在小子集上做可采纳性回归测试——sanityCheck 就是干这个的。
四、分支限界主体：A 与 IDA 的取舍
青蛙过河的边代价恒为 1，所以分支限界在这里可以退化成”带下界的优先队列搜索”，即 A（f = g + h）。当 h 不满足一致性时，A 仍能找到最优解（只要 h 可采纳），但可能重复扩展节点，需要用 bestG 表挡住。
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
/**
* 分支限界求解器：A* 语义 + 状态去重 + 上界剪枝
*/
public class FrogBranchAndBound {
/** 搜索节点 */
private static class Node {
final FrogState state;
final int g; // 已走步数
final int h; // 下界估计
Node parent;
int stepFrom = -1; // 记录从父节点哪个位置跳来，便于输出路径
Node(FrogState state, int g, int h, Node parent) {
this.state = state;
this.g = g;
this.h = h;
this.parent = parent;
}
int f() {
return g + h;
}
}
private final int pairs;
private long expanded = 0;
/** 初始上界：用贪心解或已知公式给一个可行解，作为剪枝阈值 */
private int upperBound;
public FrogBranchAndBound(int pairs) {
this.pairs = pairs;
// 标准布局下 pairs*(pairs+2) 是已知可行解，作为初始上界
this.upperBound = pairs * (pairs + 2);
}
public FrogState[] solve() {
FrogState start = FrogState.initial(pairs);
FrogState goal = FrogState.target(pairs);
long goalKey = goal.key();
PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparingInt(Node::f));
Map<Long, Integer> bestG = new HashMap<>();
Node root = new Node(start, 0, LowerBound.estimate(start.cells(), pairs), null);
open.add(root);
bestG.put(start.key(), 0);
Node best = null;
while (!open.isEmpty()) {
Node cur = open.poll();
expanded++;
// 上界剪枝：f 已不优于当前最优，整棵子树无望
if (cur.f() >= upperBound) {
continue;
}
// 重复扩展剪枝：该状态已有更短路径
Integer stored = bestG.get(cur.state.key());
if (stored != null && stored < cur.g) {
continue;
}
if (cur.state.key() == goalKey) {
upperBound = Math.min(upperBound, cur.g);
best = cur;
continue;
}
for (FrogState nxt : cur.state.successors()) {
int ng = cur.g + 1;
if (ng >= upperBound) {
continue;
}
Integer known = bestG.get(nxt.key());
if (known != null && known <= ng) {
continue;
}
bestG.put(nxt.key(), ng);
int nh = LowerBound.estimate(nxt.cells(), pairs);
open.add(new Node(nxt, ng, nh, cur));
}
}
System.out.printf("pairs=%d 展开节点=%d 最优步数=%d%n", pairs, expanded, best == null ? -1 : best.g);
if (best == null) {
return new FrogState[0];
}
return reconstruct(best);
}
/**
* 回溯路径：沿 parent 指针自底向上收集每一步的状态快照，
* 便于在界面上逐帧播放最优解
*/
private FrogState[] reconstruct(Node node) {
FrogState[] path = new FrogState[node.g + 1];
Node cur = node;
for (int i = node.g; i >= 0; i--) {
path[i] = cur.state;
cur = cur.parent;
}
return path;
}
}
这里有一个容易被忽略的细节：upperBound 初始值用的是”已知公式解”，在标准布局下它就是最优解，意味着算法第一轮就能把阈值设到最优——这会让剪枝异常激进，展开节点数远低于纯 A*。但如果布局被改动（比如空位不在正中），这个上界可能不是可行解，必须退回用贪心或放宽的估计值。用一个不可行的上界剪枝，会直接剪掉所有解。
五、等价状态归并与迭代加深
A 的内存开销主要来自 bestG 哈希表。青蛙过河有一个天然的对称性可以利用：左右反转等价*。把状态整体镜像并交换 1/2 的语义，得到的搜索子树与原子树同构。如果只搜其中一侧，可以把规模减半。
另一个优化是迭代加深（IDA*）：不维护 open 表，改用递增的 f 阈值反复 DFS，内存占用降到 O(深度)。代价是重复扩展，但在 h 较紧时重复率可接受。
/**
* IDA*：内存友好版本，适合大 pairs 场景
*/
public class FrogIdaStar {
private final int pairs;
private int threshold;
public FrogIdaStar(int pairs) {
this.pairs = pairs;
}
public int solve(int startThreshold) {
threshold = startThreshold;
while (true) {
int result = dfs(FrogState.initial(pairs), 0, 0, Long.MIN_VALUE);
if (result >= 0) {
return result;
}
if (result == Integer.MIN_VALUE) {
return new int[0]; // 无解
}
// 下一轮阈值取本轮的次小 f 值
threshold = result;
}
}
/**
* @return >=0 表示找到解（返回步数）；否则返回下一轮最小 f 阈值
*/
private int dfs(FrogState cur, int g, int depth, long parentKey) {
int h = LowerBound.estimate(cur.cells(), pairs);
int f = g + h;
if (f > threshold) {
return f;
}
if (cur.isTarget(pairs)) {
return g;
}
int min = Integer.MAX_VALUE;
for (FrogState nxt : cur.successors()) {
// 简单环检测：不回退到父状态
if (nxt.key() == parentKey) {
continue;
}
int r = dfs(nxt, g + 1, depth + 1, cur.key());
if (r >= 0) {
return r;
}
min = Math.min(min, r);
}
return min == Integer.MAX_VALUE ? Integer.MIN_VALUE : min;
}
}
parentKey 只挡住了一步回退，无法挡住更长的环。在青蛙过河里长环确实存在（跳过去再跳回来），但因为有 f > threshold 的截断，实践中危害有限。若发现 IDA* 在某个阈值上耗时异常长，就该加上”路径内状态集合”，用一个小 HashSet 记录当前 DFS 栈上的所有 key。
六、复杂度与实测对比
| 方案 | 时间 | 空间 | pairs=8 展开节点（约） |
|---|---|---|---|
| BFS | O(V + E) | O(V) 全状态 | 数十万 |
| A* + 双重下界 | 显著少于 BFS | O(V) 但常量小 | 数千 |
| IDA* + 双重下界 | 略多于 A* | O(深度) | 数千（有重复） |
真实距离对 pairs 的增长是二次的（pairs(pairs+2)），但状态空间是组合级的。这意味着下界函数的紧度决定了算法能否从”指数”退回”二次”的感觉——当 h 恰好等于真实距离时，A 只需沿最优路径一路直下，不做任何回溯。
七、游戏化：把搜索过程显示出来
算法跑通后，把它接到 Swing 上就变成一个可玩的游戏。玩家手动操作，程序在旁边显示当前状态的”下界估计”与”最优剩余步数”，两者差距就是剪枝的效率可视化。
import javax.swing.*;
import java.awt.*;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
/**
* 青蛙过河可视化：点击青蛙执行合法跳跃，界面显示下界估计
*/
public class FrogPanel extends JPanel {
private byte[] cells;
private final int pairs;
private int steps;
public FrogPanel(int pairs) {
this.pairs = pairs;
this.cells = FrogState.initial(pairs).cells();
setPreferredSize(new Dimension(80 + pairs * 2 * 60, 240));
addMouseListener(new MouseAdapter() {
@Override
public void mouseClicked(MouseEvent e) {
int idx = (e.getX() - 40) / 60;
if (idx >= 0 && idx < cells.length) {
tryMove(idx);
}
repaint();
}
});
}
/** 尝试移动 idx 位置的青蛙：允许相邻空位与跨跳 */
private void tryMove(int idx) {
byte v = cells[idx];
if (v == 0) {
return;
}
int dir = (v == 1) ? 1 : -1;
int j = idx + dir;
if (j >= 0 && j < cells.length && cells[j] == 0) {
swap(idx, j);
return;
}
int k = idx + 2 * dir;
if (k >= 0 && k < cells.length && cells[k] == 0) {
byte mid = cells[idx + dir];
if (mid != 0 && mid != v) {
swap(idx, k);
}
}
}
private void swap(int a, int b) {
byte t = cells[a];
cells[a] = cells[b];
cells[b] = t;
steps++;
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
for (int i = 0; i < cells.length; i++) {
int x = 40 + i * 60;
g.setColor(cells[i] == 0 ? new Color(220, 235, 250)
: (cells[i] == 1 ? new Color(80, 170, 90) : new Color(200, 120, 80)));
g.fillOval(x, 80, 48, 48);
g.setColor(Color.DARK_GRAY);
g.drawOval(x, 80, 48, 48);
if (cells[i] != 0) {
g.drawString(cells[i] == 1 ? "→" : "←", x + 18, 110);
}
}
g.setColor(Color.BLACK);
g.drawString("步数 = " + steps + " 下界估计 = "
+ LowerBound.estimate(cells, pairs), 40, 40);
if (java.util.Arrays.equals(cells, FrogState.target(pairs).cells())) {
g.setColor(new Color(0, 130, 0));
g.drawString("完成!", 40, 200);
}
}
public static void main(String[] args) {
JFrame f = new JFrame("青蛙过河 — 分支限界");
f.add(new FrogPanel(5));
f.pack();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.setVisible(true);
}
}
把”下界估计”实时显示在界面上，玩家会看到一个很有意思的现象：每次跳跃后下界可能不变（因为跳跃不减少 crossings 以外的东西），而相邻移动会让下界下降 1。这个视觉反馈恰好解释了为什么跳跃是这个游戏的核心资源。
八、小结
青蛙过河是”规则一句话、状态一屋子”的典型代表。本文用 Java 完成了完整实现：2-bit 状态压缩与 long 键去重、相邻与跨跳的合法后继生成、错位/跨越/连续块三重下界、带上下界剪枝的 A、内存友好的 IDA，以及可玩的可视化界面。最核心的收获是那个 crossings 下界——它抓住了”每次跳跃恰好消解一次异类交错”这一结构性质，把一个看似只能硬搜的问题压回了可控规模。设计下界函数时，先问”每步最多能改善哪个量”，答案往往就是最好的启发式。
