3.1 题目描述

西蒙.丹尼斯.泊松是著名的法国数学家和物理学家。据说在他遇到某个古老的谜题之后，就开始对数学感兴趣了，这个谜题是这样的：给定一个装满水的8品脱壶以及两个容量分别为5品脱和3品脱的空壶，如何通过完全灌满或者到空这些壶从而使得某个壶精确地装有4品脱的水？用广度优先查找来求解这个谜题。要求在输出结果中包含广度优先的遍历过程（结点的遍历顺序）。（为什么不用尝试优先？）

3.2 程序使用说明

  1. 输入水壶数量n；
    2. 输入各水壶的最大容量maxP；
    3. 输入各水壶的当前状态initState；
    4. 输入最后期望的水量target。

    3.3 分析和设计

  2. 思路
    当有n个水壶时，每种状态有n(n-1)种灌水方式，也就产生了n(n-1)种状态，这些状态可能已经存在，某一状态存在说明已经有其他更好灌水方式达到这个状态，这种状态不需要重新处理。与深度遍历相比，在相同的灌水次数下，广度遍历可以产生更多的状态，在下一次灌水时就可以排除更多的状态，这有利于在较少的灌水次数下找到目标状态。在这里可以利用队列先进先出的特点来完成广度遍历。
    2. 伪代码
    1. PourWater(maxP[1...n], initState[1...n], target)
    2. // 输入: 水壶的容量maxP，初始状态initState，目标水量target
    3. // 输出：灌水过程
    4. // 队列，存储生成的未处理的状态
    5. queue
    6. // 三维数组，存储生成的所有状态及其父级状态
    7. parentState
    8. // 加入初始状态
    9. queue.offer(initState)
    10. parentState[0] <- {initState, null}
    11. isFind <- false
    12. while !queue.isEmpty() and !isFind do
    13.  head <- queue.poll()
    14.  for i <- 1 to n do
    15.      if isFind
    16.      continue
    17.      for j <- 1 to n do
    18.          // 第i个壶灌给第j个壶
    19.          if i = j
    20.              continue
    21.          else
    22.              // 不能在原位上更改
    23.              newState <- head
    24.          if newState[i] = 0
    25.              // 没水
    26.              continue
    27.          if newState[j] = maxP[j]
    28.              // 已灌满
    29.              continue
    30.          if newState[i] + newState[j] > maxP[j]
    31.              // 有剩余
    32.              newState[i] <- newState[i] -(maxP[j] - newState[j])
    33.              newState[j] <- maxP[j]
    34.          else
    35.              newState[j] <- newState[i] + newState[j]
    36.              newState[i] <- 0
    37.          if newState not in parentState
    38.              parentState[parenState.length] <- {newState, head}
    39.              queue.offer(newState)
    40.          if target in newState
    41.              isFind <- true
    42.              break
    43. return parentState
  3. 时间复杂度
    每个状态有n(n-1)种灌水方式，广度遍历会生成一棵n(n-1)叉树，假设需要k次灌水，那么时间复杂度就为O((n*(n-1))k)

    3.4 测试用例

    | | | | | | | —- | —- | —- | —- | —- | | 1 | maxP = [8, 5, 3]
    initState = [8, 0, 0]
    target = 4 | 1 4 3<-
    1 5 2<-
    6 0 2<-
    6 2 0<-
    3 2 3<-
    3 5 0<-
    8 0 0 | 1 4 3<-
    1 5 2<-
    6 0 2<-
    6 2 0<-
    3 2 3<-
    3 5 0<-
    8 0 0 | 通过 | | 2 | maxP = [8, 6, 3, 4]
    initState = [8, 0, 0, 0]
    target = 7 | 7 0 0 1<-
    4 0 3 1<-
    4 0 0 4<-
    8 0 0 0 | 7 0 0 1<-
    4 0 3 1<-
    4 0 0 4<-
    8 0 0 0 | 通过 |

3.5 源代码（含注释）

import java.util.*;
import java.util.stream.Collectors;
public class ThreePot {
    // 三个壶的状态
    int[] pot;
    // 三个壶的最大容量
    int[] maxP;
    // value作为父状态
    Map<String, String> parentState;
    // 是否找到可行组合
    boolean isFind;
    // 队列进行广度遍历，与深度遍历相比，在相同的灌水次数中，广度遍历产生了多种组合，
    // 而深度遍历每次灌水只有一种组合，这导致了相同的组合，深度遍历可能需要更多的灌水次数
    Queue<String> queueState;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入水壶数量：");
        int n = scanner.nextInt();
        int[] maxP = new int[n];
        System.out.println("请输入最大容量：");
        for (int i = 0; i < n; i++){
            maxP[i] = scanner.nextInt();
        }
        System.out.println("请输入当前状态：");
        int[] pot = new int[n];
        for (int i = 0; i < n; i++){
            pot[i] = scanner.nextInt();
        }
        System.out.println("请输入期望值：");
        int target = scanner.nextInt();
        ThreePot threePot = new ThreePot(maxP);
        threePot.traverse(pot, target);
        threePot.display();
    }
    public ThreePot() {
        this.maxP = new int[]{8, 5, 3};
    }
    public ThreePot(int[] maxP) {
        this.maxP = maxP;
    }
    /**
     * 广度遍历直到得到target
     *
     * @param initState
     * @param target
     */
    public void traverse(int[] initState, int target) {
        queueState = new LinkedList();
        parentState = new HashMap<>();
        isFind = false;
        setState(initState);
        String initStateString = Arrays.stream(initState).boxed().map(i -> i.toString()).collect(Collectors.joining(" "));
        queueState.offer(initStateString);
        parentState.put(initStateString, null);
        while (!queueState.isEmpty() && !isFind) {
            // 弹出一个状态
            String nowStateString = queueState.poll();
            int[] nowState;
            // 遍历当前状态的所有灌水可能
            for (int i = 0; i < pot.length && !isFind; i++) {
                for (int j = 0; j < pot.length && !isFind; j++) {
                    if (i != j) { // 壶不能相同
                        // 重置stream中的对象，否则就是当前pot
                        nowState = Arrays.stream(nowStateString.split(" ")).mapToInt(Integer::valueOf).toArray();
                        setState(nowState);
                        if (canPour(i, j)) {
                            pour(i, j);
                            String newStateString = Arrays.stream(pot).boxed().map(item -> item.toString()).collect(Collectors.joining(" "));
                            // 将未记录的组合记录下来
                            if (!parentState.containsKey(newStateString)) {
                                parentState.put(newStateString, nowStateString);
                                queueState.offer(newStateString);
                            }
                            // 如果当前状态有target
                            if (Arrays.stream(pot).boxed().filter(item -> item == target).count() > 0) {
                                isFind = true;
                                break;
                            }
                        }
                    }
                }
            }
        }
    }
    /**
     * 设定当前三个壶的状态
     */
    public void setState(int[] nowState) {
        this.pot = nowState;
    }
    /**
     * 从from中灌水到to中是否可行
     *
     * @param from
     * @param to
     * @return
     */
    public boolean canPour(int from, int to) {
        // from为空
        if (pot[from] == 0) {
            return false;
        }
        // to已装满
        if (pot[to] == maxP[to]) {
            return false;
        }
        return true;
    }
    /**
     * 从from中倒水到to中
     *
     * @param from
     * @param to
     */
    public void pour(int from, int to) {
        //做一个判读看看是否能剩水
        if (pot[from] + pot[to] > maxP[to]) {
            pot[from] = pot[from] - (maxP[to] - pot[to]);
            pot[to] = maxP[to];
        } else {
            pot[to] = pot[to] + pot[from];
            pot[from] = 0;
        }
    }
    /**
     * 展示灌水过程
     */
    public void display() {
        String target = Arrays.stream(pot).boxed().map(item -> item.toString()).collect(Collectors.joining(" "));
        // 依次输出父级
        while (parentState.get(target) != null){
            System.out.print(target+"<-");
            target = parentState.get(target);
        }
        System.out.println(target);
    }
}