什么是渗流算法？( 二 ) _渗流算法

下面我们来说一下为什么需要两个WeightedQuickUnionUF 。
Backwash
我们使用虚拟顶点与虚拟底点的方式来解决对系统是否渗流的判断问题，从而引出了一个新的问题，那就是Backwash 。
为什么会出现这样的情况呢？因为有的site只与最底层连通，而没有连通至最高层的site ，但在并查集的数据结构中确实显示能够与顶层的site连通，从而被标记成了full的状态。

文章插图

那么要解决这个问题，就需要另一个WeightedQuickUnionUF ，这个不包含虚拟底点，这样在isFull()方法中检查的时候就不会出现这种问题了。
蒙特卡洛模拟

蒙特卡罗方法（英语：Monte Carlo method），也称统计模拟方法，是1940年代中期由于科学技术的发展和电子计算机的发明，而提出的一种以概率统计理论为指导的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。摘自Wikipedia 蒙特卡洛方法词条

通俗理解就是通过大量地随机样本，进而得到目标问题的所要计算的值。
在本题中，用来估计渗滤阈值。设定网格中所有方格为阻塞状态，随机打开一个方格后，判断该系统是否渗滤，如果没有，则继续打开，直到系统渗滤。那么$p$就为打开的方格数除以所有的方格数。进行大量多次实验就可以估计$p$的值。
package net.sunzhenyu.miscellaneous.dsa.other.percolation;import edu.princeton.cs.algs4.StdOut;import edu.princeton.cs.algs4.StdRandom;import edu.princeton.cs.algs4.StdStats;/** * Percolation Monte Monte Carlo simulation * * @author <a href="mailto:sunzhenyucn@gmail.com">SunZhenyu</a> * @version 0.0.1 * @date 2018/4/19 * @since 1.8 */public class PercolationStats { private static final double NUM = 1.96; private int t; private double[] fraction; public PercolationStats(int n, int t) { // perform t independent experiments on an n-by-n grid if (n <= 0 || t <= 0) { throw new IllegalArgumentException("n and t must be bigger than 0"); } this.t = t; fraction = new double[t]; for (int count = 0; count < t; count++) { Percolation pr = new Percolation(n); int openedSites = 0; while (!pr.percolates()) { int i = StdRandom.uniform(1, n + 1); int j = StdRandom.uniform(1, n + 1); if (!pr.isOpen(i, j)) { pr.open(i, j); openedSites++; } } fraction[count] = (double) openedSites / (n * n); } } public double mean() { // sample mean of percolation threshold return StdStats.mean(fraction); } public double stddev() { // sample standard deviation of percolation threshold return StdStats.stddev(fraction); } public double confidenceLo() { // low endpoint of 95% confidence interval return mean() - NUM * stddev() / Math.sqrt(t); } public double confidenceHi() { // high endpoint of 95% confidence interval return mean() + NUM * stddev() / Math.sqrt(t); } public static void main(String[] args) // test client (described below){ int n = Integer.parseInt(args[0]); int t = Integer.parseInt(args[1]); PercolationStats ps = new PercolationStats(n, t); StdOut.println("mean = " + ps.mean()); StdOut.println("stddev = " + ps.stddev()); StdOut.println("95% confidence interval = " + ps.confidenceLo() + ", " + ps.confidenceHi()); }}