普林斯頓大學(xué)算法第一部分學(xué)習(xí)總結(jié)（Week1-Percolation）

Algorithms Part1課程第一周的Programming Assignment是Percolation問題，該問題是Union-Find算法的一個應(yīng)用實例。作業(yè)要求見以下鏈接：http://coursera.cs.princeton.edu/algs4/assignments/percolation.html，要求用Java實現(xiàn)算法。此外該課程使用了作者提供的API用以簡化編程，如基本輸入、輸出、隨機數(shù)生成、數(shù)據(jù)分析等庫函數(shù)，在上述鏈接中可直接下載。

模型描述：

Percolation即滲透過程，其模型如下：一個方形“水槽”（system）由N*N個方格（site）組成，每個方格有開啟（open）或關(guān)閉（blocked）兩個狀態(tài)，相鄰（即上下左右）的開啟格子能夠構(gòu)成一條同路。如果一個格子處于開啟狀態(tài)，并且與頂端的一行能夠通過開啟的格子實現(xiàn)連通（connected）通路，我們說這個格子處于充滿水（full）的狀態(tài)；如果一個“水槽”（system）的頂端格子與底部格子通過開啟的格子實現(xiàn)了連通，我們稱這個“水槽”是可以滲透（percolates）的。如下圖所示：

image.png

第一章的作業(yè)需要制作兩個類。第一個Percolation包含五個方法，主要是用來打開滲漏的格子。第二個類PercolationStats 同樣有五個方法，用來找出N*N格子中，能夠產(chǎn)生滲漏的閾值概率的95%置信區(qū)間。先說一下大概的想法和原理。官網(wǎng)上提供有這道題目的思路，就是在創(chuàng)建格子的過程中首先要在頂層和底層各加一層，這樣的話在測試是否滲漏時直接測試（0，1）和（N+1,1）就好了首先來說下第一個類：官網(wǎng)的API已經(jīng)寫好：

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)  
}
  1. 構(gòu)造函數(shù) Percolation
    該構(gòu)造方法對模型初始化，我們創(chuàng)建一個NN大小的一維布爾數(shù)組作為“水槽”，數(shù)組值記錄每個格子的開閉狀態(tài)，初始狀態(tài)為關(guān)閉。此外，我們需要另一個(NN+2)大小的一維數(shù)組存儲連通關(guān)系，根據(jù)Union-Find算法的學(xué)習(xí)，我們創(chuàng)建類型為WeightedQuickUnionUF的數(shù)組。大小之所以為(N*N+2)，是因為在檢查是否滲透的時候，可以通過在頂部與底部設(shè)置兩個虛擬點，其與頂端或底部的一排是相連通的，這樣檢查是否滲透的時候，無需遍歷頂部或底部一排的每一個點，只需要檢查兩個虛擬點是否連通即可，如下圖所示：
    image.png
  2. 打開格子方法open
    檢查坐標(biāo)為(i, j)的點是否開啟，如果沒有開啟，則將其開啟。注意i，j的取值范圍為1~N。此外，開啟格子后，需要檢查其上下左右的格子是否同樣已經(jīng)打開，如果已經(jīng)打開，則通過WeightedQuickUnionUF的union()方法將兩個格子連通起來；另外根據(jù)作業(yè)要求，需要首先檢查是否越界，拋出java.lang.IndexOutOfBoundsException()錯誤；
  3. isOpen(int i, int j)：只需要返回該點的開閉狀態(tài)值；
  4. isFull(int i, int j)：檢查該點是否已經(jīng)打開并且已經(jīng)與頂部的虛擬點（相當(dāng)于頂部的一排）連通，用WeightedQuickUnionUF的connected()方法檢測；
  5. percolates()：檢查頂部的虛擬點與底部的虛擬點是否連通，用WeightedQuickUnionUF的connected()方法檢測；

注意：

  • 加入虛擬節(jié)點。首虛擬節(jié)點與第一層所有打開的元素相關(guān)聯(lián)，尾虛擬節(jié)點和最后一層所有打開的節(jié)點相關(guān)聯(lián)。如果首尾虛擬節(jié)點在一個集合中，那么系統(tǒng)是滲透成功的。 但是也會出現(xiàn)一個問題（backwash），因為有一些格子雖然從上面不能滲透到，但和尾虛擬節(jié)點連接后，他們也和首虛擬節(jié)點在一個集合了。
  • 使用兩個并查集避免backwash。一個只負(fù)責(zé)維護首虛擬節(jié)點，當(dāng)進行isFull判斷是否只考慮這個并查集，另一個并查集進行首尾虛擬節(jié)點的維護，用在percolates的判斷中。
image.png
  • 在用一維數(shù)組模擬二維“水槽”時，我們用i，j坐標(biāo)進行表示，(i, j)表示的是數(shù)組中序號為(i - 1)*N + (j - 1)的元素；此外，由于虛擬點的設(shè)置，坐標(biāo)的對應(yīng)容易出現(xiàn)混亂，需要首先考慮清楚這個問題。所以我們將數(shù)組的N初始化為N+1
package percolation; /**
 * @author rxy8023
 * @version 1.0    2017/6/17 22:00
 */

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

public class Percolation {

    // number of grid should be n +1，because row and column indices are between 1 and n
    private int n;
    // union-find data structure
    private WeightedQuickUnionUF uf;
    // mark open site
    // 0 for Blocked site, 1 for Open site, 2 for Open site connected to the bottom
    private byte[][] open;
    // number of open sites
    private int num;

    /**
     * create n-by-n grid, with all sites blocked.
     *
     * @param n number of dimension
     */
    public Percolation(int n) {
        if (n <= 0) throw new IllegalArgumentException("Invalid input : n must > 0 !");
        this.n = n + 1;
        uf = new WeightedQuickUnionUF(this.n * this.n);
        open = new byte[this.n][this.n];
    }

    public static void main(String[] args) {
        In in = new In(args[0]);
        int n = in.readInt();
        Percolation percolation = new Percolation(n);
        boolean isPercolated = false;
        int count = 0;
        while (!in.isEmpty()) {
            int row = in.readInt();
            int col = in.readInt();
            if (!percolation.isOpen(row, col)) {
                count++;
            }
            percolation.open(row, col);
            isPercolated = percolation.percolates();
            if (isPercolated) {
                break;
            }
        }
        StdOut.println(count + " open sites");
        if (isPercolated) {
            StdOut.println("percolates");
        } else {
            StdOut.println("does not percolate");
        }

    }

    /**
     * Validate the row and col indices.
     *
     * @param row row index
     * @param col col index
     */
    private void validate(int row, int col) {
        if (row <= 0 || row >= n) {
            throw new IndexOutOfBoundsException("Invalid input : row index out of bounds !");
        }
        if (col <= 0 || row >= n) {
            throw new IndexOutOfBoundsException("Invalid input : col index out of bounds !");
        }
    }

    /**
     * open site (row, col) if it is not open already
     *
     * @param row the index of row
     * @param col the index of column
     */
    public void open(int row, int col) {
        validate(row, col);
        // is open already
        if (isOpen(row, col)) return;
        // make this site open
        open[row][col] = 1;
        num++;
        // we make 0 represent the virtual-top, 1 represent the virtual-bottom.
        // is the bottom row
        if (row == n -1) open[row][col] = 2;
        // is the top row
        if (row == 1) {
            uf.union(0, row * n + col);
            // 1-by-1 grid corner case
            if (open[row][col] == 2) open[0][0] = 2;
        }
        // above site is open
        if (row - 1 > 0 && isOpen(row - 1, col)) {
            update(row - 1, col, row, col);
        }
        // below site is open
        if (row + 1 < n && isOpen(row + 1, col)) {
            update(row + 1, col, row, col);
        }
        // left site is open
        if (col - 1 > 0 && isOpen(row, col - 1)) {
            update(row, col - 1, row, col);
        }
        // right site is open
        if (col + 1 < n && isOpen(row, col + 1)) {
            update(row, col + 1, row, col);
        }
    }

    /**
     * update components: connect the opened site to all of its adjacent open sites
     *
     * @param i1 adjacent open site row index
     * @param j1 adjacent open site col index
     * @param i2 the opened site row index
     * @param j2 the opened site col index
     */
    private void update(int i1, int j1, int i2, int j2) {
        int p = uf.find(i1 * n + j1);
        int q = uf.find(i2 * n + j2);
        uf.union(i1 * n + j1, i2 * n + j2);
        // if one of them is connected to bottom, then the updated component is connected to bottom too.
        if (open[p / n][p % n] == 2 || open[q / n][q % n] == 2) {
            int t = uf.find(i2 * n + j2);
            open[t / n][t % n] = 2;
        }
    }

    /**
     * is site (row, col) open?
     *
     * @param row row index
     * @param col col index
     * @return
     */
    public boolean isOpen(int row, int col) {
        validate(row, col);
        return open[row][col] > 0;
    }

    /**
     * is site (row, col) full?
     *
     * @param row row index
     * @param col col index
     * @return
     */
    public boolean isFull(int row, int col) {
        validate(row, col);
        return open[row][col] > 0 && uf.connected(0, row * n + col);
    }

    /**
     * number of open sites
     *
     * @return
     */
    public int numberOfOpenSites() {
        return num;
    }

    /**
     * does the system percolate?
     *
     * @return
     */
    public boolean percolates() {
        int root = uf.find(0);
        return open[root / n][root % n] == 2;
    }


}

蒙特卡洛仿真分析（PercolationStats類）

用蒙特卡洛（Monte Carlo）方法進行仿真分析，確定滲透閾值p，具體方法是：
初始化將所有N*N個格子置于關(guān)閉狀態(tài)；
每次隨機選擇一個格子進行開啟操作，直到系統(tǒng)達到滲透狀態(tài)；
統(tǒng)計此時開啟的格子數(shù)，與全部格子數(shù)相比計算一個p值的樣本；
獨立重復(fù)T次上述實驗，最后計算出T個p值的樣本，記為x1，x2……xT。

進行以下統(tǒng)計操作。
按照下式計算均值與方差：



假設(shè)T值足夠大（至少30次），則可以根據(jù)下式計算置信區(qū)間在95%的的滲透閾值范圍：


package percolation;

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

/**
 * @author rxy8023
 * @version 1.0    2017/6/17 22:00
 */
public class PercolationStats {
    // sample mean of percolation threshold
    private double mean;
    // sample standard deviation of percolation threshold
    private double stddev;
    // low  endpoint of 95% confidence interval
    private double confidenceLo;
    // high endpoint of 95% confidence interval
    private double confidenceHi;
    // est[i] = estimate of percolation threshold in perc[i]
    private double[] est;

    /**
     * perform trials independent experiments on an n-by-n grid
     *
     * @param n
     * @param trials
     */
    public PercolationStats(int n, int trials) {
        if (n <= 0 || trials <= 0) throw new IllegalArgumentException("Invalid input : n or trials musu > 0 !");
        est = new double[trials];
        for (int k = 0; k < trials; k++) {
            Percolation perc = new Percolation(n);
            double count = 0;
            while (!perc.percolates()) {
                int i = StdRandom.uniform(1, n + 1);
                int j = StdRandom.uniform(1, n + 1);
                if (perc.isOpen(i, j)) continue;
                perc.open(i, j);
                count++;
            }
            est[k] = count / (n * n);
        }
        mean = StdStats.mean(est);
        stddev = StdStats.stddev(est);
        confidenceLo = mean - (1.96 * stddev) / Math.sqrt(trials);
        confidenceHi = mean + (1.96 * stddev) / Math.sqrt(trials);
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        int t = Integer.parseInt(args[1]);
        PercolationStats stats = new PercolationStats(n, t);
        StdOut.println("mean                    = " + stats.mean());
        StdOut.println("stddev                  = " + stats.stddev());
        StdOut.println("95% confidence interval = " + stats.confidenceLo()
                + ", " + stats.confidenceHi());
    }

    /**
     * Get sample mean of percolation threshold
     *
     * @return
     */
    public double mean() {
        return mean;
    }

    /**
     * Get sample standard deviation of percolation threshold
     *
     * @return
     */
    public double stddev() {
        return stddev;
    }


    /**
     * Get low  endpoint of 95% confidence interval
     *
     * @return
     */
    public double confidenceLo() {
        return confidenceLo;
    }


    /**
     * Get high endpoint of 95% confidence interval
     *
     * @return
     */
    public double confidenceHi() {
        return confidenceHi;
    }
}

總結(jié)：

如何根據(jù)API編譯JAVA程序：

1.把API所需要做的內(nèi)容全都用文字詳細寫出來，每個步驟該做什么；
2.可以寫出偽代碼，類似于算法課上所要求的，詳盡寫出；
3.選好數(shù)據(jù)結(jié)構(gòu)，簡單變成不需要；
4.Coding

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容