HW2-Percolation
要求
实现蒙特卡洛模拟下的渗透模拟
具体来说，给一个N*N的方格，可以将某些方格挖空，若从最顶层挖，则上方会有水流流下，并蔓延到相邻的空格中。
不同开放方格概率下，生成渗透（水流从上贯通到下）的概率不同
在\(N=100\)下，开放方格概率\(p*=0.593\)时，渗透率出现突变，意味着在这之前几乎没有可以渗透的情况，在这之后几乎都是渗透的情况
作业要求使用模拟求出不同情况下\(p*\)的价值
Percolation class
实现以下API
1
2
3
4
5
6
7
8
public class Percolation {
public Percolation(int N) // create N-by-N grid, with all sites initially blocked
public void open(int row, int col) // open the site (row, col) if it is not open already
public boolean isOpen(int row, int col) // is the site (row, col) open?
public boolean isFull(int row, int col) // is the site (row, col) full?
public int numberOfOpenSites() // number of open sites
public boolean percolates() // does the system percolate?
}The
WeightedQuickUnionUF class
作业提供了一个带权并查集的类，实现以上API时必须要用到该并查集，接口如下：
1
2
3
4
5
6
7
public class WeightedQuickUnionUF {
public WeightedQuickUnionUF(int n) // creates a UF with n elements
public int count() // number of disjoint sets
public int find(int p) // the root of p's set
public boolean connected(int p, int q) // whether p and q are in the same set
public void union(int p, int q) // join p and q's sets together
}backwash问题
在试图使用一个并查集来维护连通性与是否填满时，出现了意料之外的bug
如图
此时B到N已经被打通，实现了渗透
这时打通LP，会发现程序也会将水填到这两块地方，因为在当前并查集中
- L与P相连，P与（虚拟）底部相连
- B与F与J与N相连，N与（虚拟）底部相连
- 而两个（虚拟）底部是同一个，并查集会通过底部判断N与P相连
这就不符合我们的要求了
为解决这个问题，我们选择再开一个并查集单独维护某格是否被填满的情况，这个并查集不会与（虚拟）底部相连，也就避免了与连通性混淆，具体的：在row==size-1时，不对新并查集进行合并
1
2
3
4
5
6
if(row==0){
uf.union(top,idx);
ufFull.union(top, idx);
}
if(row==size-1) uf.union(bottom,idx);以及判断时分开使用
1
2
3
4
5
6
public boolean isFull(int row, int col) {
if (!valid(row, col)) throw new IndexOutOfBoundsException();
if(!isOpen(row,col)) return false;
int idx = convert(row, col);
return ufFull.connected(top,idx);
}虚拟顶部/底部问题
最初，本人使用0作为虚拟顶部，size-1作为虚拟底部，但这会造成下标的冲突
因为并查集中，对于每个坐标的idx是通过$ + $计算的，可能会造成size-1或0与计算的格点坐标冲突以导致结果错误。
因此，需要将虚拟顶部与底部的值设置一个超出格点范围（0~size*size-1）的值，这里我们设置虚拟顶部为\(\text{size}\times \text{size}\)，虚拟底部为\(\text{size}\times \text{size}+1\)
1
2
top =size*size;
bottom = size*size+1;实例变量设置
1
2
3
4
5
6
7
8
9
public int[][] grid; // 存储方格是被阻挡还是被挖空
public int open; // 存储挖空数量
public int size = 0; // 记录尺寸
private WeightedQuickUnionUF uf; // 记录是否渗透的并查集
private WeightedQuickUnionUF ufFull; // 记录某格是否填满的并查集
private int[] dx = {0,0,1,-1};
private int[] dy = {1,-1,0,0};
private int top;
private int bottom;构造函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public Percolation(int N) {
if(N<=0){
throw new IllegalArgumentException();
}
grid = new int[N][N];
open = 0;
size = N;
top =size*size;
bottom = size*size+1;
uf = new WeightedQuickUnionUF(size*size+2);
ufFull = new WeightedQuickUnionUF(size*size+1);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
grid[i][j] = 1;
}
}
}对并查集初始化，并设置虚拟顶部与底部，将数组初始化为全被阻挡的初始状态
open
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public void open(int row, int col) {
if (!valid(row, col)) throw new IndexOutOfBoundsException();
if (isOpen(row, col)) return;
grid[row][col] = 0;
open++;
int idx = convert(row, col);
if(row==0){
uf.union(top,idx);
ufFull.union(top, idx);
}
if(row==size-1) uf.union(bottom,idx);
for (int i = 0; i<4;i++){
int nr = row+dx[i];
int nc = col+dy[i];
if(nr < 0 ||nr>size-1|| nc < 0 ||nc>size-1) continue;
if (isOpen(nr,nc)){
int tidx = convert(nr,nc);
uf.union(idx, tidx);
ufFull.union(idx, tidx);
}
}
}首先判断是否合法以及是否已经是开放
然后将该格标记为开放，并计算该格对应并查集idx
为了防止backwash，第一行都与顶部连通，而最后一行判断full的并查集不与底部连通
循环判断四个方位是否连通，若连通则在并查集标记
isFull
1
2
3
4
5
6
public boolean isFull(int row, int col) {
if (!valid(row, col)) throw new IndexOutOfBoundsException();
if(!isOpen(row,col)) return false;
int idx = convert(row, col);
return ufFull.connected(top,idx);
}判满使用单独的并查集，计算idx值并判断与顶部是否连通即可
percolates
1
2
3
public boolean percolates() {
return uf.connected(top,bottom);
}判断是否渗透，用渗透并查集判断顶部与底部是否相连即可