Table of Contents
前言
最後一個主題拉~~~歡慶昨天中秋節~~~
最後一個主題我們要講的是貪婪的演算法(Greedy Algorithm),前言廢話不多說,所以就開始吧~~
Greedy Algorithm是什麼
Greedy Algorithm的做法跟Dynamic Programming有點類似,都是一步一步將解答建構出來,Dynamic Programming在進行的時候,會將所以小解答記錄下來,然後再利用這些小解答來推導出答案;然而,Greedy Algorithm與之不同的地方是:Greedy Algorithm再一步步將解答建構出來的過程中,總是選擇當前最佳解
來記錄下來。如此一來,當整個流程進行完成後,留下來的結果就是想要的成果了。
問題:在一個網絡系統中,依序找出由近至遠的節點
在處理這種問題時,基本上會先將所有擁有的資料變成Graph的形式,紀錄著節點與節點之間的關聯與這個關聯的代價(Weight),然後再從預計的起始節點開始一路往後推導,而今天要介紹的這個方法叫做Prim's Algorithm
,基本上步驟如下:
- 選擇任一節點並加入清單。
- 從這個節點開始,將其所有『鄰居』及『代價』記錄下來。
- 從記錄中選出代價最低的節點加入清單。
- 反覆進行2~3步,直到所有節點都加入了清單。
從上範例GIF中可以看到,假設我們預計起始點為A,先在結果清單中將節點A加入後,再從節點A去計算其所有鄰居的距離,然後發現節點E的數值是最小的,因此將節點E放入結果清單,再從節點E來計算距離,而節點E唯一尚未加入結果清單的鄰居就只有節點B了,而且此時從節點E到節點B的距離是5
,比原本的7
還小,因此這時候節點B的數值被從7
換成了5
,然後再從Distance的紀錄中選出最小數值的節點加入結果清單,依此類推,直到所有節點都加入到結果清單。
小結
Prim’s Algorithm執行的過程中,若有數值較小的狀況,其數值會被替換,並在爾後變成判斷的依據。
預告
明天我們將會介紹另外一種解決同一個問題的演算法 - Kruskal’s Algorithm。