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

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

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

import edu.princeton.cs.algs4.StdRandom;

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

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

algs4.jar中已經(jīng)有了UF這個(gè)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)行存儲(chǔ)array id[i]
如果兩個(gè)objects相互鏈接，那么他們數(shù)組的值相同
All sites in a component must have the same value in id[].
例如，當(dāng)union(p,q)時(shí)，p所存的值改為q所存的值。id[p] = id[q]

同樣是id[i]數(shù)組形式，不同的地方是id[i]中存儲(chǔ)父節(jié)點(diǎn)
如果兩個(gè)sites的根相同，那么他們?cè)谕粋€(gè)component
根節(jié)點(diǎn)i == id[i]
例如，當(dāng)union(p,q)時(shí)

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

4.1 weighted
增加sz[]數(shù)組來存儲(chǔ)一顆樹里面objects的個(gè)數(shù)
當(dāng)要鏈接(p,q)時(shí)，需要比較sz[i]和sz[j]的大小（假設(shè)i,j分別是他們的root）

4.2 path compression
只需要增添一個(gè)語句

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

兩種運(yùn)用

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比對(duì)，如果對(duì)上了(match)，那么這些items就可能是用戶想要的。我覺得這個(gè)可能也是并查集相關(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)
}

要點(diǎn)

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

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

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

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

Debug

Percolation.java的問題

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

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

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

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

去掉bottom root,但是這樣會(huì)遍歷n次

isFull方法加上if判斷

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

Percolationstat.java 的問題

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

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

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

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

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

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