演算法 Algorithm ─ Greedy Algorithm PART 2

貪婪演算法 Greedy Algorithm


(前篇回顧請按此)

○ 換零錢遊戲

例：現有 71個 1元，幣值分別為 29元、22元、5元、1元，請用最少的零錢個數兌換零錢。

    ※  貪婪演算法：    
                            ○ 局部解 ：    29元     22元     5元     1元
                     
                                     1. 換 29元           2個
                                     2. 換 22元                          0個
                                     3. 換   5元                                       2個
                                     4. 換   1元                                                   3個
                            -------------------------------------------------------------------------------------
                                        總共換了      2+2+3=  7 枚硬幣

    ※  動態演算法：    
                            ○ 最佳解 ：    29元     22元     5元     1元
                     
                                     1. 換 29元           0個
                                     2. 換 22元                          3個
                                     3. 換   5元                                       1個
                                     4. 換   1元                                                   0個
                            -------------------------------------------------------------------------------------
                                        總共換了      3+1=  4 枚硬幣


由此可知：

● 貪婪演算法不一定是最佳解，但效率高
● 動態演算法可以求出最佳解，但效率略差 
● 要依問題的特性判斷採用何種演算法，依此換零錢例子，應該採用動態演算法(Dynamic Programming)


=============================================================================================

最小生成樹

首先要求出最小生成樹要先有無向量圖型的概念

無向量圖型又是什麼呢?  

1.  線上的數字代表權重   (無向量權重圖)
2. 連通：圖上任一點均可連到另外一點  (連通圖)
3. 循環(Cycle)： 三個點可以形成一個循環，而無向量圖上有n個循環  (循環圖)


(無向量權重圖)

(連通圖)















(循環圖)














=============================================================================================

而生成樹的概念

基本上是對無向量圖型稍作修改所形成的

-------------------------------------------------------------

最小生成樹

特性：

1. 沒有方向性 (無循環(cycle))
2. 可以連通(必須將所有的點都連通，且其邊之總和必須是最小的)
3. 不能移除點，只能移動邊


貪婪演算法延伸的兩種方法：

1. Kruskal 演算法
2. Prim演算法


-------------------------------------------------------------------

Kruskal 演算法


作法：

1. 先清空邊線
2. 挑邊，需要挑最小的邊
3. 扣除掉畫過的最小邊之後，在繼續找次小邊，以此類推
4. 當圖型連通所有的點，並沒有循環的特性，就完成了！！

 

Result ：













(解法A)


依情況而定，結果不一定只有一種













(解法B)



**********************************************************************************************************************************
Prim 演算法


作法：

1. 清空畫面，並先選擇其中一點
2. 挑邊，需要挑最小的邊
3. 扣除掉畫過的最小邊之後，在以已經相連接的點為基礎，找已經連接的點的最小邊連接，以此類推
4. 當圖型連通所有的點，並沒有循環的特性，就完成了！！

 (原始圖)


Result ：



=============================================================================================

練習題：   請以下列圖型找出最小生成樹，並用 Kruskal 演算法 & Prim演算法 分別畫出最小生成樹

--------------------------------------------------------------------------------------------------------
Result：

紫色編號為步驟順序

Kruskal 演算法

Prim演算法