每日算法 — 使用java实现量水问题：扩展欧几里得与BFS最优解搜索

引言

量水问题（Water Jug Problem）是经典的数学智力题：给定两个容量分别为 m 和 n 升的水壶，以及无限的水源，如何精确量出 d 升水？本文用Java实现该问题的完整求解系统，讲解扩展欧几里得算法判定可解性，以及BFS广度优先搜索寻找最少操作步数的最优解。

问题分析

操作定义

每个水壶可以执行以下6种基本操作：
1. 装满（Fill）：将水壶从水源装满
2. 倒空（Empty）：将水壶中的水全部倒掉
3. 倾倒（Pour）：将一个水壶的水倒入另一个，直到倒空或倒满

数学可解性判定

量水问题有解的充要条件是：d % gcd(m, n) == 0 且 d <= max(m, n)

这是裴蜀定理（Bézout’s Identity）的直接应用：对于任意整数 a, b，存在整数 x, y 使得 ax + by = gcd(a, b)。当且仅当 d 是 gcd(m,n) 的倍数时，才能通过若干次装满和倒空操作得到精确体积 d。

核心算法一：扩展欧几里得算法

扩展欧几里得算法不仅能计算 gcd(m, n)，还能找到满足 mx + ny = gcd(m, n) 的整数系数 x 和 y。基于这组系数，我们可以推导出量出 d 升水的具体操作序列。

// 扩展欧几里得算法核心逻辑
static int extendedGcd(int a, int b, int[] coeff) {
    if (b == 0) {
        coeff[0] = 1;  // x = 1
        coeff[1] = 0;  // y = 0
        return a;
    }
    int[] nextCoeff = new int[2];
    int gcd = extendedGcd(b, a % b, nextCoeff);
    coeff[0] = nextCoeff[1];
    coeff[1] = nextCoeff[0] - (a / b) * nextCoeff[1];
    return gcd;
}

核心算法二：BFS最优解搜索

虽然扩展欧几里得能告诉我们”能否量出”，但要找到操作步数最少的解法，需要借助状态空间搜索。将问题建模为图：
– 状态节点：(jug1, jug2) 表示两个水壶当前的水量
– 边：一次合法操作导致的状態转移
– 目标：任意一个水壶中的水量等于 d

BFS能保证找到步数最少的最优解。

完整Java实现

package water.jug;

import java.util.*;

/**
 * 量水问题求解器
 * 
 * 核心功能：
 * 1. 扩展欧几里得判定可解性并给出数学证明
 * 2. BFS搜索最少操作步数的最优解
 * 3. 输出可读的步骤序列
 * 4. 支持多组测试用例
 */
public class WaterJugSolver {

    /**
     * 水壶状态类
     */
    public static class State {
        public final int jug1;  // 第一个水壶当前水量
        public final int jug2;  // 第二个水壶当前水量
        public final int steps; // 到达该状态的操作步数
        public final String action; // 到达该状态的操作描述
        public final State parent;  // 父状态（用于回溯路径）

        public State(int j1, int j2, int steps, String action, State parent) {
            this.jug1 = j1;
            this.jug2 = j2;
            this.steps = steps;
            this.action = action;
            this.parent = parent;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof State)) return false;
            State s = (State) o;
            return jug1 == s.jug1 && jug2 == s.jug2;
        }

        @Override
        public int hashCode() {
            return jug1 * 1000 + jug2;
        }

        @Override
        public String toString() {
            return String.format("(%d, %d)", jug1, jug2);
        }
    }

    private final int capacity1;
    private final int capacity2;
    private final int target;

    public WaterJugSolver(int cap1, int cap2, int target) {
        this.capacity1 = cap1;
        this.capacity2 = cap2;
        this.target = target;
    }

    /**
     * 扩展欧几里得算法
     * 返回 gcd(a, b)，并通过 coeff 数组返回满足 ax + by = gcd 的系数
     * coeff[0] = x, coeff[1] = y
     */
    public int extendedGcd(int a, int b, int[] coeff) {
        if (b == 0) {
            coeff[0] = 1;
            coeff[1] = 0;
            return a;
        }
        int[] nextCoeff = new int[2];
        int gcd = extendedGcd(b, a % b, nextCoeff);
        // 回代：x = y', y = x' - (a/b) * y'
        coeff[0] = nextCoeff[1];
        coeff[1] = nextCoeff[0] - (a / b) * nextCoeff[1];
        return gcd;
    }

    /**
     * 判定问题是否可解
     * 充要条件：target 是 gcd(cap1, cap2) 的倍数，且 target <= max(cap1, cap2)
     */
    public boolean isSolvable() {
        if (target == 0) return true;
        if (target > capacity1 && target > capacity2) return false;
        int[] coeff = new int[2];
        int gcd = extendedGcd(capacity1, capacity2, coeff);
        return target % gcd == 0;
    }

    /**
     * 获取数学解法的关键系数
     * 返回满足 cap1 * x + cap2 * y = target 的 (x, y)
     * 注意：x, y 可能为负数，表示装满/倒空的方向
     */
    public int[] getMathSolution() {
        if (!isSolvable()) return null;
        int[] coeff = new int[2];
        int gcd = extendedGcd(capacity1, capacity2, coeff);
        int scale = target / gcd;
        return new int[]{coeff[0] * scale, coeff[1] * scale};
    }

    /**
     * BFS搜索最少步数的最优解
     * 返回达到目标状态的路径，若不可解返回 null
     */
    public List<State> solveBfs() {
        if (!isSolvable()) return null;
        if (target == 0) return Arrays.asList(new State(0, 0, 0, "初始状态", null));

        Queue<State> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        State start = new State(0, 0, 0, "初始状态", null);
        queue.add(start);
        visited.add("0,0");

        while (!queue.isEmpty()) {
            State current = queue.poll();

            // 检查是否达到目标
            if (current.jug1 == target || current.jug2 == target) {
                return reconstructPath(current);
            }

            // 生成所有可能的下一步状态
            List<State> nextStates = getNextStates(current);
            for (State next : nextStates) {
                String key = next.jug1 + "," + next.jug2;
                if (!visited.contains(key)) {
                    visited.add(key);
                    queue.add(next);
                }
            }
        }

        return null; // BFS理论上不会到达此处（可解性已判定）
    }

    /**
     * 从当前状态生成所有合法的下一步状态
     */
    private List<State> getNextStates(State current) {
        List<State> nextStates = new ArrayList<>();
        int j1 = current.jug1;
        int j2 = current.jug2;
        int nextSteps = current.steps + 1;

        // 操作1：装满水壶1
        if (j1 < capacity1) {
            nextStates.add(new State(capacity1, j2, nextSteps, 
                String.format("装满水壶1: (%d,%d) -> (%d,%d)", j1, j2, capacity1, j2), current));
        }

        // 操作2：装满水壶2
        if (j2 < capacity2) {
            nextStates.add(new State(j1, capacity2, nextSteps,
                String.format("装满水壶2: (%d,%d) -> (%d,%d)", j1, j2, j1, capacity2), current));
        }

        // 操作3：倒空水壶1
        if (j1 > 0) {
            nextStates.add(new State(0, j2, nextSteps,
                String.format("倒空水壶1: (%d,%d) -> (0,%d)", j1, j2, j2), current));
        }

        // 操作4：倒空水壶2
        if (j2 > 0) {
            nextStates.add(new State(j1, 0, nextSteps,
                String.format("倒空水壶2: (%d,%d) -> (%d,0)", j1, j2, j1), current));
        }

        // 操作5：将水壶1倒入水壶2
        if (j1 > 0 && j2 < capacity2) {
            int pour = Math.min(j1, capacity2 - j2);
            nextStates.add(new State(j1 - pour, j2 + pour, nextSteps,
                String.format("水壶1倒入水壶2: (%d,%d) -> (%d,%d)", j1, j2, j1 - pour, j2 + pour), current));
        }

        // 操作6：将水壶2倒入水壶1
        if (j2 > 0 && j1 < capacity1) {
            int pour = Math.min(j2, capacity1 - j1);
            nextStates.add(new State(j1 + pour, j2 - pour, nextSteps,
                String.format("水壶2倒入水壶1: (%d,%d) -> (%d,%d)", j1, j2, j1 + pour, j2 - pour), current));
        }

        return nextStates;
    }

    /**
     * 回溯重构从初始状态到目标状态的完整路径
     */
    private List<State> reconstructPath(State targetState) {
        List<State> path = new ArrayList<>();
        State current = targetState;
        while (current != null) {
            path.add(0, current); // 头插法
            current = current.parent;
        }
        return path;
    }

    /**
     * 打印求解结果
     */
    public void printSolution(List<State> path) {
        if (path == null) {
            System.out.println("该问题不可解！");
            return;
        }

        System.out.println("===== 最优解（最少步数） =====");
        System.out.println("水壶容量: (" + capacity1 + ", " + capacity2 + ")");
        System.out.println("目标水量: " + target);
        System.out.println("最少步数: " + (path.size() - 1));
        System.out.println();

        for (int i = 0; i < path.size(); i++) {
            State s = path.get(i);
            System.out.printf("步骤 %d: %s -> 状态 %s%n", i, s.action, s.toString());
        }
    }

    /**
     * 打印数学分析
     */
    public void printMathAnalysis() {
        int[] coeff = new int[2];
        int gcd = extendedGcd(capacity1, capacity2, coeff);
        int[] sol = getMathSolution();

        System.out.println("===== 数学分析 =====");
        System.out.println("水壶1容量 m = " + capacity1);
        System.out.println("水壶2容量 n = " + capacity2);
        System.out.println("目标水量 d = " + target);
        System.out.println("gcd(" + capacity1 + ", " + capacity2 + ") = " + gcd);
        System.out.println("可解性判定: d % gcd = " + (target % gcd) + 
            (target % gcd == 0 ? " == 0 → 可解" : " != 0 → 不可解"));

        if (sol != null) {
            System.out.println("\n裴蜀方程解: " + capacity1 + "×" + sol[0] + 
                " + " + capacity2 + "×" + sol[1] + " = " + target);
            System.out.println("解释: " + (sol[0] >= 0 ? "装满水壶1 " + sol[0] + " 次" : 
                "倒空水壶1 " + (-sol[0]) + " 次"));
            System.out.println("       " + (sol[1] >= 0 ? "装满水壶2 " + sol[1] + " 次" : 
                "倒空水壶2 " + (-sol[1]) + " 次"));
        }
    }

    // ==================== 测试入口 ====================
    public static void main(String[] args) {
        System.out.println("===== 量水问题求解器 =====\n");

        // 经典例题：3升和5升水壶，量出4升
        System.out.println("【例题1】3升和5升水壶，量出4升");
        WaterJugSolver solver1 = new WaterJugSolver(3, 5, 4);
        solver1.printMathAnalysis();
        System.out.println();
        List<State> path1 = solver1.solveBfs();
        solver1.printSolution(path1);

        System.out.println("\n" + "=".repeat(50) + "\n");

        // 经典例题：6升和10升水壶，量出8升
        System.out.println("【例题2】6升和10升水壶，量出8升");
        WaterJugSolver solver2 = new WaterJugSolver(6, 10, 8);
        solver2.printMathAnalysis();
        System.out.println();
        List<State> path2 = solver2.solveBfs();
        solver2.printSolution(path2);

        System.out.println("\n" + "=".repeat(50) + "\n");

        // 不可解例题：6升和10升水壶，量出9升
        System.out.println("【例题3】6升和10升水壶，量出9升（不可解）");
        WaterJugSolver solver3 = new WaterJugSolver(6, 10, 9);
        solver3.printMathAnalysis();
        System.out.println();
        List<State> path3 = solver3.solveBfs();
        solver3.printSolution(path3);
    }
}

复杂度分析

扩展与优化

1. 双方向BFS：从初始状态和目标状态同时进行BFS，将时间复杂度降为 O(√(m×n))
2. 贪心策略：基于扩展欧几里得的系数，直接构造近似最优解而不需要搜索
3. 多水壶扩展：支持 k 个水壶的量水问题，状态空间变为 O(m₁×m₂×…×mₖ)
4. 带权操作：不同操作有不同代价时，改用Dijkstra算法求最优解

总结

本文用Java实现了量水问题的完整求解系统，将数论中的裴蜀定理与图论中的BFS搜索完美结合。扩展欧几里得算法优雅地回答了”能否量出”的问题，而BFS则系统地找到了”如何最少步数量出”的最优策略。这种”先判定、后求解”的两阶段思路，是算法设计中处理约束满足问题的经典范式。