引言
称球问题是一道经典的信息论谜题：给定 $n$ 个外观相同的小球，其中恰好有一个是次品（可能更重或更轻），使用天平最少需要称几次才能找出次品并确定其轻重？本文将用Java实现称球问题的最优求解算法，核心结合信息论三分搜索与最优决策树构建。
问题分析与信息论下界
天平每次称重有3种可能结果：左重、平衡、右重。因此 $k$ 次称重最多可区分 $3^k$ 种情况。
对于 $n$ 个球，每个球都可能是重球或轻球，共 $2n$ 种可能。因此信息论下界为：
$$3^k \geq 2n \Rightarrow k \geq \lceil \log_3(2n) \rceil$$
经典结论：12球问题只需3次称重即可解决。
状态空间建模
每个球有三种状态：可能重（H）、可能轻（L）、正常（N）。初始时所有球都是 H 或 L 状态。
import java.util.*;
/**
* 称球问题求解器：信息论三分搜索 + 最优决策树
*/
public class BallWeighingSolver {
// 球的状态
enum Status { HEAVY, LIGHT, NORMAL }
static class Ball {
int id;
Status status;
Ball(int id) { this.id = id; this.status = Status.NORMAL; }
}
// 当前信息状态：记录每个球是否可能为H/L
static class State {
Set<Integer> possibleHeavy; // 可能重的球
Set<Integer> possibleLight; // 可能轻的球
int weighCount; // 已称重次数
List<String> history; // 称重历史
State(int n) {
possibleHeavy = new HashSet<>();
possibleLight = new HashSet<>();
for (int i = 1; i <= n; i++) {
possibleHeavy.add(i);
possibleLight.add(i);
}
weighCount = 0;
history = new ArrayList<>();
}
State(State other) {
possibleHeavy = new HashSet<>(other.possibleHeavy);
possibleLight = new HashSet<>(other.possibleLight);
weighCount = other.weighCount;
history = new ArrayList<>(other.history);
}
// 获取当前总可能性数
int getPossibilityCount() {
return possibleHeavy.size() + possibleLight.size();
}
// 是否已确定唯一解
boolean isSolved() {
return getPossibilityCount() == 1;
}
// 获取唯一解
String getSolution() {
if (possibleHeavy.size() == 1) {
int id = possibleHeavy.iterator().next();
return "球" + id + "是重的";
}
if (possibleLight.size() == 1) {
int id = possibleLight.iterator().next();
return "球" + id + "是轻的";
}
return "未确定";
}
}
称重操作与状态转移
/**
* 执行一次称重操作，根据结果更新状态
* @param state 当前信息状态
* @param left 左盘球编号集合
* @param right 右盘球编号集合
* @param result 称重结果：1=左重, 0=平衡, -1=右重
* @return 更新后的状态
*/
public State weigh(State state, Set<Integer> left, Set<Integer> right, int result) {
State newState = new State(state);
newState.weighCount++;
String record = String.format("第%d次: 左%s vs 右%s -> %s",
newState.weighCount, left, right,
result == 1 ? "左重" : (result == 0 ? "平衡" : "右重"));
newState.history.add(record);
Set<Integer> notWeighed = new HashSet<>();
for (int i = 1; i <= 12; i++) {
if (!left.contains(i) && !right.contains(i)) {
notWeighed.add(i);
}
}
if (result == 1) { // 左重
// 左盘的球可能重，右盘的球可能轻
// 未称的球和之前排除的球都是正常的
newState.possibleHeavy.retainAll(left);
newState.possibleLight.retainAll(right);
} else if (result == -1) { // 右重
newState.possibleHeavy.retainAll(right);
newState.possibleLight.retainAll(left);
} else { // 平衡
// 所有参与称重的球都是正常的
newState.possibleHeavy.removeAll(left);
newState.possibleHeavy.removeAll(right);
newState.possibleLight.removeAll(left);
newState.possibleLight.removeAll(right);
}
return newState;
}
最优称重方案生成：三分搜索策略
/**
* 生成当前状态下的最优称重方案
* 核心策略：将可能状态尽可能均匀地分配到3种结果中
* @param state 当前状态
* @param totalBalls 总球数
* @return 最优的左右盘球集合
*/
public WeighingPlan findBestWeighing(State state, int totalBalls) {
Set<Integer> candidates = new HashSet<>();
candidates.addAll(state.possibleHeavy);
candidates.addAll(state.possibleLight);
// 已知的正常球（可用于平衡配重）
Set<Integer> normalBalls = new HashSet<>();
for (int i = 1; i <= totalBalls; i++) {
if (!candidates.contains(i)) normalBalls.add(i);
}
WeighingPlan bestPlan = null;
double bestEntropy = Double.MAX_VALUE;
// 枚举左右盘的分配方案（只从候选球和已知正常球中选择）
// 策略：左右盘数量相等，且尽量将候选球均匀分配
List<Integer> candidateList = new ArrayList<>(candidates);
int maxPerSide = Math.min(4, candidateList.size() / 2 + 1);
for (int size = 1; size <= maxPerSide; size++) {
List<Set<Integer>> leftCombinations = generateCombinations(candidates, normalBalls, size);
for (Set<Integer> left : leftCombinations) {
// 右盘从剩余候选球中选择同样数量
Set<Integer> remaining = new HashSet<>(candidates);
remaining.removeAll(left);
List<Set<Integer>> rightCombinations = generateCombinations(remaining, normalBalls, size);
for (Set<Integer> right : rightCombinations) {
if (left.equals(right)) continue;
// 计算该方案的信息熵（三种结果的可能性分布）
double entropy = calculateEntropy(state, left, right);
if (entropy < bestEntropy) {
bestEntropy = entropy;
bestPlan = new WeighingPlan(left, right);
}
}
}
}
return bestPlan;
}
/**
* 计算给定称重方案的信息熵
* 熵越小表示信息增益越大（三种结果越均匀）
*/
private double calculateEntropy(State state, Set<Integer> left, Set<Integer> right) {
// 模拟三种结果，统计各自的可能性数量
State s1 = weigh(state, left, right, 1);
State s0 = weigh(state, left, right, 0);
State s_1 = weigh(state, left, right, -1);
int c1 = s1.getPossibilityCount();
int c0 = s0.getPossibilityCount();
int c_1 = s_1.getPossibilityCount();
int total = c1 + c0 + c_1;
if (total == 0) return Double.MAX_VALUE;
// 香农熵: -sum(p_i * log(p_i))
double entropy = 0;
for (int c : new int[]{c1, c0, c_1}) {
if (c > 0) {
double p = (double) c / total;
entropy -= p * Math.log(p) / Math.log(3);
}
}
return entropy;
}
/**
* 生成指定大小的球集合组合（从候选球+正常球中选取）
*/
private List<Set<Integer>> generateCombinations(Set<Integer> candidates,
Set<Integer> normalBalls,
int size) {
List<Set<Integer>> results = new ArrayList<>();
List<Integer> all = new ArrayList<>();
all.addAll(candidates);
all.addAll(normalBalls);
combinationsHelper(all, 0, size, new HashSet<>(), results);
return results;
}
private void combinationsHelper(List<Integer> list, int start, int size,
Set<Integer> current, List<Set<Integer>> results) {
if (size == 0) {
results.add(new HashSet<>(current));
return;
}
for (int i = start; i <= list.size() - size; i++) {
current.add(list.get(i));
combinationsHelper(list, i + 1, size - 1, current, results);
current.remove(list.get(i));
}
}
static class WeighingPlan {
Set<Integer> left, right;
WeighingPlan(Set<Integer> l, Set<Integer> r) { left = l; right = r; }
public String toString() {
return "左盘" + left + " vs 右盘" + right;
}
}
完整求解与验证
/**
* 针对12球问题的完整求解流程演示
* 已知：12个球中有一个次品，不知轻重
*/
public void solve12Balls() {
System.out.println("=== 12球称球问题求解 ===\n");
System.out.println("信息论下界: ceil(log3(24)) = " +
(int)Math.ceil(Math.log(24) / Math.log(3)) + " 次\n");
State state = new State(12);
// 第一次称重：最优策略是将12球分4组，每组3个
// 1,2,3,4 vs 5,6,7,8
Set<Integer> left1 = new HashSet<>(Arrays.asList(1, 2, 3, 4));
Set<Integer> right1 = new HashSet<>(Arrays.asList(5, 6, 7, 8));
System.out.println("第一次称重方案: " + new WeighingPlan(left1, right1));
System.out.println("（理论最优：将24种可能性尽量均匀分为3组）\n");
// 模拟所有可能的结果
for (int result : new int[]{1, 0, -1}) {
State s = weigh(state, left1, right1, result);
String resultStr = result == 1 ? "左重" : (result == 0 ? "平衡" : "右重");
System.out.println("若结果=" + resultStr + ": 剩余可能性=" + s.getPossibilityCount());
System.out.println(" 可能重: " + s.possibleHeavy);
System.out.println(" 可能轻: " + s.possibleLight);
if (!s.isSolved()) {
WeighingPlan plan2 = findBestWeighing(s, 12);
System.out.println(" 第二次称重: " + plan2);
}
System.out.println();
}
}
/**
* 针对已知次品轻重的情况求解（简化版）
* @param n 球的数量
* @param heavy 是否已知次品更重（false则已知更轻）
* @return 最少称重次数及方案
*/
public int solveKnownWeight(int n, boolean heavy) {
// 此时每次称重也是3种结果，但只有n种可能性
// 信息论下界: ceil(log3(n))
return (int) Math.ceil(Math.log(n) / Math.log(3));
}
public static void main(String[] args) {
BallWeighingSolver solver = new BallWeighingSolver();
solver.solve12Balls();
System.out.println("=== 已知轻重的情况 ===");
System.out.println("27球已知次品更重: 最少需要 " + solver.solveKnownWeight(27, true) + " 次");
System.out.println("解释: 3^3 = 27，每次将球分为3组，可逐次缩小到1/3");
}
}
决策树构建与可视化
/**
* 决策树节点：记录每个称重步骤
*/
class DecisionNode {
Set<Integer> left, right; // 本次称重的左右盘
DecisionNode leftHeavy; // 左重分支
DecisionNode balance; // 平衡分支
DecisionNode rightHeavy; // 右重分支
String solution; // 叶子节点的解（若已确定）
boolean isLeaf() { return solution != null; }
}
/**
* 构建完整决策树（针对小规模问题）
*/
public class DecisionTreeBuilder {
/**
* 递归构建决策树
* @param state 当前信息状态
* @param totalBalls 总球数
* @param maxDepth 最大深度限制
* @return 决策树根节点
*/
public DecisionNode buildTree(BallWeighingSolver.State state,
int totalBalls, int maxDepth) {
DecisionNode node = new DecisionNode();
if (state.isSolved() || state.weighCount >= maxDepth) {
node.solution = state.getSolution();
return node;
}
BallWeighingSolver solver = new BallWeighingSolver();
BallWeighingSolver.WeighingPlan plan = solver.findBestWeighing(state, totalBalls);
if (plan == null) {
node.solution = "无法确定";
return node;
}
node.left = plan.left;
node.right = plan.right;
node.leftHeavy = buildTree(solver.weigh(state, plan.left, plan.right, 1),
totalBalls, maxDepth);
node.balance = buildTree(solver.weigh(state, plan.left, plan.right, 0),
totalBalls, maxDepth);
node.rightHeavy = buildTree(solver.weigh(state, plan.left, plan.right, -1),
totalBalls, maxDepth);
return node;
}
}
复杂度分析
- 信息论下界：$k = \lceil \log_3(2n) \rceil$，这是理论最优解
- 方案枚举：每次称重需要从 $n$ 个球中选择左右盘，复杂度为 $O(C(n, k)^2)$，实际中通过剪枝和限制盘大小，效率可接受
- 决策树空间：完整决策树有 $3^k$ 个节点，空间复杂度 $O(3^k)$
- 求解时间：对于12球问题，构建完整决策树的时间为 $O(3^3 \cdot poly(n))$，即常数时间
总结
本文通过Java实现了称球问题的完整求解框架：
- 信息论分析：利用香农熵计算理论下界，证明12球问题只需3次称重
- 状态空间建模：用 H/L/N 三态追踪每个球的可能性
- 三分搜索策略：每次称重将可能性集合尽量均匀分为3份
- 决策树构建：递归生成完整的称重决策流程
读者可以进一步扩展：实现N球通用求解器、引入未知次品数量的情况、或构建交互式称重模拟器验证决策树正确性。
