摘要：算法鏈接學(xué)習(xí)工具，，環(huán)境搭建在小伙伴的推薦下，這個學(xué)期開始上普林斯頓的算法課。一系列的整數(shù)對代表與相互連接，比如等，每一個整數(shù)代表了一個。我覺得這個可能也是并查集相關(guān)應(yīng)用。這學(xué)期繼續(xù)學(xué)習(xí)深入理解了就能明白了。

《算法》鏈接：1.5 Case Study: Union-Find
學(xué)習(xí)工具：mac，java8，eclipse,coursera

環(huán)境搭建
在小伙伴的推薦下，這個學(xué)期開始上普林斯頓的算法課。
這門課有自己的Java library，剛開始的時候研究載入這個library花了好長時間，最終的解決方案是下載algs4.jar包，然后在eclipse軟件中將其作為外部library，使用的時候import statement要寫成類似這樣的：

import edu.princeton.cs.algs4.StdRandom;

教授一開始就講到了dynamic connectivity，其實這是Union Find算法的一種應(yīng)用，這學(xué)期選修的另外一門network model和這個也有關(guān)。

Input: 一系列的整數(shù)對（p,q）代表p與q相互連接("is connected to")，比如（4,3）(3,8)等，每一個整數(shù)代表了一個object。這里的"is connected to"表示的是沒有方向的對稱連接,且一個p可以與自身p相連。
Goal:當(dāng)讀取的(p,q)整數(shù)對本來不相連時，輸出這個整數(shù)對(p,q)且使其相連；如果相連的話，就不輸出，忽略這個整數(shù)對

algs4.jar中已經(jīng)有了UF這個class，可以直接使用。

public static void main(String[] args) {
        int n = StdIn.readInt();
        UF uf = new UF(n);
        while (!StdIn.isEmpty()) {
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            if (uf.connected(p, q)) continue;
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
        StdOut.println(uf.count() + " components");
    }

數(shù)組形式進(jìn)行存儲array id[i]
如果兩個objects相互鏈接，那么他們數(shù)組的值相同
All sites in a component must have the same value in id[].
例如，當(dāng)union(p,q)時，p所存的值改為q所存的值。id[p] = id[q]

同樣是id[i]數(shù)組形式，不同的地方是id[i]中存儲父節(jié)點
如果兩個sites的根相同，那么他們在同一個component
根節(jié)點i == id[i]
例如，當(dāng)union(p,q)時

    pID = id[p];
    qID = id[q];
    循環(huán)數(shù)組中所有值等于pID的，如果id[i]==pID，則id[i] = qID;
    也就是說p所在的樹將作為q的子樹

4.1 weighted
增加sz[]數(shù)組來存儲一顆樹里面objects的個數(shù)
當(dāng)要鏈接(p,q)時，需要比較sz[i]和sz[j]的大?。僭O(shè)i,j分別是他們的root）

4.2 path compression
只需要增添一個語句

id[i] = id[id[i]]

兩種運用

quick union with path compression

weighted quick-union with path compression

教授列舉了相當(dāng)多的應(yīng)用，物理學(xué)上的，應(yīng)用到其他算法或者語言的。所給的面試題也很常見。
最近剛接觸seo相關(guān)的內(nèi)容，老師談到IR system需要將用戶提供的單詞和收集的items中相關(guān)的words比對，如果對上了(match)，那么這些items就可能是用戶想要的。我覺得這個可能也是并查集相關(guān)應(yīng)用。這學(xué)期繼續(xù)學(xué)習(xí)深入理解了就能明白了。

Write a program to estimate the value of the percolation threshold via Monte Carlo simulation.
Percolation. Given a composite systems comprised of randomly distributed insulating and metallic materials: what fraction of the materials need to be metallic so that the composite system is an electrical conductor? Given a porous landscape with water on the surface (or oil below), under what conditions will the water be able to drain through to the bottom (or the oil to gush through to the surface)? Scientists have defined an abstract process known as percolation to model such situations.
The model. We model a percolation system using an n-by-n grid of sites. Each site is either open or blocked.

open

full

Percolation data type：

public class Percolation {
   public Percolation(int n)                // create n-by-n grid, with all sites blocked
   public    void open(int row, int col)    // open site (row, col) if it is not open already
   public boolean isOpen(int row, int col)  // is site (row, col) open?
   public boolean isFull(int row, int col)  // is site (row, col) full?
   public     int numberOfOpenSites()       // number of open sites
   public boolean percolates()              // does the system percolate?

   public static void main(String[] args)   // test client (optional)
}

PercolationStats data type：

public class PercolationStats {
   public PercolationStats(int n, int trials)    // perform trials 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)
}

要點

導(dǎo)入WeightedQuickUnionUF,在程序中主要使用connect(p,q),union(p,q)函數(shù)

題目默認(rèn)(1,1)就是左上角的位置，(n,n)就是右下角的位置，所以我先創(chuàng)建了一個siten+1的二維數(shù)組, 并全部初始化為0，代表全部block

創(chuàng)建WeightedQuickUnionUF對象，由于UF算法中都是以一維數(shù)組存儲，所以數(shù)組uf[1]-uf[NN]對應(yīng)NN矩陣中的位置，并且根據(jù)老師的提示，創(chuàng)建了top virtual site uf[0]和bottom site uf[NN+1], 所以整個uf一維數(shù)組的長度是NN+2

最關(guān)鍵也是最容易出錯的地方就在open一個點以后，檢查上下左右鄰近的點，并對open的鄰近做union的過程，要考慮到邊緣位置的特殊情況，比如中心點在第一行，那么該點上下左右最多只有三個臨近點，而上點可以與top virtual site連通。

Debug

Percolation.java的問題

幾次發(fā)現(xiàn)結(jié)果不對，問題都出在open函數(shù)里面

對eclipse還不熟，測試中In in = new In(args[0]) 語句要求從命令行鍵入文件名，回車運行。eclipse的操作方法是，在 run configurations-->arguments-->program arguments-->鍵入文件名，可以不打引號,也可以打引號。

如果不想寫路徑，只寫filename.txt，文件要放在項目目錄下(我的項目名是algs)，因為eclipse默認(rèn)的根目錄就是項目目錄

等待解決的bug：一旦連通，再在第N行open的單元格會變成full狀態(tài)，因為bottom virtual root 已經(jīng)聯(lián)通，那么與之相連的方塊都認(rèn)為是與top virtual root 相連的。目前想到的解決方案有

去掉bottom root,但是這樣會遍歷n次

isFull方法加上if判斷

思考優(yōu)化open 方法

Percolationstat.java 的問題

Percolationstat.java 在編寫時，for循環(huán)里面，每一次判斷一個網(wǎng)格是不是連通之前都要新創(chuàng)建一個n-by-n的網(wǎng)格，但是我把創(chuàng)建的語句寫在了for循環(huán)外面，導(dǎo)致同一個網(wǎng)格會被實驗T次

計算時除號/左右兩邊numberOfOpenSites和(nn)都是整數(shù)，所以得到的結(jié)果也是整數(shù)；需要強(qiáng)制轉(zhuǎn)換成double類型，即numberOfOpenSites/(double)(nn)

每次讀取一組整數(shù)對后，open site前先要判斷這個點是否被open了，以免多計算在numberOfOpenSites里面

作業(yè)提交遇到的問題

所有的fields 和自己定義的methods都要寫為private

最后提交的作業(yè)91分，看了一下report, 扣分主要就扣在bottom root與所有最后一行的sites連通的問題上。以后有時間再來修改code吧