Algorithms Part1课程第一周的Programming Assignment是Percolation问题，该问题是Union-Find算法的一个应用实例。
作业要求见以下链接：，要求用Java实现算法。此外该课程使用了作者提供的API用以简化编程，如基本输入、输出、随机数生成、数据分析等库函数，在上述链接中可直接下载。
模型描述：
Percolation即渗透过程，其模型如下：一个方形“水槽”（system）由N*N个方格（site）组成，每个方格有开启（open）或关闭（blocked）两个状态，相邻（即上下左右）的开启格子能够构成一条同路。如果一个格子处于开启状态，并且与顶端的一行能够通过开启的格子实现连通（connected）通路，我们说这个格子处于充满水（full）的状态；如果一个“水槽”（system）的顶端格子与底部格子通过开启的格子实现了连通，我们称这个“水槽”是可以渗透（percolates）的。如下图所示：
问题描述：
本次作业要求实现上述模型，并计算出“水槽”达到渗透状态时开启格子的数量占所有格子总数的比例（p）。通过蒙特卡洛模拟方法，采用多次模拟采样进行p值的估算。对于不同大小的“水槽”有如下模拟曲线，左图为20*20大小，右图为100*100大小：
Percolation编程分析：
按照作业要求，需要按照以下API创建一个Percolation类作为数据抽象类型：
public class Percolation { public Percolation(int N)// create N-by-N grid, with all sites blocked public void open(int i, int j)// open site (row i, column j) if it is not already public boolean isOpen(int i, int j) // is site (row i, column j) open? public boolean isFull(int i, int j) // is site (row i, column j) full? public boolean percolates()// does the system percolate?}
对其中每个方法分析如下：
Percolation(int N)：该构造方法对模型初始化，我们创建一个N*N大小的一维布尔数组作为“水槽”，数组值记录每个格子的开闭状态，初始状态为关闭。此外，我们需要另一个(N*N+2)大小的一维数组存储连通关系，根据Union-Find算法的学习，我们创建类型为WeightedQuickUnionUF的数组。大小之所以为(N*N+2)，，是因为在检查是否渗透的时候，可以通过在顶部与底部设置两个虚拟点，其与顶端或底部的一排是相连通的，这样检查是否渗透的时候，无需遍历顶部或底部一排的每一个点，只需要检查两个虚拟点是否连通即可，如下图所示：
注意的一点是，在用一维数组模拟二维“水槽”时，我们用i，j坐标进行表示，(i, j)表示的是数组中序号为(i – 1)*N + (j – 1)的元素；此外，由于虚拟点的设置，坐标的对应容易出现混乱，需要首先考虑清楚这个问题。
更重要的一个问题：BackWash即回流/倒灌问题，按照上面的方法设置虚拟点虽然使得检查是否percolate变得方便，但如果水已经渗透到底部，由于虚拟点与底部一排都是连通的，则会通过底部开启的格子向上“灌水”，如下图所示：
解决的方法是：在构造方法中额外定义一个(N*N+1)大小的数组，其不包括底部的虚拟点，其他与(N*N+2)大小的数组一致，在isFull()方法中，我们使用这个(N*N+1)的数组进行检查，也就是说，如果底部的格子确实没有与顶部的虚拟点连通，是不会“灌满”的。下面用图来说明这一过程：
左图中由于底部有虚拟点，右下角的格子出现了倒灌；而右图中由于底部没有虚拟点，不会出现倒灌。注意仅仅在执行percolates()方法时有这一区别。
代码实现如下：
public class Percolation {private boolean[] openStates;private WeightedQuickUnionUF connectStates;private WeightedQuickUnionUF connectStatesBW;//private QuickFindUF connectStates;//private QuickFindUF connectStatesBW;private int N;//create N-by-N grid, with all sites blockedpublic Percolation(int N) {this.N = N;openStates = new boolean[N * N];for (int i = 0; i < N; i++)for (int j = 0; j < N; j++)openStates[i * N + j] = false;connectStates = new WeightedQuickUnionUF(N * N + 2);connectStatesBW = new WeightedQuickUnionUF(N * N + 1);//connectStates = new QuickFindUF(N * N + 2);//connectStatesBW = new QuickFindUF(N * N + 1);}//open site (row i, column j) if it is not already public void open(int i, int j) {if (i < 1 || j < 1 || i > N || j > N)throw new java.lang.IndexOutOfBoundsException();int nx = i – 1; int ny = j – 1;if (!openStates[nx * N + ny]){openStates[nx * N + ny] = true;if ((nx – 1) >= 0 && ny >= 0 && (nx – 1) < N && ny < N && openStates[(nx – 1) * N + ny]) {connectStates.union(nx * N + ny + 1, (nx – 1) * N + ny + 1);connectStatesBW.union(nx * N + ny + 1, (nx – 1) * N + ny +1);}if ((nx + 1) >= 0 && ny >= 0 && (nx + 1) < N && ny < N && openStates[(nx + 1) * N + ny]) {connectStates.union(nx * N + ny + 1, (nx + 1) * N + ny + 1);connectStatesBW.union(nx * N + ny + 1, (nx + 1) * N + ny + 1);}if (nx >= 0 && (ny – 1) >= 0 && nx < N && ny < N && openStates[nx * N + (ny – 1)] && ny != 0) {connectStates.union(nx * N + ny + 1, nx * N + (ny – 1) + 1);connectStatesBW.union(nx * N + ny + 1, nx * N + (ny – 1) + 1);}if (nx >= 0 && (ny + 1) >= 0 && nx < N && (ny + 1) < N && openStates[nx * N + (ny + 1)] && ny != N – 1) {connectStates.union(nx * N + ny + 1, nx * N + (ny + 1) + 1);connectStatesBW.union(nx * N + ny + 1, nx * N + (ny + 1) + 1);}if (i == 1) {connectStates.union(nx * N + ny + 1, 0);connectStatesBW.union(nx * N + ny + 1, 0);}if (i == N)connectStates.union(nx * N + ny + 1, N * N + 1);}}// is site (row i, column j) open?public boolean isOpen(int i, int j) {if (i < 1 || i > N || j < 1 || j > N)throw new java.lang.IndexOutOfBoundsException();int nx = i – 1; int ny = j – 1;return (openStates[nx * N + ny]);}// is site (row i, column j) full?public boolean isFull(int i, int j) {if (i < 1 || i > N || j < 1 || j > N)throw new java.lang.IndexOutOfBoundsException();int nx = i – 1; int ny = j – 1;return openStates[nx * N + ny] && connectStatesBW.connected(nx * N + ny + 1, 0);}// does the system percolate?public boolean percolates() {return connectStates.connected(0, N * N + 1);}}
PercolationStats编程分析：
用蒙特卡洛（Monte Carlo）方法进行仿真分析，确定渗透阈值p，具体方法是：
进行以下统计操作。
按照下式计算均值与方差：
假设T值足够大（至少30次），则可以根据下式计算置信区间在95%的的渗透阈值范围：
即使是不成熟的尝试，也胜于胎死腹中的策略。
