求解系统的渗透阈值——基于union-find算法

桃扇骨 2022-05-12 15:18 151阅读 0赞

问题描述：[http://coursera.cs.princeton.edu/algs4/assignments/percolation.html][http_coursera.cs.princeton.edu_algs4_assignments_percolation.html]

Percolation的求解基于Union-Find算法，这里用了Quick Find和Weighted Quick Union算法，并对两种算法进行了比较。

首先建立渗透模型类：

/ **
    *  @Author DXH924 
    *  Xidian University
    */
    /*渗透模型*/
    import java.lang.Math;
    public class Percolation{
    	static int[][] a;//虚拟化网格
    	static int[] id;//每个网格对应的id，相同id的网格视为连通
    	
    	public int size;//网格数量
    	public int cnt=0;//“开启”的网格数
    	public int top, bottom;//增加两个虚拟化的网格（顶部和底部）
    	public Percolation(int N){
    		a=new int[N][N];
    		size=N*N+2;
    		top=size-2;
    		bottom=size-1;
    		id=new int[size];
    		
    		for (int i=0; i<size; i++)
    			id[i]=i;
    	
            //将系统顶部与底部分别抽象为一个网格
    		for (int i=0; i<N; i++)
    			id[i]=id[top];
    		for (int i=size-2-N; i<size-2; i++)
    			id[i]=id[bottom];
    	}//渗透系统初始化
    	
    	public void open(int i, int j){
    		a[i][j]=1;
    		cnt++;
    	}//开启网格(i, j)
    	
    	public boolean isOpen(int i, int j){
    		return a[i][j]==1;
    	}//网格是否开启
    	
    	public boolean isFull(int i, int j){
    		return a[i][j]==0;
    	}//网格是否阻塞
    	
    	public void union(int p, int q){
    		int pID=find(p), qID=find(q);
    		if (pID==qID)
    			return;
    		for (int i=0; i<size; i++)
    			if (id[i]==pID)
    				id[i]=qID;
    	}//基于QF的连通方式
    	
    	public int find(int p){
    		return id[p];
    	}//找到连通分量的id
    	
    	public boolean connected(int i, int j){
    		return find(i)==find(j);
    	}//判断i与j是否连通
    
    	public boolean percolates(){
    		if (connected(top, bottom)) 
    			return true;
    		return false;
    	}//判断系统是否渗透
    	
    	public void set(int N){
    		 	int i=(int)(Math.random()*N);
    			int j=(int)(Math.random()*N);
    			if (isOpen(i, j))
    				return;
    			open(i,  j);//设置open格点
    			int p, q=0;//p为(i,j)的格子,q为p相邻的格子
    			p=i*N+j;
    			if (i-1>=0){
    				q=p-N;
    				if (a[i-1][j]==1)
    					union(p, q);
    			}	
    			if (j+1<N){
    				q=p+1;
    				if (a[i][j+1]==1)
    					union(p, q);
    			}	
    			if (i+1<N){
    				q=p+N;
    				if (a[i+1][j]==1)
    					union(p, q);
    			}
    			if (j-1>=0){
    				q=p-1;
    				if (a[i][j-1]==1)
    					union(p, q);
    			}	
    	}//连通与(i, j)相邻的网格
    	
    	public double test(int N){
    		while (!percolates()){
    			int i=(int)(Math.random()*N);
    			int j=(int)(Math.random()*N);
    			set(N);
    		}
    		double mean=cnt*1.0/(size-2);
    		return mean;
    	}//计算渗透阈值
    }//based on Quick Find
    
    /*QuickFind类*/
    public class QF extends Percolation{
    	public QF(int N){
    		super(N);
    	}
    }
    
    /*WeightedQuickUnion类*/
    public class WQU extends Percolation{
    	public int[] sz;//连通分量的大小
    	public WQU(int N){
    		super(N);
    		sz=new int[size];
    		for (int i=0; i<size; i++)
    			sz[i]=1;
    	}
    	
    	public void union(int p, int q){
    		int i=find(p), j=find(q);
    		if (i==j)
    			return;
    		if (sz[i]<sz[j]){
    			id[i]=j;
    			sz[j]+=sz[i];
    		}
    		else{
    			id[j]=i;
    			sz[i]+=sz[j];
    		}
    	}//基于Weighted Quick Union, 根据权重连通分量
    	
    	public int find(int p){
    		while (id[p]!=p)
    			p=id[p];
    		return p;
    	}//寻找与p连通的分量id
    }//based on Weight Quick Union

计算及测试类：

/*计算及测试类*/
    public class PercolationStats {
    	int N, T;//N为系统规模，T为测试数据组数
    	double sample[];//每组测试数据样本值
    	double mean=0, stddev, lo, hi;//渗透阈值，标准差以及置信区间
    	double start, end, runtime;//运行时间
    
    	public PercolationStats(int N, int T, String arg){
    		this.N=N;
    		this.T=T;
    		sample=new double[T];
    		
    		start=System.currentTimeMillis();
            if (arg.equals("Quick Find"))
    			for (int i=0; i<T; i++){
    				Percolation qf=new QF(N);
    				sample[i]=qf.test(N);
    				}
    		
    		if (arg.equals("Weighted Quick Union"))
    			for (int i=0; i<T; i++){
    				Percolation wqu=new WQU(N);
    				sample[i]=wqu.test(N);
    				}
    		end=System.currentTimeMillis();
    		runtime=end-start;
    	}
    	
    	// sample mean of percolation threshold
    	public double mean(){
    		double sum=0;
    		for (int i=0; i<T; i++)
    			sum+=sample[i];
    		mean=sum/T;
    		return mean;
    	}
    		
    	// sample standard deviation of percolation threshold 
    	public double stddev(){
    		double sigma_2, sum=0;
    		for (int i=0; i<T; i++)
    			sum+=(sample[i]-mean)*(sample[i]-mean);
    		sigma_2=sum/(T-1);
    		stddev=Math.sqrt(sigma_2);
    		return stddev;
    		}
    		
    	//returns lower bound of the 95% confidence interval 
    	public double confidenceLo(){
    		lo=mean-1.96*stddev/Math.sqrt(T);
    		return lo;
    	}
    		
    	//returns upper bound of the 95% confidence interval
    	public double confidenceHi(){
    		hi=mean+1.96*stddev/Math.sqrt(T);
    		return hi;
    	}
    }
    
    import java.util.*;
    public class PercolationTest {
    	public static void main(String[] args){
    		int N, T;
    		String arg1="Quick Find";
    		String arg2="Weighted Quick Union";
            System.out.println("enter N and T:");
    		Scanner input=new Scanner(System.in);
    		N=input.nextInt();
    		T=input.nextInt();
    		for (int i=0; i<5; i++, N*=2){
    			PercolationStats qf=new PercolationStats(N, T, arg1);
    			PercolationStats wqu=new PercolationStats(N, T, arg2);
    			show(qf, arg1);
    			show(wqu, arg2);
    			System.out.println("When N = "+N+" ,");
    			System.out.println(arg2+" is "+qf.runtime/wqu.runtime+" times faster than "+arg1);
    			System.out.println();
    		}					
    	}
    	
    	public static void show(PercolationStats t, String arg){
    		System.out.println(arg);
    		System.out.println("N = "+t.N+", T = "+t.T);
    		System.out.println("mean           = "+t.mean());
    		System.out.println("stddev         = "+t.stddev());
    		System.out.println("confidenceLow  = "+t.confidenceLo());
    		System.out.println("confidenceHigh = "+t.confidenceHi());
    		System.out.println("running time   = "+t.runtime+"ms\n");
    	}
    }

测试样例：

enter N and T:
    20 50
    Quick Find
    N = 20, T = 50
    mean           = 0.59345
    stddev         = 0.05346153013225148
    confidenceLow  = 0.5786312198882635
    confidenceHigh = 0.6082687801117366
    running time   = 14.0ms
    
    Weighted Quick Union
    N = 20, T = 50
    mean           = 0.59695
    stddev         = 0.04694843567409778
    confidenceLow  = 0.583936557565348
    confidenceHigh = 0.609963442434652
    running time   = 8.0ms
    
    When N = 20 ,
    Weighted Quick Union is 1.75 times faster than Quick Find
    
    Quick Find
    N = 40, T = 50
    mean           = 0.6013999999999999
    stddev         = 0.02381052974065492
    confidenceLow  = 0.5948000578790416
    confidenceHigh = 0.6079999421209583
    running time   = 49.0ms
    
    Weighted Quick Union
    N = 40, T = 50
    mean           = 0.59295
    stddev         = 0.031969283328385896
    confidenceLow  = 0.5840885667637791
    confidenceHigh = 0.6018114332362209
    running time   = 34.0ms
    
    When N = 40 ,
    Weighted Quick Union is 1.4411764705882353 times faster than Quick Find
    
    Quick Find
    N = 80, T = 50
    mean           = 0.5915874999999999
    stddev         = 0.01903813368268796
    confidenceLow  = 0.5863103985761594
    confidenceHigh = 0.5968646014238405
    running time   = 453.0ms
    
    Weighted Quick Union
    N = 80, T = 50
    mean           = 0.59128125
    stddev         = 0.021882378493217065
    confidenceLow  = 0.5852157641373505
    confidenceHigh = 0.5973467358626494
    running time   = 48.0ms
    
    When N = 80 ,
    Weighted Quick Union is 9.4375 times faster than Quick Find
    
    Quick Find
    N = 160, T = 50
    mean           = 0.5930671875
    stddev         = 0.010708300388289247
    confidenceLow  = 0.5900989980667396
    confidenceHigh = 0.5960353769332604
    running time   = 6405.0ms
    
    Weighted Quick Union
    N = 160, T = 50
    mean           = 0.5936234375
    stddev         = 0.012259872074749474
    confidenceLow  = 0.5902251743372303
    confidenceHigh = 0.5970217006627697
    running time   = 198.0ms
    
    When N = 160 ,
    Weighted Quick Union is 32.34848484848485 times faster than Quick Find
    
    Quick Find
    N = 320, T = 50
    mean           = 0.5923541015624999
    stddev         = 0.006205852182211583
    confidenceLow  = 0.5906339270993554
    confidenceHigh = 0.5940742760256444
    running time   = 99309.0ms
    
    Weighted Quick Union
    N = 320, T = 50
    mean           = 0.5916140625000001
    stddev         = 0.0081841638093851
    confidenceLow  = 0.5893455280306407
    confidenceHigh = 0.5938825969693596
    running time   = 807.0ms
    
    When N = 320 ,
    Weighted Quick Union is 123.05947955390334 times faster than Quick Find

<table>  各种union-find算法在N个触点成本时的性能特点（最坏情况）  
 <thead> 
  <tr> 
   <th style="width:230px;">算法</th> 
   <th style="width:205px;">构造函数</th> 
   <th style="width:211px;">union()</th> 
   <th>find()</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="width:230px;">quick-find</td> 
   <td style="width:205px;">N</td> 
   <td style="width:211px;">N</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td style="width:230px;">quick-union</td> 
   <td style="width:205px;">N</td> 
   <td style="width:211px;">树的高度</td> 
   <td>树的高度</td> 
  </tr> 
  <tr> 
   <td style="width:230px;">加权quick-union</td> 
   <td style="width:205px;">N</td> 
   <td style="width:211px;">lgN</td> 
   <td>lgN</td> 
  </tr> 
  <tr> 
   <td style="width:230px;">路径压缩加权quick-union</td> 
   <td style="width:205px;">N</td> 
   <td style="width:211px;">→1</td> 
   <td>→1</td> 
  </tr> 
  <tr> 
   <td style="width:230px;">理想情况</td> 
   <td style="width:205px;">N</td> 
   <td style="width:211px;">1</td> 
   <td>1</td> 
  </tr> 
 </tbody> 
</table>

[http_coursera.cs.princeton.edu_algs4_assignments_percolation.html]: http://coursera.cs.princeton.edu/algs4/assignments/percolation.html