普林斯顿大学算法Week1: Percolation 渗透(98

Welcome To My Blog

总结

视频讲述了并查集算法的细节,作业是该算法的实际应用

1. 下载algs4.jar,并添加到CLASSPATH中

2. 使用algs4.jar中的工具:求均值,求标准差,输入输出

3. 需要传入外部参数的方法都得进行参数检测,否则扣分

4. UnionFind算法的输入是一维的,Percolation系统是n*n的格子,每个site由坐标对(x,y)表示,
   所以要想描述点与点之间的关系,得先将二维坐标转换成一维的数值,我采用的转换规则是:(x,y)→x*(n+1)+y
   (1,1)到(n,n) 对应n+2到n*(n+2),注意:一维数值并不是连续的
   可以采用其它转换规则,比如易于理解的(x,y)→x*(n+2)+y,第5条有进一步的说明

5. 之所以采用如上的转换规则:
   其一,方便判断某个点的上下左右邻居时不会有数组越界异常,对于四周的site来说,并不都有四个邻点(如下图3*3.png,左上角的点1没有上邻居和左邻居,扩充为5*5.png后,点1就有上下左右四个邻居了)
   其二,节省空间,最容易理解的是使用(n+2)*(n+2)长的一维数组(如下图3*3.png和5*5.png),使用(n+2)*(n+1)+1长的也行,因为在转换规则的约束下,所有site的一维表示都是唯一的,并且最大值等于(n+2)*(n+1)

6. 要区分好block,open,full这三个状态,block对应false,open对应true,full表示某个site和上虚拟点相连

7. 为方便判断系统为渗透状态,在n*n格子的上下分别加两个虚拟的点,
   代码中:索引为0的代表上虚拟点,索引为(n+1)*(n+1)代表下虚拟点(找两个没用的索引值即可)
   这样做会导致backwash问题(即回流问题),因为在open方法中第n行的所有site都和下虚拟点union过了

8. 解决backwash问题,需要再创建一个并查集对象,即代码中的uf2,该对象不将最后一行和下虚拟点相连,在isFull方法中使用uf2的connected方法就不会导致backwash问题了
   

   3*3.png

代码

Percalation.java

/**
 * @author Sasuke
 * @date 25/1/2018
 */

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {
   // n*n grid
   private int n ; 
   //status of each site
   private boolean[] eachStatus ; 
   //number of open site
   private int openNum;
   //UF alg with virtual site
   private WeightedQuickUnionUF uf1;
   //UF alg with only top site due to backwash
   private WeightedQuickUnionUF uf2;

   // create n-by-n grid, with all sites blocked
   public Percolation(int n){   
    if(n<=0) throw new IllegalArgumentException("illegal value of n!");
    this.n = n;
    //plus two virtual site
    eachStatus = new boolean[(n+1)*(n+2)]; 
    
    //all sites are blocked
    for(int i=0; i< eachStatus.length;i++) eachStatus[i]=false;
    // grid with top site and bottom site
    uf1 = new WeightedQuickUnionUF((n+1)*(n+2));
    // grid with only bottom site
    uf2 = new WeightedQuickUnionUF((n+1)*(n+2));
   }

   //translate 2 dimentional coordinate to 1 dimentional pattern
   private int oneDimention(int row, int col){
    return row*(n+1)+col;
   }
   // open site (row, col) if it is not open already
   public void open(int row, int col){
    if(row<1 || row>n || col<1 || col>n) throw new IllegalArgumentException("illegal row or col!");
    if(!isOpen(row,col)) {
        eachStatus[oneDimention(row,col)]=true;
        openNum++;
        int temp1 = oneDimention(row,col);
        //if neighbor could be connected?
        if(row==1){
            uf1.union(0,temp1);
            uf2.union(0,temp1);
        }
        if(row==n) { 
            uf1.union((n+1)*(n+1),temp1);
        }
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};
        for(int i=0; i<4;i++){
            int tempX = row+dx[i];
            int tempY = col+dy[i];
            int temp2 = oneDimention(tempX,tempY);
            if (eachStatus[temp2]){
                uf1.union(temp1,temp2);
                uf2.union(temp1,temp2);
             }
            }
    }
   }    

   //is site (row, col) open?
   public boolean isOpen(int row, int col){
       if(row<1 || row>n || col<1 || col>n) throw new IllegalArgumentException("illegal row or col!");
       return eachStatus[oneDimention(row,col)];
   }  

   //is site (row, col) full?
   public boolean isFull(int row, int col){
    if(row<1 || row>n || col<1 || col>n) throw new IllegalArgumentException("illegal row or col!");
    return uf2.connected(0,oneDimention(row,col));
   }

   // number of open sites
   public int numberOfOpenSites() {
    return openNum;
   }
   
   // does the system percolate?
   public boolean percolates() {
    return uf1.connected(0,(n+1)*(n+1));
   }

   // test client (optional)
   public static void main(String[] args) {
     Percolation p = new Percolation(3);
     p.open(1, 2);
     p.open(2, 2);
     p.open(3, 2);
     StdOut.println(p.isOpen(1,1));
     StdOut.println(p.percolates());
   }
   
}

PercolationStats.java

/**
 * @author Sasuke
 * @date 25/1/2018
 */

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;

public class PercolationStats {
    //trial times
    private int trialNum;
    //threshold P
    private double[] preP;
    public PercolationStats(int n,int trialNum) {
        if (n<1 || trialNum<1) throw new IllegalArgumentException("Illegal n or trialNum,please check");
        this.trialNum = trialNum;
        preP = new double[trialNum];
        for(int i=0;i<trialNum;i++) {
            Percolation p = new Percolation(n);
            while(!p.percolates()) {
                int row = StdRandom.uniform(n)+1;
                int col = StdRandom.uniform(n)+1;
                p.open(row,col);
                if (p.percolates()) break;
            }
            preP[i] = (double)p.numberOfOpenSites()/(n*n);
        }
    }
    
    // mean of p
    public double mean() {
        return StdStats.mean(preP);
    }
    
    // standard deviation
    public double stddev() {
        return StdStats.stddev(preP);
    }
    
    //confidence interval:low
    public double confidenceLo() {
        return mean()-1.96*stddev()/Math.sqrt(trialNum);
    }
    
    //confidence interval:high
    public double confidenceHi() {
        return mean()+1.96*stddev()/Math.sqrt(trialNum);
    }
    
    public static void main(String[] args) {
        int n =10,trialNum=1000;
        PercolationStats ps = new PercolationStats(n,trialNum);
        StdOut.println("grid size :" + n+"*"+n);
        StdOut.println("trial times :" + trialNum);
        StdOut.println("mean of p :"+ ps.mean());
        StdOut.println("standard deviation :"+ps.stddev());
        StdOut.println("confidence interval low :"+ps.confidenceLo());
        StdOut.println("confidence interval high :"+ps.confidenceHi());
    }
    
    
}