倒水问题(Fill, UVa 10603)Java算法实现BFS+PriorityQueue优先队列

倒水问题(Fill, UVa 10603)

有装满水的6升的杯子、空的3升杯子和1升杯子,3个杯子中都没有刻度。在不使用其他 道具的情况下,是否可以量出4升的水呢?

倒水问题:一种方法是(6,0,0)→(3,3,0)→(3,2,1)→(4,2,0)

注意:由于没有刻度,用杯子x给杯子y倒水时必须一直持续到把杯子y倒满或者把杯 子x倒空,而不能中途停止。

你的任务是解决一般性的问题:设3个杯子的容量分别为a, b, c,最初只有第3个杯子装 满了c升水,其他两个杯子为空。最少需要倒多少升水才能让某一个杯子中的水有d升呢?如 果无法做到恰好d升,就让某一个杯子里的水是d’升,其中d’<d并且尽量接近d。 (1≤a,b,c,d≤200)。要求输出最少的倒水量和目标水量(d或者d’)。

分析

大致思想是通过解答树完成,利用BFS算法,假设在某一时刻,第1个杯子中有v0升水,第2个杯子中有v1升水,第3个杯子中有v2升水,称当时的系统状态为(v0,v1,v2)。这里提到了“状态”这个词,它是理解很多概念和算法的关键。简单地说,它就是“对系统当前状况的描述”。例如,在国际象棋中,当前游戏者 和棋盘上的局面就是刻画游戏进程的状态。

把“状态”想象成树中的结点,可以得到如下解答树。

注意:本题的目标是倒的水量最少,而不是步数最少。实际上,水量最少时步数不一定 最少,例如a=1, b=12, c=15, d=7,倒水量最少的方案是C->A, A->B重复7次,最后C里有7 升水。一共14步,总水量也是14。还有一种方法是C->B,然后B->A, A->C重复4次,最后C 里有7升水。一共只有10步,但总水量多达20。

因此,需要改进一下算法:不是每次取出步数最少的结点进行扩展,而是取出水量最少的结点进行扩展。这样的程序只需要把队列queue换成优先队列PriorityQueue,其他部分的代码不变。

代码

以下代码纯手工编写,欢迎指出错误和优化方法。

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;

/**
 * 倒水问题(Fill, UVa 10603)
 * 
 * 有装满水的6升的杯子、空的3升杯子和1升杯子,3个杯子中都没有刻度。在不使用其他 道具的情况下,是否可以量出4升的水呢?
 * 
 * 注意: 由于没有刻度,用杯子x给杯子y倒水时必须一直持续到把杯子y倒满或者把杯子x倒空,而不能中途停止。
 * 
 * 你的任务是解决一般性的问题: 设3个杯子的容量分别为a, b, c,最初只有第3个杯子装
 * 满了c升水,其他两个杯子为空。最少需要倒多少升水才能让某一个杯子中的水有d升呢?如
 * 果无法做到恰好d升,就让某一个杯子里的水是d'升,其中d'<d并且尽量接近d。
 * (1≤a,b,c,d≤200)。要求输出最少的倒水量和目标水量(d或者d')。
 * 
 */

public class Main {

	public static int goal;// 需要获取的最终水量
	public static int[] glassMax = new int[3];// 各个杯子最大容积
	public static Node originNode;// 初始状态杯子内存有的水量

	public static int nearestNum = -1;// 最接近目标水量的水量
	public static int lowest = Integer.MAX_VALUE; // 最接近目标水量或已达到最优水量的最少倒水量
	public static Node lowestNode;// //最接近目标水量或已达到最优水量的最少倒水量情况(结点)

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			glassMax[0] = sc.nextInt();
			glassMax[1] = sc.nextInt();
			glassMax[2] = sc.nextInt();
			goal = sc.nextInt();
			initOriginNode();// 初始化originNode节点
			BlockOut();// 此方法利用多线程限制时间,用于防止计算超时,给出当前可行解(未必是最优解,碰运气!)

			try {
				bfs();// 通过广度优先生成树并检索最优解
				printResult();// 输出最优解
			} catch (Exception e) {
			}

			System.exit(0);
		}
	}

	/**
	 * 此方法利用初始化originNode节点
	 */
	public static void initOriginNode() {
		int maxIndex = -1;
		int maxValue = -1;
		for (int i = 0; i < glassMax.length; i++) {
			if (glassMax[i] > maxValue) {
				maxValue = glassMax[i];
				maxIndex = i;
			}
		}
		int[] picOrigin = new int[glassMax.length];// 各个杯子最大容积
		Arrays.fill(picOrigin, 0);
		picOrigin[maxIndex] = maxValue;
		originNode = new Node(picOrigin);
		lowestNode = originNode;
	}

	/**
	 * 此方法利用多线程限制时间,用于防止计算超时,给出当前可行解(未必是最优解,碰运气!)
	 */
	public static void BlockOut() {
		Runnable run = new Runnable() {
			@Override
			public void run() {
				try {
					Thread.sleep(2900);
					printResult();
				} catch (Exception e) {
				} finally {
					System.exit(0);
				}
			}

		};
		new Thread(run).start();
	}

	/**
	 * 输出最优解
	 * 
	 * @throws CloneNotSupportedException
	 */
	public static void printResult() throws CloneNotSupportedException {

		Stack<Node> stack = new Stack<Node>();
		Node pre = lowestNode;

		stack.add(pre.clone());
		do {
			pre = pre.paNode;
			stack.add((Node) pre.clone());
		} while (pre.paNode != pre);

		for (int i = 0; !stack.isEmpty(); i++) {
			System.out.println("Step" + i + ":"
					+ Arrays.toString(stack.pop().pic));
		}

		if (nearestNum != goal) {
			System.out.println("无法找到最优解,最接近的可得目标容量:" + nearestNum);
		}
		System.out.println("其最少倒水量:" + lowest);

	}

	/**
	 * 通过广度优先生成树并检索最优解
	 */
	public static void bfs() {
		PriorityQueue<Node> queue = new PriorityQueue<Node>();
		queue.add(originNode);

		while (!queue.isEmpty()) {
			Node keyNode = queue.remove();

			// 检索操作,对当前结点和当前解进行判断
			if (nearestNum != goal) {
				if (keyNode.getNear() > nearestNum) {
					nearestNum = keyNode.getNear();
					lowestNode = keyNode;
					lowest = keyNode.addStepNumTotal;
				}

			} else {
				if (lowestNode.isGoal()) {
					if (keyNode.isGoal()) {
						if (keyNode.addStepNumTotal <= lowest) {
							lowest = keyNode.addStepNumTotal;
							lowestNode = keyNode;
						}
					}
				} else {
					if (keyNode.isGoal()) {
						lowest = keyNode.addStepNumTotal;
						lowestNode = keyNode;
					} else {
						if (keyNode.addStepNumTotal <= lowest
								&& keyNode.addStepNumTotal != 0) {
							lowest = keyNode.addStepNumTotal;
							lowestNode = keyNode;
						}
					}
				}
			}

			for (int item = 0; item < glassMax.length; item++) {
				for (int other = 0; other < glassMax.length; other++) {
					// item代表被倒入水的杯子索引,other代表从某个杯子向item杯子倒水

					// 粗剪枝
					if (item == other) {
						continue;
					}
					if (keyNode.pic[other] == 0) {
						continue;
					}
					if (keyNode.pic[item] == glassMax[item]) {
						continue;
					}

					// 生产新节点
					int[] newPic = keyNode.pic.clone();
					int beforeNum = newPic[item];
					int addNum = newPic[other];
					newPic[item] = (beforeNum + addNum <= glassMax[item] ? beforeNum
							+ addNum
							: glassMax[item]);
					newPic[other] = (beforeNum + addNum <= glassMax[item] ? 0
							: addNum - glassMax[item] + beforeNum);

					Node newNode = new Node(newPic, keyNode.addStepNumTotal
							+ newPic[item] - beforeNum, keyNode);

					// 判断是否已经出现过这样的情况
					boolean sameFlag = false;
					Node judge = newNode;
					do {
						judge = judge.paNode;
						if (newNode.equals(judge)) {
							sameFlag = true;
							break;
						}
					} while (judge != judge.paNode);

					if (sameFlag) {
						continue;
					}

					queue.add(newNode);
				}
			}
		}
	}
}

class Node implements Comparable<Node>, Cloneable {
	public int pic[];// 以数组形式存放当前情况下各个杯子的水量
	public int addStepNumTotal = 0;// 执行到此步时共倒水量
	public Node paNode;// 父节点,代表产生这个情况的上一种情况

	/**
	 * 此构造方法仅可用于初始化originNode来构造
	 * 
	 * @param pic
	 */
	public Node(int pic[]) {
		this.pic = pic;
		this.paNode = this;
	}

	/**
	 * 此构造方法仅可用于产生新情况(新结点)使用
	 * 
	 * @param pic
	 * @param addNumTotal到这步总共增倒水量
	 * @param pa父节点
	 *            ,代表产生这个情况的上一种情况
	 */
	public Node(int pic[], int addNumTotal, Node pa) {
		this.pic = pic;
		this.addStepNumTotal = addNumTotal;
		this.paNode = pa;
	}

	/**
	 * 用于剪枝操作,对比两个情况是否相同
	 */
	public boolean equals(Object obj) {
		if (obj instanceof Node) {
			Node objNode = (Node) obj;
			return Arrays.equals(this.pic, objNode.pic);
		}
		return false;
	}

	/**
	 * 此方法判断是否出现解
	 * 
	 * @return
	 */
	public boolean isGoal() {
		for (int i = 0; i < this.pic.length; i++) {
			if (this.pic[i] == Main.goal) {
				return true;
			}
		}
		return false;
	}

	/**
	 * 此方法返回最接近目标的水量
	 * 
	 * @return
	 */
	public int getNear() {
		int nearest = -1;
		for (int i = 0; i < this.pic.length; i++) {
			if (this.pic[i] <= Main.goal && this.pic[i] > nearest) {
				nearest = this.pic[i];
			}
		}
		return nearest;
	}

	/**
	 * 此方法用于优先队列中,快速对优先的情况进行判断
	 */
	@Override
	public int compareTo(Node obj) {
		if (this.isGoal()) {
			if (obj.isGoal()) {
				if (this.addStepNumTotal <= obj.addStepNumTotal) {
					return 1;
				} else {
					return -1;
				}
			} else {
				return 2;
			}
		} else {
			if (obj.isGoal()) {
				return -2;
			} else {
				return 0;
			}
		}
	}

	/**
	 * 克隆当前情况(浅复制)
	 */
	public Node clone() throws CloneNotSupportedException {
		return (Node) super.clone();
	}

}