游戏简介与算法背景
叠叠杯（Cup Stacking）是一款考验手眼协调的经典益智玩具：若干颜色各异的杯子以特定规则堆叠，玩家需要通过一系列移动操作将杯子从初始状态整理为目标状态。从算法视角看，这等价于状态空间搜索问题——每个杯子的堆叠配置是一个状态，合法移动是状态转移边，求解最短操作序列即寻找状态空间中的最短路径。本文用 Java 实现基于 BFS 与 A* 搜索的最优解算法。
核心算法设计
1. 状态表示
将每个杯子堆叠列视为一个栈，整体状态用一个栈数组表示。状态编码为字符串以便哈希判重。
2. BFS 最短路径
BFS 天然保证找到的操作步数最少。核心流程：
– 将初始状态入队
– 逐层扩展所有合法移动
– 首次到达目标状态即为最优解
3. A* 启发式优化
对于复杂状态，BFS 的状态爆炸严重。引入启发函数 f = g + h：
– g：已执行步数
– h：错位杯子数 / 2（每个错误杯子至少需要一次移动）
Java 完整实现
import java.util.*;
/**
* 叠叠杯游戏 — 状态空间BFS与A*最优操作序列规划
*
* 核心算法：
* 1. 状态空间BFS：保证最少步数的完备搜索
* 2. A*搜索：启发式加速，适合复杂初始状态
* 3. 状态哈希编码：字符串化判重
* 4. 路径回溯：记录前驱状态与操作
*/
public class CupStacking {
private final int cupCount;
private final int columnCount;
public CupStacking(int cupCount, int columnCount) {
this.cupCount = cupCount;
this.columnCount = columnCount;
}
/**
* 状态类：不可变，便于哈希和比较
*/
static class State {
final List<Stack<Integer>> columns; // 每列是一个杯子栈，栈顶在末尾
final String encoded; // 编码字符串，用于哈希判重
State(List<Stack<Integer>> cols) {
this.columns = new ArrayList<>();
for (Stack<Integer> s : cols) {
Stack<Integer> copy = new Stack<>();
copy.addAll(s);
this.columns.add(copy);
}
this.encoded = encode();
}
/**
* 将状态编码为字符串，格式：每列杯子用逗号分隔，列之间用分号分隔
* 例如 "1,2;3;" 表示第一列有杯子1和2（1在底），第二列有杯子3
*/
private String encode() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < columns.size(); i++) {
Stack<Integer> col = columns.get(i);
for (int j = 0; j < col.size(); j++) {
if (j > 0) sb.append(',');
sb.append(col.get(j));
}
if (i < columns.size() - 1) sb.append(';');
}
return sb.toString();
}
/**
* 获取可执行的移动：将某列顶部杯子移到另一非空列或空列
*/
List<Move> getLegalMoves() {
List<Move> moves = new ArrayList<>();
for (int from = 0; from < columns.size(); from++) {
if (columns.get(from).isEmpty()) continue;
for (int to = 0; to < columns.size(); to++) {
if (from == to) continue;
moves.add(new Move(from, to));
}
}
return moves;
}
/**
* 执行移动，返回新状态
*/
State applyMove(Move move) {
List<Stack<Integer>> newCols = new ArrayList<>();
for (Stack<Integer> s : columns) {
Stack<Integer> copy = new Stack<>();
copy.addAll(s);
newCols.add(copy);
}
int cup = newCols.get(move.from).pop();
newCols.get(move.to).push(cup);
return new State(newCols);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof State)) return false;
return encoded.equals(((State) o).encoded);
}
@Override
public int hashCode() {
return encoded.hashCode();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < columns.size(); i++) {
sb.append("列").append(i).append(": ");
sb.append(columns.get(i));
sb.append("\n");
}
return sb.toString();
}
}
/**
* 移动操作：从 from 列顶部移一个杯子到 to 列
*/
static class Move {
final int from;
final int to;
Move(int from, int to) {
this.from = from;
this.to = to;
}
@Override
public String toString() {
return String.format("列%d → 列%d", from, to);
}
}
/**
* BFS求解最短操作序列
* 时间复杂度：O(状态数 × 分支因子)
* 空间复杂度：O(状态数)
*/
public List<Move> solveBFS(State initial, State target) {
if (initial.equals(target)) {
return new ArrayList<>();
}
Queue<State> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
Map<String, State> parent = new HashMap<>(); // 前驱状态
Map<String, Move> parentMove = new HashMap<>(); // 导致该状态的操作
queue.offer(initial);
visited.add(initial.encoded);
while (!queue.isEmpty()) {
State current = queue.poll();
for (Move move : current.getLegalMoves()) {
State next = current.applyMove(move);
if (visited.contains(next.encoded)) {
continue;
}
visited.add(next.encoded);
parent.put(next.encoded, current);
parentMove.put(next.encoded, move);
if (next.equals(target)) {
return reconstructPath(parent, parentMove, initial, next);
}
queue.offer(next);
}
}
return null; // 无解
}
/**
* A*搜索：启发式加速
* 启发函数：不在目标位置的杯子数 / 2
*/
public List<Move> solveAStar(State initial, State target) {
if (initial.equals(target)) {
return new ArrayList<>();
}
// 优先队列：按 f = g + h 排序
PriorityQueue<AStarNode> openSet = new PriorityQueue<>(
Comparator.comparingInt(n -> n.g + n.h)
);
Map<String, Integer> gScore = new HashMap<>();
Map<String, State> parent = new HashMap<>();
Map<String, Move> parentMove = new HashMap<>();
int h0 = heuristic(initial, target);
openSet.offer(new AStarNode(initial, 0, h0));
gScore.put(initial.encoded, 0);
while (!openSet.isEmpty()) {
AStarNode current = openSet.poll();
if (current.state.equals(target)) {
return reconstructPath(parent, parentMove, initial, current.state);
}
int currentG = gScore.getOrDefault(current.state.encoded, Integer.MAX_VALUE);
if (current.g > currentG) continue; // 已找到更优路径
for (Move move : current.state.getLegalMoves()) {
State next = current.state.applyMove(move);
int tentativeG = current.g + 1;
if (tentativeG < gScore.getOrDefault(next.encoded, Integer.MAX_VALUE)) {
parent.put(next.encoded, current.state);
parentMove.put(next.encoded, move);
gScore.put(next.encoded, tentativeG);
int h = heuristic(next, target);
openSet.offer(new AStarNode(next, tentativeG, h));
}
}
}
return null;
}
/**
* 启发函数：计算错位杯子数量
* 每个不在正确位置的杯子至少需要一次移动
*/
private int heuristic(State state, State target) {
// 简单启发：统计不在目标列的杯子数
int misplaced = 0;
// 构建目标位置映射：杯子编号 -> 目标列索引
Map<Integer, Integer> targetPos = new HashMap<>();
for (int col = 0; col < target.columns.size(); col++) {
for (int cup : target.columns.get(col)) {
targetPos.put(cup, col);
}
}
for (int col = 0; col < state.columns.size(); col++) {
for (int cup : state.columns.get(col)) {
if (targetPos.getOrDefault(cup, -1) != col) {
misplaced++;
}
}
}
return misplaced / 2; // 每次移动最多修正2个错位
}
static class AStarNode {
final State state;
final int g; // 实际代价
final int h; // 启发估计
AStarNode(State state, int g, int h) {
this.state = state;
this.g = g;
this.h = h;
}
}
/**
* 回溯重建操作序列
*/
private List<Move> reconstructPath(Map<String, State> parent,
Map<String, Move> parentMove,
State start, State end) {
LinkedList<Move> path = new LinkedList<>();
State current = end;
while (!current.equals(start)) {
Move move = parentMove.get(current.encoded);
path.addFirst(move);
current = parent.get(current.encoded);
}
return path;
}
/**
* 创建示例初始状态和目标状态
* 杯子编号 1-N，目标状态为所有杯子按顺序叠在第一列
*/
public static void demo() {
// 示例：4个杯子，3列
// 初始：列0=[1,2], 列1=[3], 列2=[4]
// 目标：列0=[1,2,3,4], 列1=[], 列2=[]
Stack<Integer> col0 = new Stack<>();
col0.push(1);
col0.push(2);
Stack<Integer> col1 = new Stack<>();
col1.push(3);
Stack<Integer> col2 = new Stack<>();
col2.push(4);
List<Stack<Integer>> initialCols = Arrays.asList(col0, col1, col2);
State initial = new State(initialCols);
Stack<Integer> t0 = new Stack<>();
t0.push(1);
t0.push(2);
t0.push(3);
t0.push(4);
List<Stack<Integer>> targetCols = Arrays.asList(t0, new Stack<>(), new Stack<>());
State target = new State(targetCols);
CupStacking game = new CupStacking(4, 3);
System.out.println("=== 初始状态 ===");
System.out.println(initial);
System.out.println("=== 目标状态 ===");
System.out.println(target);
// BFS求解
System.out.println("=== BFS求解 ===");
long startTime = System.currentTimeMillis();
List<Move> bfsSolution = game.solveBFS(initial, target);
long bfsTime = System.currentTimeMillis() - startTime;
if (bfsSolution != null) {
System.out.printf("BFS找到最优解，步数：%d，耗时：%dms%n",
bfsSolution.size(), bfsTime);
for (int i = 0; i < bfsSolution.size(); i++) {
System.out.printf(" 第%d步: %s%n", i + 1, bfsSolution.get(i));
}
}
// A*求解
System.out.println("\n=== A*求解 ===");
startTime = System.currentTimeMillis();
List<Move> aStarSolution = game.solveAStar(initial, target);
long aStarTime = System.currentTimeMillis() - startTime;
if (aStarSolution != null) {
System.out.printf("A*找到最优解，步数：%d，耗时：%dms%n",
aStarSolution.size(), aStarTime);
for (int i = 0; i < aStarSolution.size(); i++) {
System.out.printf(" 第%d步: %s%n", i + 1, aStarSolution.get(i));
}
}
}
public static void main(String[] args) {
demo();
}
}
算法复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 最优性 | 适用场景 |
|---|---|---|---|---|
| BFS | O(b^d) |
O(b^d) |
保证最优 | 状态空间小 |
| A* | O(b^d) 最坏，O(d) 平均 |
O(b^d) |
保证最优（可采纳启发式） | 状态空间大 |
| DFS | O(b^d) |
O(d) |
不保证最优 | 仅需任意解 |
其中 b 为分支因子（合法移动数），d 为最优解深度。
扩展思考
- IDA*算法：当内存受限时，迭代加深 A* 以时间换空间，仅需
O(d)内存。 - 双向搜索：从初始状态和目标状态同时 BFS，可将复杂度从
O(b^d)降至O(b^(d/2))。 - Pattern Database：预计算子问题的距离作为更强启发式，显著提升 A* 效率。
- 增强约束：实际叠叠杯可能有额外规则（如只能移顶部、列高度限制），需在
getLegalMoves中增加约束判断。
总结
叠叠杯问题完美诠释了状态空间搜索的核心思想。BFS 提供了完备性和最优性保证，而 A* 通过启发式引导搜索方向，在复杂问题中实现了数量级的加速。这种”状态表示 → 转移规则 → 搜索策略”的三段式建模方法，可广泛应用于魔方求解、华容道、推箱子等经典益智游戏。
