java貪婪演算法

A. 貪婪演算法之——最小耗費生成樹

在例 及 中已考察過這個問題 因為具有n 個頂點的無向網路G的每個生成樹剛好具有n 條邊 所以問題是用某種方法選擇n 條邊使它們形成G的最小生成樹 至少可以採用三種不同的貪婪策略來選擇這n 條邊 這三種求解最小生成樹的貪婪演算法策略是 K r u s k a l演算法 P r i m演算法和S o l l i n演算法

Kruskal演算法

( ) 演算法思想

K r u s k a l演算法每次選擇n 條邊 所使用的貪婪准則是 從剩下的邊中選擇一條不會產生環路的具有最小耗費的邊加入已選擇的邊的集合中 注意到所選取的邊若產生環路則不可能形成一棵生成樹 K r u s k a l演算法分e 步 其中e 是網路中邊的數目 按耗費遞增的順序來考慮這e 條邊 每次考慮一條邊 當考慮某條邊時 若將其加入到已選邊的集合中會出現環路 則將其拋棄 否則 將它選入

考察圖 a 中的網路 初始時沒有任何邊被選擇 圖 b 顯示了各節點的當前狀態 邊( )是最先選入的邊 它被加入到欲構建的生成樹中 得到圖 c 下一步選擇邊( )並將其加入樹中(如圖 d所示) 然後考慮邊( ) 將它加入樹中並不會產生環路 於是便得到圖 e 下一步考慮邊( )並將其加入樹中(如圖 f所示) 在其餘還未考慮的邊中 ( )具有最小耗費 因此先考慮它 將它加入正在創建的樹中會產生環路 所以將其丟棄 此後將邊( )加入樹中 得到的樹如圖 g 所示 下一步考慮邊( ) 由於會產生環路 將其丟棄 最後考慮邊( )並將其加入樹中 產生了一棵生成樹 其耗費為 圖 給出了K r u s k a l演算法的偽代碼

/ /在一個具有n 個頂點的網路中找到一棵最小生成樹

令T為所選邊的集合 初始化T=

令E 為網路中邊的集局野合

w h i l e(E≠ )&&(| T |≠n ) {

令(u v)為E中代價最小的邊 E=E { (u v) } / /從E中刪除邊

i f( (u v)加入T中不會產生環路)將( u v)加入T

}

i f(| T | = =n ) T是最小耗費生成樹

e l s e 網路不是互連的 不能找到生成樹

圖 Kruskao演算法的偽代碼

( ) 正確性證明

利用前述裝載問題所用的轉化技術可以證明圖 的貪婪演算法總能建立一棵最小耗費生成樹 需要證明以下兩點 ) 只要存羨旅在生成樹 K r u s k a l演算法總能產生一棵生成樹; ) 產生的生成樹具有最小耗費 令G為任意加權無向圖(即G是一個無向網路) 從 節可知當且僅當一個無向圖連通時它有生成樹 而且在Kruskal 演算法中被拒絕(丟棄)的邊是那些會產生環路的邊 刪除連通圖環路中的一條邊所形成兄臘凳的圖仍是連通圖 因此如果G在開始時是連通的 則T與E中的邊總能形成一個連通圖 也就是若G開始時是連通的 演算法不會終止於E= 和| T |< n

現在來證明所建立的生成樹T具有最小耗費 由於G具有有限棵生成樹 所以它至少具有一棵最小生成樹 令U為這樣的一棵最小生成樹 T與U都剛好有n 條邊 如果T=U 則T就具有最小耗費 那麼不必再證明下去 因此假設T≠U 令k(k > ) 為在T中而不在U中的邊的個數 當然k 也是在U中而不在T中的邊的數目 通過把U變換為T來證明U與T具有相同的耗費 這種轉化可在k 步內完成 每一步使在T而不在U中的邊的數目剛好減 而且U的耗費不會因為轉化而改變 經過k 步的轉化得到的U將與原來的U具有相同的耗費 且轉化後U中的邊就是T中的邊 由此可知 T具有最小耗費 每步轉化包括從T中移一條邊e 到U中 並從U中移出一條邊f 邊e 與f 的選取按如下方式進行

) 令e 是在T中而不在U中的具有最小耗費的邊 由於k > 這條邊肯定存在

) 當把e 加入U時 則會形成唯一的一條環路 令f 為這條環路上不在T中的任意一條邊

由於T中不含環路 因此所形成的環路中至少有一條邊不在T中

從e 與f 的選擇方法中可以看出 V=U+ {e} { f } 是一棵生成樹 且T中恰有k 條邊不在V中出現 現在來證明V的耗費與U的相同 顯然 V的耗費等於U的耗費加上邊e 的耗費再減去邊f 的耗費 若e 的耗費比f 的小 則生成樹V的耗費比U的耗費小 這是不可能的 如果e 的耗費高於f 在K r u s k a l演算法中f 會在e 之前被考慮 由於f 不在T中 Kruskal 演算法在考慮f 能否加入T時已將f 丟棄 因此f 和T中耗費小於或等於f 的邊共同形成環路 通過選擇e 所有這些邊均在U中 因此U肯定含有環路 但是實際上這不可能 因為U是一棵生成樹 e 的代價高於f 的假設將會導致矛盾 剩下的唯一的可能是e 與f 具有相同的耗費 由此可知V與U的耗費相同

( ) 數據結構的選擇及復雜性分析

為了按耗費非遞減的順序選擇邊 可以建立最小堆並根據需要從堆中一條一條地取出各邊 當圖中有e 條邊時 需花(e) 的時間初始化堆及O ( l o ge) 的時間來選取每一條邊 邊的集合T與G中的頂點一起定義了一個由至多n 個連通子圖構成的圖 用頂點集合來描述每個子圖 這些頂點集合沒有公共頂點 為了確定邊( u v)是否會產生環路 僅需檢查u v 是否在同一個頂點集中(即處於同一子圖) 如果是 則會形成一個環路;如果不是 則不會產生環路 因此對於頂點集使用兩個F i n d操作就足夠了 當一條邊包含在T中時 個子圖將被合並成一個子圖 即對兩個集合執行U n i o n操作 集合的F i n d和U n i o n操作可利用 節的樹(以及加權規則和路徑壓縮)來高效地執行 F i n d操作的次數最多為 e Un i o n操作的次數最多為n (若網路是連通的 則剛好是n 次) 加上樹的初始化時間 演算法中這部分的復雜性只比O (n+e) 稍大一點

對集合T所執行的唯一操作是向T中添加一條新邊 T可用數組t 來實現 添加操作在數組的一端進行 因為最多可在T中加入n 條邊 因此對T的操作總時間為O (n)

總結上述各個部分的執行時間 可得圖 演算法的漸進復雜性為O (n+el o ge)

( ) 實現

利用上述數據結構 圖 可用C + +代碼來實現 首先定義E d g e N o d e類(見程序 ) 它是最小堆的元素及生成樹數組t 的數據類型

程序 Kruskal演算法所需要的數據類型

template

class EdgeNode {

p u b l i c :

operator T() const {return weight;}

p r i v a t e :

T weight;//邊的高度

int u v;//邊的端點

} ;

為了更簡單地使用 節的查找和合並策略 定義了U n i o n F i n d類 它的構造函數是程序 的初始化函數 U n i o n是程序 的加權合並函數 F i n d是程序 的路徑壓縮搜索函數

為了編寫與網路描述無關的代碼 還定義了一個新的類U N e t Wo r k 它包含了應用於無向網路的所有函數 這個類與U n d i r e c t e d類的差別在於U n d i r e c t e d類中的函數不要求加權邊 而U N e t Wo r k要求邊必須帶有權值 U N e t Wo r k中的成員需要利用N e t w o r k類中定義的諸如B e g i n和N e x t Ve r t e x的遍歷函數 不過 新的遍歷函數不僅需要返回下一個鄰接的頂點 而且要返回到達這個頂點的邊的權值 這些遍歷函數以及有向和無向加權網路的其他函數一起構成了W N e t w o r k類(見程序 )

程序 WNeork類

template

class WNeork : virtual public Neork

{

public :

virtual void First(int i int& j T& c)= ;

virtual void Next(int i int& j T& c)= ;

} ;

象B e g i n和N e x t Ve r t e x一樣 可在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h類中加入函數F i r s t與N e x t 現在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h類都需要從W N e t Wo r k中派生而來 由於A d j a c e n c y W G r a p h類和L i n k e d W G r a p h類需要訪問U N e t w o r k的成員 所以這兩個類還必須從U N e t Wo r k中派生而來 U N e t Wo r k : : K r u s k a l的代碼見程序 它要求將Edges() 定義為N e t Work 類的虛成員 並且把U N e t Wo r k定義為E d g e N o d e的友元) 如果沒有生成樹 函數返回f a l s e 否則返回t r u e 注意當返回true 時 在數組t 中返回最小耗費生成樹

程序 Kr u s k a l演算法的C + +代碼

template

bool UNeork ::Kruskal(EdgeNode t[])

{// 使用K r u s k a l演算法尋找最小耗費生成樹

// 如果不連通則返回false

// 如果連通 則在t [ : n ]中返回最小生成樹

int n = Ve r t i c e s ( ) ;

int e = Edges();

/ /設置網路邊的數組

InitializePos(); // 圖遍歷器

EdgeNode *E = new EdgeNode [e+ ];

int k = ; // E的游標

for (int i = ; i <= n; i++) { // 使所有邊附屬於i

int j;

T c;

First(i j c);

while (j) { // j 鄰接自i

if (i < j) {// 添加到達E的邊

E[++k] weight = c;

E[k] u = i;

E[k] v = j;}

Next(i j c);

}

}

// 把邊放入最小堆

MinHeap > H( );

H Initialize(E e e);

UnionFind U(n); // 合並/搜索結構

B. 找零錢問題 [貪心演算法](java實現）

public getMin{

public int MinNumber=0;

public int findMax(int[] a){
for(int i=0;i<a.length;i++){
if(a[i]==0) return a[--i];
}
return a[a.length-1];
}

public boolean Compare(int a,int b){
public boolean flag=true;
if(a>b) flag=flase;
return flag;
}

public int getMinNumber(int[] M,int Money){
int[] findM=new int[M.length];

int index=0;

for(int i=0;i<M.length;i++){
boolean f = this.Compare(M[i],money)
if(f) findM[index++]=M[i];
}

int max = this.findMax(findM);
MinNumber++;

if((Money-max)!=0) {
getMinNumber(M,Money-max)
}

return MinNumber;
}

public int[] Start(){
System.out.println("請輸入查詢組數");
int group=System.in.read();

int[] M={1,2,5,10,20,50,100};

int[] Result = new Int[group];
int index=0;

while (group-- > 0){
System.out.println("請輸入金額");
int money=System.in.read();
Result[index++] = getMinNumber(M,money);
MinNumber=0;
}
}

public void print(int[] MinNumber){
for(int i=0;i<MinNumber.length.i++){
System.out.println(MinNumber[i]+" ");
}
}
}

public static void main(String[] args){
new getMin().print(new getMin().Start());
}

沒測試啊，有問題請勿噴，呵呵

C. 貪心演算法的特性

貪婪演算法可解決的問題通常大部分都有如下的特性：
⑴隨著演算法的進行，將積累起其它兩個集合：一個包含已經被考慮過並被選出的候選對象，另一個包含已經被考慮過但被丟棄的候選對象。
⑵有一個函數來檢查一個候選對象的集合是否提供了問題的解答。該函數不考慮此時的解決方法是否最優。
⑶還有一個函數檢查是否一個候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數一樣，此時不考慮解決方法的最優性。
⑷選擇函數可以指出哪一個剩餘的候選對象最有希望構成問題的解。
⑸最後，目標函數給出解的值。
⑹為了解決問題，需要尋找一個構成解的候選對象集合，它可以優化目標函數，貪婪演算法一步一步的進行。起初，演算法選出的候選對象的集合為空。接下來的每一步中，根據選擇函數，演算法從剩餘候選對象中選出最有希望構成解的對象。如果集合中加上該對象後不可行，那麼該對象就被丟棄並不再考慮；否則就加到集合里。每一次都擴充集合，並檢查該集合是否構成解。如果貪婪演算法正確工作，那麼找到的第一個解通常是最優的。