解題策略 貪進法(greedy method)

Presentation on theme: "解題策略 貪進法(greedy method)"— Presentation transcript:

1 解題策略 貪進法(greedy method)
綜合目前的情況，並不特別考慮下一階段的狀況下， 以最小的成本(或最大的效益)為原則，找出目前可行 的解答(最後找到的可能不是最佳解答) 概念簡單、效率高，常被用來解決最佳化(最低成本、 最短路徑…)的問題，

2 解題策略-貪進法 興建哪幾條馬路以連接5個城市&總興建成本最低？ B A C D E 馬路興建成本示意圖 一 1 路段編號 成本 四 6 三
2 C 二 7 五 3 七 4 六 5 D E 八 9 馬路興建成本示意圖

3 解題策略-貪進法 用貪進法找出最低成本的路段組合 選取路段 成本 徒增成本 路段組合 A B C D E B 一 1 否→選取 {一} 三
2 {一、三} 五 3 {一、三、五} 七 4 是→不選 六 5 {一、三、五、六} 四 6 二 7 八 9 一 A 四 三 五 二 C 七 六 D 八 E A B C D E

4 解題策略Top Down 關鍵字:分解、模組化 分治法(各個擊破法) divide & conquer
找出解決方法(共通的)將問題分解成數個子問題 重複操作(共通的解決方法)解決各個子問題 直到問題解決

5 Ex: 用各個擊破法，將一串數值由小到大排序 演算法(文字表示法) 1. 以第一個數值為標準值
20,2,52,48,13 用各個擊破法，將一串數值由小到大排序 演算法(文字表示法) 1. 以第一個數值為標準值 2. 將標準值右邊小於標準值的數依次移至標準值最左邊 3. 對標準值左邊的數值重複步驟1、2 4. 對標準值右邊的數值重複步驟1、2 5.重複步驟3~5直到完成排序 標準值左右兩邊即為2個子問題

6 解題策略-各個擊破法 分 解 擊 破 　　　　20　02　52　48　13　 　　　02　20　 　52　48　13 　13　02　20　 　48　 　　　　13　02　20　52　48 　　　02　13　0　 20　52　48 　 　20　52　48 　　　02　13　20　48　52　48 移到最左邊 1 2 左 48　52　 52　48 右 02　13　 標準值 13　02 4 3

7 有60個外型一樣的硬幣及一個沒有砝碼的天平 ，現在知道只有一個偽幣和其它的重量不同， 問怎樣稱才能最少次數內就找到那個重量不同 的偽硬。（注意此題並未說明那個硬幣的重量 是輕是重，所以需要仔細考慮） 如果知道偽幣比較輕時，你又會怎麼稱？

8 只考慮偽幣是輕的 分成三堆20：20：20(秤兩次，取出較輕的那堆 ) 在分成三堆7：7：6(只秤7：7，若相同偽幣在6 ，若不同取輕的7) 在分成三堆3：3 or 3：3：1(只秤3：3，若相 同取得偽幣，若不同取輕的3) 第五次 1：1：1