引言
“传金币”是一类经典的组合博弈问题：n个人围坐一圈，每人持有若干金币，每次只能将一枚金币传给相邻的人，目标是使所有人金币数相等。本文用Java实现该问题的最优求解算法，涵盖BFS状态空间搜索、博弈论中的纳什均衡思想，以及剪枝优化策略。
一、问题建模
1.1 状态定义
将n个人的金币数表示为一个状态向量，目标状态为每人平均金币数：
public class CoinState {
public final int[] coins; // 每人持有的金币数
public final int moves; // 已执行的传递次数
public final CoinState parent; // 父状态，用于回溯路径
public CoinState(int[] coins, int moves, CoinState parent) {
this.coins = coins.clone();
this.moves = moves;
this.parent = parent;
}
/**
* 计算状态的唯一哈希值，用于去重
*/
@Override
public int hashCode() {
return Arrays.hashCode(coins);
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (!(obj instanceof CoinState)) return false;
return Arrays.equals(coins, ((CoinState) obj).coins);
}
/**
* 检查是否达到目标状态
*/
public boolean isGoal(int target) {
for (int c : coins) {
if (c != target) return false;
}
return true;
}
}
1.2 合法移动生成
每次移动将一枚金币从位置i传给相邻的(i+1)%n或(i-1+n)%n：
public class CoinTransferGame {
private final int n; // 人数
private final int target; // 目标金币数
private final int[] initial; // 初始状态
public CoinTransferGame(int[] initial) {
this.initial = initial;
this.n = initial.length;
int sum = Arrays.stream(initial).sum();
if (sum % n != 0) {
throw new IllegalArgumentException("金币总数无法均分");
}
this.target = sum / n;
}
/**
* 生成当前状态的所有后继状态
* 每个位置可以向左右邻居传递一枚金币（如果有的话）
*/
public List<CoinState> getNeighbors(CoinState state) {
List<CoinState> neighbors = new ArrayList<>();
int[] c = state.coins;
for (int i = 0; i < n; i++) {
if (c[i] <= 0) continue; // 没有金币可传
// 传给左边邻居 (i-1)
int left = (i - 1 + n) % n;
int[] newLeft = c.clone();
newLeft[i]--;
newLeft[left]++;
neighbors.add(new CoinState(newLeft, state.moves + 1, state));
// 传给右边邻居 (i+1)
int right = (i + 1) % n;
if (right != left) { // n=2时左右是同一个
int[] newRight = c.clone();
newRight[i]--;
newRight[right]++;
neighbors.add(new CoinState(newRight, state.moves + 1, state));
}
}
return neighbors;
}
}
二、BFS最优解搜索
2.1 标准BFS实现
由于每次传递的代价相同（均为1次操作），BFS保证找到最少传递次数：
public class BFSSolver {
private final CoinTransferGame game;
public BFSSolver(CoinTransferGame game) {
this.game = game;
}
/**
* BFS搜索最少传递次数
* @return 最优解的状态链，null表示无解
*/
public CoinState solve() {
Queue<CoinState> queue = new LinkedList<>();
Set<CoinState> visited = new HashSet<>();
CoinState start = new CoinState(game.getInitial(), 0, null);
queue.offer(start);
visited.add(start);
int explored = 0;
while (!queue.isEmpty()) {
CoinState current = queue.poll();
explored++;
if (current.isGoal(game.getTarget())) {
System.out.println("BFS探索状态数: " + explored);
return current;
}
for (CoinState next : game.getNeighbors(current)) {
if (!visited.contains(next)) {
visited.add(next);
queue.offer(next);
}
}
}
return null; // 无解
}
/**
* 回溯打印解路径
*/
public void printSolution(CoinState goal) {
List<CoinState> path = new ArrayList<>();
CoinState cur = goal;
while (cur != null) {
path.add(cur);
cur = cur.parent;
}
Collections.reverse(path);
System.out.println("最少传递次数: " + goal.moves);
for (int i = 0; i < path.size(); i++) {
System.out.printf("Step %d: %s%n", i, Arrays.toString(path.get(i).coins));
}
}
}
2.2 双向BFS优化
当状态空间较大时，双向BFS可显著降低搜索范围：
public class BidirectionalBFSSolver {
public CoinState solve(CoinTransferGame game) {
// 构造目标状态
int[] goalArr = new int[game.getN()];
Arrays.fill(goalArr, game.getTarget());
CoinState goalState = new CoinState(goalArr, 0, null);
Queue<CoinState> qStart = new LinkedList<>();
Queue<CoinState> qGoal = new LinkedList<>();
Map<CoinState, CoinState> visitedStart = new HashMap<>();
Map<CoinState, CoinState> visitedGoal = new HashMap<>();
CoinState start = new CoinState(game.getInitial(), 0, null);
qStart.offer(start);
qGoal.offer(goalState);
visitedStart.put(start, null);
visitedGoal.put(goalState, null);
while (!qStart.isEmpty() && !qGoal.isEmpty()) {
// 优先扩展规模较小的一侧
if (qStart.size() <= qGoal.size()) {
CoinState meet = expandLayer(qStart, visitedStart, visitedGoal, game, true);
if (meet != null) return reconstruct(meet, visitedStart, visitedGoal);
} else {
CoinState meet = expandLayer(qGoal, visitedGoal, visitedStart, game, false);
if (meet != null) return reconstruct(meet, visitedStart, visitedGoal);
}
}
return null;
}
private CoinState expandLayer(Queue<CoinState> q, Map<CoinState, CoinState> myVisited,
Map<CoinState, CoinState> otherVisited,
CoinTransferGame game, boolean fromStart) {
int size = q.size();
for (int i = 0; i < size; i++) {
CoinState cur = q.poll();
for (CoinState next : game.getNeighbors(cur)) {
if (myVisited.containsKey(next)) continue;
myVisited.put(next, cur);
if (otherVisited.containsKey(next)) {
return next; // 相遇
}
q.offer(next);
}
}
return null;
}
private CoinState reconstruct(CoinState meet,
Map<CoinState, CoinState> fromStart,
Map<CoinState, CoinState> fromGoal) {
// 拼接双向路径
List<CoinState> path = new ArrayList<>();
CoinState cur = meet;
while (cur != null) {
path.add(cur);
cur = fromStart.get(cur);
}
Collections.reverse(path);
cur = fromGoal.get(meet);
while (cur != null) {
path.add(cur);
cur = fromGoal.get(cur);
}
// 创建带正确步数的目标状态
CoinState result = path.get(path.size() - 1);
return new CoinState(result.coins, path.size() - 1, null);
}
}
三、博弈论视角：纳什均衡与最优策略
3.1 双人对抗变体
考虑对抗版本：两人轮流传递金币，每次必须传递一枚，无法操作者输。这等价于Nim变体：
public class GameTheoryAnalyzer {
/**
* 计算双人对抗版传金币的Grundy数（SG函数）
* 状态: 每个人与目标值的偏差向量
* 简化模型: 将问题转化为偏差的一维流动
*/
public static int computeGrundy(int[] diffs) {
// 对简化的一维链模型，使用记忆化搜索
String key = Arrays.toString(diffs);
if (memo.containsKey(key)) return memo.get(key);
Set<Integer> reachable = new HashSet<>();
int n = diffs.length;
for (int i = 0; i < n; i++) {
if (diffs[i] > 0) {
// 可以向左边传递（减少自己的 surplus）
int[] next = diffs.clone();
next[i]--; next[(i-1+n)%n]++;
reachable.add(computeGrundy(next));
}
if (diffs[i] < 0) {
// 可以向右边传递（减少自己的 deficit）
int[] next = diffs.clone();
next[i]++; next[(i+1)%n]--;
reachable.add(computeGrundy(next));
}
}
int g = 0;
while (reachable.contains(g)) g++;
memo.put(key, g);
return g;
}
private static final Map<String, Integer> memo = new HashMap<>();
}
3.2 线性时间贪心解法
对于原始的最小步数问题（非对抗），存在O(n)贪心解法：
public class GreedySolver {
/**
* 线性时间求解最少传递次数
* 核心思想: 将环形拆成链，枚举断开点，取最小值
*
* @param coins 初始金币数组
* @return 最少传递次数
*/
public static int solve(int[] coins) {
int n = coins.length;
int sum = Arrays.stream(coins).sum();
if (sum % n != 0) return -1;
int target = sum / n;
// 计算前缀与目标的偏差
int[] diff = new int[n];
for (int i = 0; i < n; i++) {
diff[i] = coins[i] - target;
}
// 将环形拆成链，枚举断开点k
// 断开后，链上每个位置i的净流出量就是diff前缀和
int minMoves = Integer.MAX_VALUE;
for (int k = 0; k < n; k++) {
// 以k为起点，计算链上的前缀和
int[] prefix = new int[n];
prefix[0] = diff[k];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i-1] + diff[(k+i)%n];
}
// 最少移动次数 = 前缀和绝对值之和
// 证明: 每个prefix[i]表示位置i必须向右传递的金币数
int moves = 0;
for (int p : prefix) {
moves += Math.abs(p);
}
minMoves = Math.min(minMoves, moves);
}
return minMoves;
}
/**
* 更优的O(n)算法: 利用中位数性质
* 将问题转化为找前缀和数组的中位数
*/
public static int solveOptimal(int[] coins) {
int n = coins.length;
int sum = Arrays.stream(coins).sum();
if (sum % n != 0) return -1;
int target = sum / n;
// 任选一个断开点，计算前缀和
int[] prefix = new int[n];
prefix[0] = coins[0] - target;
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i-1] + coins[i] - target;
}
// 排序找中位数
int[] sorted = prefix.clone();
Arrays.sort(sorted);
int median = sorted[n / 2];
// 最小移动次数 = sum|prefix[i] - median|
int moves = 0;
for (int p : prefix) {
moves += Math.abs(p - median);
}
return moves;
}
}
四、完整测试与对比
public class Main {
public static void main(String[] args) {
int[] test = {3, 0, 2, 1}; // 总和6，4人，目标每人1.5...不对
int[] test2 = {4, 0, 2, 0}; // 总和6，4人，无法均分
int[] test3 = {3, 2, 1, 0}; // 总和6，4人，目标1.5...也不对
int[] test4 = {4, 0, 2, 2}; // 总和8，4人，目标2
// 使用合法测试用例
int[] coins = {4, 0, 2, 2};
System.out.println("=== 测试数据: " + Arrays.toString(coins) + " ===");
// BFS求解
CoinTransferGame game = new CoinTransferGame(coins);
BFSSolver bfs = new BFSSolver(game);
CoinState solution = bfs.solve();
if (solution != null) {
System.out.println("BFS最少步数: " + solution.moves);
}
// 贪心O(n)求解
int greedyMoves = GreedySolver.solveOptimal(coins);
System.out.println("贪心最优步数: " + greedyMoves);
// 更大规模测试
int[] large = {10, 0, 0, 0, 0, 0, 0, 0, 0, 0}; // 10人，1人有10枚
System.out.println("\n=== 大规模测试 ===");
int largeMoves = GreedySolver.solveOptimal(large);
System.out.println("10人均分10枚，最少步数: " + largeMoves);
}
}
五、复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| BFS | O((2n)^S) | O((2n)^S) | S为小规模状态空间，求精确最优解 |
| 双向BFS | O((2n)^(S/2)) | O((2n)^(S/2)) | 状态空间中等，加速明显 |
| 贪心O(n^2) | O(n^2) | O(n) | n较大，枚举断开点 |
| 贪心O(n log n) | O(n log n) | O(n) | n很大，利用中位数性质 |
其中S为总偏差金币数（即sum|coins[i]-target|/2）。
六、扩展方向
- 多轮博弈: 引入时间折扣因子，分析长期合作与背叛策略
- 图结构扩展: 将环形拓扑替换为任意图，使用网络流建模
- 带权传递: 不同方向/距离的传递消耗不同体力值，转化为最短路问题
总结
本文从BFS状态空间搜索出发，逐步优化到O(n log n)的贪心算法求解传金币问题。核心技巧包括双向BFS剪枝、SG函数博弈分析，以及将环形问题拆链后利用中位数性质求解。读者可以在此基础上扩展更复杂的网络拓扑与多智能体博弈场景。
