貪婪演算法

Report
演算法設計報告
貪婪演算法
資工四乙
96360750
程建銘
1
Greedy algorithm
又稱(貪婪演算法),是一種在每一步選擇中都
採取在當前狀態下最好或最優(即最有利)的
選擇,從而希望導致結果是最好或最優的演算
法。比如在旅行推銷員問題中,如果旅行員每
次都選擇最近的城市,那這就是一種貪婪演算
法。
貪婪法可以解決一些最優化問題,如:求圖中
的最小生成樹、求哈夫曼編碼..對於其他問題,
貪婪法一般不能得到我們所要求的答案。一旦
一個問題可以通過貪婪法來解決,那麼貪婪法
一般是解決這個問題的最好辦法。由於貪婪法
的高效性以及其所求得的答案比較接近最優結
果,貪婪法也可以用作輔助演算法或者直接解
決一些要求結果不特別精確的問題
2
Minimum Spanning Tree( MST )

無向圖(undirected graph)是指該圖的邊線不具方
向性,在圖中以沒有箭頭的實線來表示;其中邊
線是指介於兩個頂點之間的線。

路徑(path)唯一連串頂點所組成的序列。

連通(connected)指在無向圖中兩兩頂點間都存在
一條路徑。

簡單循環(simple cycle)就是指一條至少包含三個
頂點,並且是由其中某一頂點出發、經過不同的
中點、回到該頂點的路徑。
3



非環狀(acycliic)是指無向圖中找不到任何
的simple cycle
樹(tree)唯一無向連通非環狀圖
(acyclic,connected, undirected)
有根樹(rooted tree)為以某個頂點為根的
樹,因此有根樹通常也被直接稱為樹
4
Prim演算法
5
Prim演算法
是圖論中的一種演算法,可在加權連通
圖裡搜索最小生成樹。意即由此演算法
搜索到的邊子集所構成的樹中,不但包
括了連通圖裡的所有頂點,且所有邊的
權值之和亦為最小。
6
Prim演算法用於解決最小生成樹
問題
輸入:一個加權連通圖,其中頂點集合為V,邊集合為E;
初始化:Vnew = {x},其中x為集合V中的任一節點(起始
點),Enew = {};
重複下列操作,直到Vnew = V:
在集合E中選取權值最小的邊(u, v),其中u為集
合Vnew中的元素,而v則不是(如果存在有多條滿足
前述條件即具有相同權值的邊,則可任意選取其中
之一);
將v加入集合Vnew中,將(u, v)加入集合Enew中;
輸出:使用集合Vnew和Enew來描述所得到的最小生成樹。
7
7
時間複雜度
通過鄰接矩陣圖表示的簡易實現中,找
到所有最小權邊共需O(V2)的運行時
間。使用簡單的二叉堆與鄰接表來表示
的話,prim演算法的運行時間則可縮減
為O(E log V),其中E為連通圖的邊數,
V為頂點數。
8
此為原始的加權連通圖。每條邊一
側的數字代表其權值
頂點D被任意選為起始點。頂點A、
B、E和F通過單條邊與D相連。A是
距離D最近的頂點,因此將A及對應
邊AD以高亮表示。 C, G(不可選) A,
B, E, F(可選) D(已選)
下一個頂點為距離D或A最近的頂點。
B距D為9,距A為7,E為15,F為6。
因此,F距D或A最近,因此將頂點
F與相應邊DF以高亮表示。 C, G
(不可選) B, E, F (可選) A, D (已選)
9
演算法繼續重複上面的步驟。距離
A為7的頂點B被高亮表示。 C(不可
選) B, E, G(可選) A, D, F(已選)
在當前情況下,可以在C、E與G間
進行選擇。C距B為8,E距B為7,G
距F為11。E最近,因此將頂點E與
相應邊BE高亮表示。無(不可選) C,
E, G (可選) A, D, F, B (已選)
可供選擇的頂點只有C和G。C距E
為5,G據E為9,故選取C,並與邊
EC一同高亮表示。 無(不可選) C, G
(可選)A, D, F, B, E (已選)
10
頂點G是唯一剩下的頂點,它距F為
11,距E為9,E最近,故高亮表示G
及相應邊EG。 無(不可選) G (不可
選) A, D, F, B, E, C (已選)
現在,所有頂點均已被選取,圖中
綠色部分即為連通圖的最小生成樹。
在此例中,最小生成樹的權值之和
為39。
無 (不可選)無(不可選) A, D, F, B, E, C,
G (已選)
11
Kruskal 演算法

Kruskal演算法是每次選取最小權重值的邊,不用從
某頂點出發,然後檢查是否形成迴路,會形成迴路
的邊不能取用,因為是由小到大取邊以形成生成樹,
所以可建構最小成本生成樹(MST)。一個有n個頂
點的相連圖形,其Kruskal的演算步驟如下:
◦ 1.邊的權重值先由小到大排序。
◦ 2.從所有未走訪的邊中取出最小權重值的邊,記
錄此邊已走訪,檢查是否形成迴路。
(1)形成迴路,此邊不能加入MST中,回到步驟2。
(2)未形成迴路,此邊加入MST中,如果邊數已達
(n-1)條則到步驟3,否則回到步驟2。
◦ 3.Kruskal可以找出MST,結束。
Kruskal 演算法
輸入:圖形G=(V,E),|V|=n, W( ei )為 ei 上的加權值
*/
輸出:T、T是圖形G的最小成本生成樹
Kruskal()
{
while((T的邊數<=n-1)&&(E邊的個數不為0))
{
從E中選出最小權重值的邊ei
從E中刪除ei
if (ei加入T中不會形成迴路)
加入ei到T中
}
if(T的邊數<(n-1))
輸出 “G無最小成本擴張樹”;
else
輸出 T;
}
13
13
Kruskal 時間複雜度
假設有一個n個頂點e條邊的相連圖形作
Kruskal演算法,必須先對邊進行排序,所
需時間O(e log e),所建立的E如果是陣列,
則演算法虛擬碼的第4行的時間是O(e),如
果用堆積來存放邊,則第4、5行每次取出最
小邊和刪除的最平均時間是O(log e),最差
情況要對所有的邊皆處理,則其時間為O(e
log e),所以Kruskal演算法的時間複雜度
為O(e log e) 或者是O(n2 log n),因為
e=O(n2)。
14
(1)建立邊由小到大的排序
5
1
2
2
13
20
3
15
8
0
10
5
4
1
3
4
(4)取出(0,2)建立邊
(3,4)
1
(0,1)
2
(0,2)
3
(4,5)
4
(1,2)
5
(2,4)
8
(0,4)
10
(1,3)
13
(2,5)
15
(0,3)
20
0
1
0
3
4
(6)取出(1,2)形成迴路
不建立邊
2
1
0
3
4
(3)取出(0,1)建立邊
2
1
1
3
(5)取出(4,5)建立邊
2
1
0
5
5
4
3
(7)取出(2,4),建立邊,已
達6條邊,結束。
2
1
0
3
(2)取出(3,4)建立邊
5
4
4
3
邊
權重值
MST邊
(3,4)
(0,1)
(0,2)
1
2
3
要
要
要
(4,5)
(1,2)
(2,4)
(0,4)
(1,3)
(2,5)
(0,3)
4
5
8
10
13
15
20
要
不要
要
4
權重值總和
=1+2+3+4+8=18
不檢查
不檢查
不檢查
不檢查
15
Prim演算法 VS
Kruskal演算法
Kruskal演算法有一個特色。如果原圖並非連通,找出來的
邊仍然具有「權重最小」且能「連結圖上各點」
的性質。但 Prim's Algorithm 則無法處理不連通的圖。
16
Gabow's Algorithm
用途:
在無向圖上,求出一棵最大(小)生成樹,再
求出權重最接近最小(大)生成樹的另一棵生
成樹。
當圖上每條邊的權重都不一樣時,才保證能求
出權重次小(大)的生成樹。一般情況下,有
可能求出另一棵最小(大)生成樹。
17
演算法
最小生成樹改了一條邊,就能變成次小生成樹,因此
可以試著窮舉此條邊。
1.先求出一棵最小生成樹。
2. 求出樹上任兩點ij之間,權重最大的邊,記為E(i,j)。
3. 窮舉每一條不在最小生成樹上的邊pq: 甲、把邊
pq添加到最小生成樹上,勢必形成環。 乙、
然後移除邊E(p,q),勢必又形成樹,此樹權重已
然盡量少。 丙、記下此樹。
4. 剛剛得到的E-(V-1)棵樹之中,權重最小者便是次小生
成樹。
18
時間複雜度
為下述三項總和
一、建立一棵最小生成樹,看是用哪種演算法;
二、建立 E(i,j) 的時間,等同於求樹上所有兩
點之間的距離,為 O(V^2) ;
三、窮舉邊 pq 與增減一條邊的時間,共 O(E) 。
19
霍夫曼編碼
霍夫曼編碼(Huffman Coding)是一種編碼方式,是一種用於無
損數據壓縮的權編碼)演算法
在電腦資料處理中,霍夫曼編碼使用變長編碼表對源符號(如文
件中的一個字母)進行編碼,其中變長編碼表是通過一種評估來
源符號出現機率的方法得到的,出現機率高的字母使用較短的編
碼,反之出現機率低的則使用較長的編碼,這便使編碼之後的字
元串的平均長度、期望值降低,從而達到無損壓縮數據的目的。
霍夫曼樹又稱最優二叉樹,是一種帶權路徑長度最短的二叉樹。
所謂樹的帶權路徑長度,就是樹中所有的葉結點的權值乘上其到
根結點的路徑長度(若根結點爲0 層,葉結點到根結點的路徑長
度爲葉結點的層數)。樹的路徑長度是從樹根到每一結點的路徑
長度之和,記爲WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln),N個
權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹,相應的葉結點
的路徑 長度爲Li(i=1,2,...n)。可以證明霍夫曼樹的WPL是最小的。
20
演算法




一、對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構
成n棵二叉樹的初始集合{T1,T2,T3,...,Ti,...,Tn},其
中每棵二叉樹Ti中只有一個權值為Wi的根結點,
它的左右子樹均為空。(為方便在計算機上實現
算 法,一般還要求以Ti的權值Wi的升序排列。)
二、在F中選取兩棵根結點權值最小的樹作為新構
造的二叉樹的左右子樹,新二叉樹的根結點的權
值為其左右子樹的根結點的權值之和。
三、從F中刪除這兩棵樹,並把這棵新的二叉樹同
樣以升序排列加入到集合F中。
四、重複二和三兩步,直到集合F中只有一棵二叉
樹為止。
21
用C語言實現上述算法,可用靜態的二叉樹或動態的二叉樹。若用動態的二叉
樹可用以下數據結構: struct tree{
float weight; /*權值*/
union{
char leaf; /*葉結點信息字符*/
struct tree *left; /*樹的左結點*/
};
struct tree *right; /*樹的右結點*/
};
struct forest{ /*F集合,以鏈表形式表示*/
struct tree *ti; /* F中的樹*/
struct forest *next; /* 下一個結點*/
};
22
如圖:
這個句子「this is an example of a huffman
tree」中得到的字母頻率來建構霍夫曼樹。
句中字母的編碼和頻率如下。編碼此句子句
子需要135 bit(不包括保存樹所用的空間)
23
END
24

similar documents