model & problem

(原文描述太啰嗦了)
A system using an N-by-N grid of sites.
→ Each site is either open or blocked.
→ A full site is an open site that can be connected to an open site in the top row via a chain of neighboring open sites. (这个full的定义有玄机 而且导致后面写程序时有个问题, 看论坛想了半天才想出来, 见后文.)
→ We say the system percolates if there is a path of connected open sites form the top row to the bottom row.

⇒ pb: if sites are independently set to be open with probability p, what is the probability that the system percolates?

→ When N is sufficiently large, there is a threshold value **p such that when p < p a random N-by-N grid almost never percolates, and when p > p, a random N-by-N grid almost always percolates.
→ No mathematical solution for determining the percolation threshold p has yet been derived.
⇒ Your task is to *write a computer program to estimate p.

Method

• API:

  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 open 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?
     public static void main(String[] args   // test client (optional)
  }
  

• Corner cases: the row and column indices i and j are integers between 1 and N. 1≤i,j≤N

if i/j out of range: java.lang.IndexOutOfBoundsException if N<=0 in constructor: java.lang.IllegalArgumentException

• Performance requirements: N2 for constructor, const for other operations

• Monte Carlo simulation

  • all sites init to be closed

  → randomly choose a blocked site (i,j) and open it → repeat until percolates ⇒ the fraction of opened sites is an estimation of p*

• ex. 20*20 grid, when percolated:

⇒ estimated p* = 204/400=0.51

• repeat the estimation for T times, get T estimations

  → get mean and std:
  
  → 95% 置信区间:
  

• create API for this simulation:

  public class PercolationStats {
     public PercolationStats(int N, int T)     // perform T independent experiments on an N-by-N grid
     public double mean()                      // sample mean of percolation threshold
     public double stddev()                    // sample standard deviation of percolation threshold
     public double confidenceLo()              // low  endpoint of 95% confidence interval
     public double confidenceHi()              // high endpoint of 95% confidence interval
     public static void main(String[] args)    // test client (described below)
  }
  

  -if N ≤ 0 or T ≤ 0: java.lang.IllegalArgumentException
  -main() : takes two command-line arguments N and T
  ⇒ performs T independent computational experiments on an N-by-N grid, and prints out the mean, standard deviation, and the 95% confidence interval for p*.
  (Use standard random from our standard libraries to generate random numbers; use standard statistics to compute the sample mean and standard deviation.
  Here is the algo API: http://algs4.cs.princeton.edu/code/index.php)

Code

注意一定要用它们提供的那些库, 否则自己写的话代码就长了....
shuffle, mean, stddev什么的直接用他们的函数库就可以做到.
http://algs4.cs.princeton.edu/code/index.php
另外UF也是用他们写好的, WeightedQuickUnionUF.

按照提示, 除了格子的N^2个节点以外再增加两个节点: 顶部和底部的虚拟节点. 这里写的时候注意一开始也是不恩能够把它们与第一行/最后一行相连的 — 要在一个格子open以后再相连.

backwash问题

这次题目有一点比较困难就是, 需要实现isFull()函数, 这个函数判断一个格子(i,j)是否和顶部相连. 这里如果直接用UF的connected()判断是否和顶部虚拟节点相连的话是有问题的, 如下图:

白色格子表示格子是open的, 蓝色格子表示格子是open并且是full的(i.e. 和顶部相连的), 左边图片里的状态是对的, 右边图片里底下部分的格子状态则不对: 如左下角的格子, 其实是没有和顶部联通的, 如果我们用两个虚拟节点的话, 由于底部虚拟节点和顶部虚拟节点相连, 所以和底部虚拟节点相连的左下角部分就被判断成了full的.

这个问题一开始我以为可以很简单解决, 后来发现没那么容易... (注意题目还要求isFull()也要在常数时间给出结果).
一个不优雅的办法是, 建立两个UF, 一个用来判断percolation, 另一个UF里没有底部虚拟节点所以可以专门用来判断isFull().

这样解决的话使可以通过测试, 不过非常不好看, 另外一个UF的内存占用是8N^2(内部有size[]和id[]两个int数组), 比较大.

在论坛上找了半天, 看了一些人的分享终于想到了这个非常妙的办法:

1. UF只建立顶部虚拟节点, 不建立底部虚拟节点.
2. 判断isFull只需要用UF的connected()一下就好了
3. 问题是怎么判断percolation:
   a. 建立一个数组 boolean connectedToBottom[], 指示某一点是否和底部相连
   b. trick在这里: 不必修改一个联通分支的所有点的connectedToBottom的值, 只需要修改联通分支的root(UF的find)即可. 在进行union的时候先查看两个component的root是不是连到底部, 然后有一个连到底部的话, 在union以后把合并后的联通分支的connectedToBottom状态改为true即可
   c. 然后判断percolate: 先找到顶部虚拟节点锁在component的root, 然后看这个root是否连到底部即可!

这样用一个boolean数组(N^2内存)代替了一个新的UF(8N^2内存), 而且实现也更加优雅.
非常有意思的练习...