算法的主題思想:
1.優秀的算法因為能夠解決實際問題而變得更為重要；
2.高效算法的代碼也可以很簡單；
3.理解某個實現的性能特點是一個挑戰；
4.在解決同一個問題的多種算法之間進行選擇時，科學方法是一種重要的工具；
5.迭代式改進能夠讓算法的效率越來越高效；
1. 動態連通性
動態連接：輸入是一對整數對的序列，其中每個整數代表某種類型的對象（或觸點），我們將整數對p q 解釋為意味着p連接到q。我們假設“連接到”是等價關係：
對稱性：如果p連接到q，則q 連接到p。
傳遞性：如果p連接到q且q 連接到r，則p連接到r。
自反性：p與p連接。
等價關係將對象劃分為多個等價類 或連接的組件。等價類稱為連通分量或分量。
我們的目標是編寫一個程序，以從序列中過濾掉多餘的對：當程序從輸入中讀取整數對 p q時，只有在該對點不等價的情況下，才應將對寫入到輸出中，並且將p連接到q。如果等價，則程序應忽略整數對pq 並繼續讀取下對。
動態連通性問題的應用：
1.網絡
2.變量名等價性
3.數學集合
在更高的抽象層次上，可以將輸入的所有整數看做屬於不同的數學集合。
2. 定義問題
設計算法的第一個任務就是精確地定義問題。
算法解決的問題越大，它完成任務所需的時間和空間可能越多。我們不可能預先知道這其間的量化關係，通常只會在發現解決問題很困難，或是代價巨大，或是發現算法所提供的信息比原問題所需要的更加有用時修改問題。例如，連通性問題只要求我們的程序能夠判斷出給定的整數對是否相連，但並沒有要求給出兩者之間的通路上的所有連接。這樣的要求更難，並會得出另一組不同的算法。
為了定義和說明問題，先設計一份API 來封裝基本操作: 初始化，連接兩個觸點，查找某個觸點的分量 ，判斷兩個觸點是否屬於同一分量，分量的數量：
/// <summary>
/// 動態連通API
/// </summary>
public interface IUnionFind
{
/// <summary>
/// 連接
/// </summary>
/// <param name="p"></param>
/// <param name="q"></param>
void Union(int p, int q);
/// <summary>
/// 查找觸點 p 的分量標識符
/// </summary>
/// <param name="p"></param>
/// <returns></returns>
int Find(int p);
/// <summary>
/// 判斷兩個觸點是否處於同一分量
/// </summary>
/// <param name="p"></param>
/// <param name="q"></param>
/// <returns></returns>
bool Connected(int p, int q);
/// <summary>
/// 連通分量的數量
/// </summary>
/// <returns></returns>
int Count();
}
為解決動態連通性問題設計算法的任務轉化為實現這份API：
1. 定義一種數據結構表示已知的連接；
2. 基於此數據結構高效的實現API的方法；
數據結構的性質會直接影響算法的效率。這裏，以觸點為索引，觸點和連接分量都是用 int 值表示，將會使用分量中某個觸點的值作為分量的標識符。所以，一開始，每個觸點都是只含有自己的分量，分量標識符為觸點的值。由此，可以初步實現一部分方法：
public class FirstUnionFind:IUnionFind
{
private int[] id;//* 分量id 以觸點作為索引
private int count;//分量數量
public FirstUnionFind(int n)
{
count = n;
id = new int[n];
for (var i = 0; i < n; i++)
{
id[i] = i; // 第一個 i 作為觸點，第二個 i 作為觸點的值
}
}
public int Count()
{
return count;
}
public bool Connected(int p, int q)
{
return Find(p) == Find(q);
}
public int Find(int p)
{
}
public void Union(int p, int q)
{
}
}
Union-find 的成本模型 是數組的訪問次數(無論讀寫)。
3. quick-find算法實現
quick-find 算法是保證當且僅當 id[p] 等於 id[q] 時，p 和 q 是連通的。也就是說，在同一個連通分量中的所有觸點在 id[ ] 中的值全部相等。
所以 Find 方法只需返回 id[q]，Union 方法需要先判斷 Find(p) 是否等於 Find(q) ,若相等直接返回；若不相等，需要將 q 所在的連通分量中所有觸點的 id [ ] 值全部更新為 id[p]。
public class QuickFindUF: IUnionFind
{
private int[] id;//* 分量id 以觸點作為索引
private int count;//分量數量
public QuickFindUF(int n)
{
count = n;
id = new int[n];
for (var i = 0; i < n; i++)
{
id[i] = i; // 第一個 i 作為觸點，第二個 i 作為觸點的值
}
}
public int Count()
{
return count;
}
public bool Connected(int p, int q)
{
return Find(p) == Find(q);
}
public int Find(int p)
{
return id[p];
}
public void Union(int p, int q)
{
var pID = Find(p);
var qID = Find(q);
if (pID == qID)
return;
for (var i = 0; i < id.Length; i++)
{
if (id[i] == qID)
id[i] = pID;
}
count--; //連通分量減少
}
public void Show()
{
for(var i = 0;i<id.Length;i++)
Console.WriteLine("索引："+i+",值："+ id[i] );
Console.WriteLine("連通分量數量："+count);
}
}
算法分析
Find() 方法只需訪問一次數組，所以速度很快。但是對於處理大型問題，每對輸入 Union() 方法都需要掃描整個數組。
每一次歸併兩個分量的 Union() 方法訪問數組的次數在 N+3 到 2N+1 之間。由代碼可知，兩次 Find 操作訪問兩次數組，掃描數組會訪問N次，改變其中一個分量中所有觸點的值需要訪問 1 到 N – 1 次（最好情況是該分量中只有一個觸點，最壞情況是該分量中有 N – 1個觸點），2+N+N-1。
如果使用quick-find 算法來解決動態連通性問題並且最後只得到一個連通分量，至少需要調用 N-1 次Union() 方法，那麼至少需要 (N+3)(N-1) ~ N^2 次訪問數組，是平方級別的。
4. quick-union算法實現
quick-union 算法重點提高 union 方法的速度，它也是基於相同的數據結構 — 已觸點為索引的 id[ ] 數組，但是 id[ ] 的值是同一分量中另一觸點的索引(名稱)，也可能是自己（根觸點）——這種聯繫成為鏈接。
在實現 Find() 方法時，從給定觸點，鏈接到另一個觸點，知道到達根觸點，即鏈接指向自己。同時修改 Union() 方法，分別找到 p q 的根觸點，將其中一個根觸點鏈接到根觸點。
public class QuickUnionUF : IUnionFind
{
private int[] id;
private int count;
public QuickUnionUF(int n)
{
count = n;
id = new int[n];
for (var i = 0; i < n; i++)
{
id[i] = i; // 第一個 i 作為觸點，第二個 i 作為觸點的值
}
}
public int Count()
{
return count;
}
public bool Connected(int p, int q)
{
return Find(p) == Find(q);
}
public int Find(int p)
{
while (p != id[p])
p = id[p];
return p;
}
public void Union(int p, int q)
{
var pRoot = Find(p);
var qRoot = Find(q);
if (pRoot == qRoot)
return;
id[pRoot] =qRoot;
count--; //連通分量減少 } public void Show() { for (var i = 0; i < id.Length; i++) Console.WriteLine("索引：" + i + ",值：" + id[i]); Console.WriteLine("連通分量數量：" + count); } }
森林表示
id[ ] 數組用父鏈接的形式表示一片森林，用節點表示觸點。無論從任何觸點所對應的節點隨着鏈接查找，最後都將到達含有該節點的根節點。初始化數組之後，每個節點的鏈接都指向自己。
算法分析
定義：一棵樹的大小是它的節點的數量。樹中一個節點的深度是它到根節點的路徑上鏈接數。樹的高度是它的所有節點中的最大深度。
quick-union 算法比 quick-find 算法更快，因為它對每對輸入不需要遍歷整個數組。
分析quick-union 算法的成本比 quick-find 算法的成本要困難，因為quick-union 算法依賴於輸入的特點。在最好的情況下，find() 方法只需訪問一次數組就可以得到一個觸點的分量表示；在最壞情況下，需要 2i+1 次數組訪問(i 時觸點的深度)。由此得出，該算法解決動態連通性問題，在最佳情況下的運行時間是線性級別，最壞情況下的輸入是平方級別。解決了 quick-find 算法中 union() 方法總是線性級別，解決動態連通性問題總是平方級別。
quick-union 算法中 find() 方法訪問數組的次數為 1(到達根節點只需訪問一次) 加上 給定觸點所對應節點的深度的兩倍（while 循環，一次讀，一次寫）。union() 訪問兩次 find() ，如果兩個觸點不在同一分量還需加一次寫數組。
假設輸入的整數對是有序的 0-1， 0-2，0-3 等，N-1 對之後N個觸點將全部處於相同的集合之中，且得到的樹的高度為 N-1。由上可知，對於整數對 0-i , find() 訪問數組的次數為 2i + 1,因此，處理 N 對整數對所需的所有訪問數組的總次數為 3+5+7+ ……+(2N+1) ~ n^2
5.加權 quick-union 算法實現
簡單改動就可以避免 quick-union算法 出現最壞情況。quick-union算法 union 方法是隨意將一棵樹連接到另一棵樹，改為總是將小樹連接到大樹，這需要記錄每一棵樹的大小，稱為加權quick-union算法。
代碼：
public class WeightedQuickUnionUF: IUnionFind
{
int[] sz;//以觸點為索引的 各個根節點對應的分量樹大小
private int[] id;
private int count;
public WeightedQuickUnionUF(int n)
{
count = n;
id = new int[n];
sz = new int[n];
for (var i = 0; i < n; i++)
{
id[i] = i; // 第一個 i 作為觸點，第二個 i 作為觸點的值
sz[i] = 1;
}
}
public int Count()
{
return count;
}
public bool Connected(int p, int q)
{
return Find(p) == Find(q);
}
public int Find(int p)
{
while (p != id[p])
p = id[p];
return p;
}
public void Union(int p, int q)
{
var pRoot = Find(p);
var qRoot = Find(q);
if (pRoot == qRoot)
return;
if (sz[pRoot] < sz[qRoot])
{
id[pRoot] = qRoot;
}
else
{
id[qRoot] = pRoot;
}
count--; //連通分量減少
}
public void Show()
{
for (var i = 0; i < id.Length; i++)
Console.WriteLine("索引：" + i + ",值：" + id[i]);
Console.WriteLine("連通分量數量：" + count);
}
}
算法分析
加權 quicj-union 算法最壞的情況：
這種情況，將要被歸併的樹的大小總是相等的（且總是 2 的 冥），都含有 2^n 個節點，高度都正好是 n 。當歸併兩個含有 2^n 個節點的樹時，得到的樹含有 2 ^ n+1 個節點，高度增加到 n+1 。
節點大小： 1 2 4 8 2^k = N
高 度： 0 1 2 3 k
k = logN
所以加權 quick-union 算法可以保證對數級別的性能。
對於 N 個觸點，加權 quick-union 算法構造的森林中的任意節點的深度最多為logN。
對於加權 quick-union 算法 和 N 個觸點，在最壞情況下 find，connected 和 union 方法的成本的增長量級為 logN。
對於動態連通性問題，加權 quick-union 算法 是三種算法中唯一可以用於解決大型問題的算法。加權 quick-union 算法 處理 N 個觸點和 M 條連接時最多訪問數組 c M logN 次，其中 c 為常數。
三個算法處理一百萬個觸點運行時間對比：
三個算法性能特點：
6.最優算法 – 路徑壓縮
在檢查節點的同時將它們直接連接到根節點。
實現：為 find 方法添加一個循環，將在路徑上的所有節點都直接鏈接到根節點。完全扁平化的樹。
研究各種基礎問題的基本步驟：
1. 完整而詳細地定義問題，找出解決問題所必須的基本抽象操作並定義一份API。
2. 簡潔地實現一種初級算法，給出一個精心組織的開發用例並使用實際數據作為輸入。
3. 當實現所能解決的問題的最大規模達不到期望時決定改進還是放棄。
4. 逐步改進實現，通過經驗性分析和數學分析驗證改進后的效果。
5. 用更高層次的抽象表示數據結構或算法來設計更高級的改進版本。
6. 如果可能盡量為最壞情況下的性能提供保證，但在處理普通數據時也要有良好的性能。
7.在適當的時候將更細緻的深入研究留給有經驗的研究者並解決下一個問題。
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能
※台北網頁設計公司這麼多該如何選擇?
※智慧手機時代的來臨，RWD網頁設計為架站首選
※評比南投搬家公司費用收費行情懶人包大公開
※幫你省時又省力,新北清潔一流服務好口碑
※回頭車貨運收費標準
