首页 > 代码库 > Programming Assignment 1: Percolation
Programming Assignment 1: Percolation
问题描述可以详见：http://coursera.cs.princeton.edu/algs4/assignments/percolation.html
关于QuickFindUF的javadoc:http://algs4.cs.princeton.edu/15uf/QuickFindUF.java.html
关于WeightedQuickUnionUF的javadoc:http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionUF.java.html
附言：（引用于http://blog.csdn.net/revilwang/article/details/10823467）
关于这个模型，其实存在一个问题，在算法课程的论坛上，讨论的热度很高。问题是这样的：
由于引入虚拟的顶层区域和虚拟的底层区域，那么当模型渗透的时候，可能会出现下图的情况
如右边图所示，由于所有的底层区域都和虚拟底层区域相连，所以一旦当区域渗透，则和其他的底层开启区域相连的区域也显示为区域满状态。而实际的情况应该是按照左图所示。这个问题称为 backwash，个人把这个翻译成“回流”。引入虚拟底层区域，很难避免这个问题。讨论的结果，有两种方式可以改进：
1. 不使用虚拟底层区域，只保留顶层，判断是否渗透的时候用虚拟顶层和一个for循环来判断。
2. 保留虚拟底层区域，另外加一个不使用虚拟底层的模型，将两个模型结合在一起来判断是否渗透，通过浪费一些内存来保证效率。
backwash的情况导致Percolation.java在测试时public void isfull(int i, int j) 方法出现错误，这一点从上面两张图也可以明显的看出来。（而解决的办法通过上面两种方法实现)
下面两段代码是从http://www.cnblogs.com/tiny656/p/3820653.html 复制来的，因为自己写的没有考虑到backwash的情况，所以有一些错误，就不挂上来误人子弟了。
Percolation.java
public class Percolation { private boolean[] matrix; private int row, col; private WeightedQuickUnionUF wquUF; private WeightedQuickUnionUF wquUFTop; private boolean alreadyPercolates; public Percolation(int N) { if (N < 1) throw new IllegalArgumentException("Illeagal Argument"); wquUF = new WeightedQuickUnionUF(N*N+2); wquUFTop = new WeightedQuickUnionUF(N*N+1); alreadyPercolates = false; row = N; col = N; matrix = new boolean[N*N+1]; } private void validate(int i, int j) { if (i < 1 || i > row) throw new IndexOutOfBoundsException("row index i out of bounds"); if (j < 1 || j > col) throw new IndexOutOfBoundsException("col index j out of bounds"); } public void open(int i, int j) { validate(i, j); int curIdx = (i-1)*col + j; matrix[curIdx] = true; if (i == 1) { wquUF.union(curIdx, 0); wquUFTop.union(curIdx, 0); } if (i == row) { wquUF.union(curIdx, row*col+1); } int[] dx = {1, -1, 0, 0}; int[] dy = {0, 0, 1, -1}; for (int dir = 0; dir < 4; dir++) { int posX = i + dx[dir]; int posY = j + dy[dir]; if (posX <= row && posX >= 1 && posY <= row && posY >= 1 && isOpen(posX, posY)) { wquUF.union(curIdx, (posX-1)*col+posY); wquUFTop.union(curIdx, (posX-1)*col+posY); } } } public boolean isOpen(int i, int j) { validate(i, j); return matrix[(i-1)*col + j]; } public boolean isFull(int i, int j) { validate(i, j); int curIdx = (i-1)*col+j; if (wquUFTop.find(curIdx) == wquUFTop.find(0)) return true; return false; } public boolean percolates() { if (alreadyPercolates) return true; if (wquUF.find(0) == wquUF.find(row*col+1)) { alreadyPercolates = true; return true; } return false; } public static void main(String[] args) { Percolation perc = new Percolation(2); perc.open(1, 1); perc.open(1, 2); perc.open(2, 1); System.out.println(perc.percolates()); } }
PercolationStats.java
public class PercolationStats { private double[] x; private int expTime; public PercolationStats(int N, int T) { // perform T independent experiments on an N-by-N grid if (N <= 0 || T <= 0) throw new IllegalArgumentException("Illeagal Argument"); x = new double[T+1]; expTime = T; for (int i = 1; i <= T; i++) { Percolation perc = new Percolation(N); while (true) { int posX, posY; do { posX = StdRandom.uniform(N) + 1; posY = StdRandom.uniform(N) + 1; } while(perc.isOpen(posX, posY)); perc.open(posX, posY); x[i] += 1; if (perc.percolates()) break; } x[i] = x[i]/(double) (N * N); } } public double mean() { // sample mean of percolation threshold double u = 0.0; for (int i = 1; i <= expTime; i++) { u += x[i]; } return u / (double)expTime; } public double stddev() { // sample standard deviation of percolation threshold double q = 0.0; double u = mean(); for (int i = 1; i <= expTime; i++) { q += (x[i]-u)*(x[i]-u); } return Math.sqrt(q / (double)(expTime - 1)); } public double confidenceLo() { // low endpoint of 95% confidence interval double mu = mean(); double sigma = stddev(); return mu - 1.96*sigma / Math.sqrt(expTime); } public double confidenceHi() { // high endpoint of 95% confidence interval double mu = mean(); double sigma = stddev(); return mu + 1.96*sigma / Math.sqrt(expTime); } public static void main(String[] args) { // test client (described below) int N = Integer.parseInt(args[0]); int T = Integer.parseInt(args[1]); PercolationStats percStats = new PercolationStats(N, T); StdOut.printf("mean = %f\n", percStats.mean()); StdOut.printf("stddev = %f\n", percStats.stddev()); StdOut.printf("95%% confidence interval = %f, %f\n", percStats.confidenceLo(), percStats.confidenceHi()); }}
Programming Assignment 1: Percolation