MinimumSpanningTrees最小成本扩张树-联合大学.PPT

Algorithms (Dr. Shi-Jay Chen, National United University) Course 7貪婪法則Greedy Approach ▓ Outlines 本章重點 Concepts of Greedy Approach Dynamic Programming v.s. Greedy Approach Minimum Spanning Trees The Greedy Approach versus Dynamic Programming: The Knapsack Problem ▓ Concepts of Greedy Approach Greedy approach grabs data items in sequence, each time taking the one that is deemed best according to some criterion, without regard for the choices it has made before or will in the future. Like dynamic programming, greedy algorithms are often used to solve optimization problems. However, the greedy approach is more straightforward. In dynamic programming, a recursive property is used to divide an instance into smaller instances. In the greedy approach, there is no division into smaller instances. A greedy algorithm arrives at a solution by making a sequence of choices, each of which simply looks the best at the moment. ▓ Dynamic Programming v.s. Greedy Approach 對於具有限制的最佳化問題，可以採用 “貪婪法則” 或 “動態規劃” 來設計演算法則。 Greedy Approach: 是一種階段性 (Stage) 的方法 具有一選擇程序 (Selection Procedure)，自某起始點(值) 開始，在每一個階段逐一檢查每一個輸入是否適合加入答案中，重複經過多個階段後，即可順利獲得最佳解 一個選擇程序正確與否，會影響貪婪法則所設計出之演算法在執行過後的答案是否為最佳答案。 較為簡單 (?若遇最佳化問題，先思考可否用Greedy Approach解，若不行再考慮用Dynamic Programming) 如果所要處理的最佳化問題無法找到一個選擇程序，則需要考慮所有的可能情況，就是屬於Dynamic Programming Dynamic Programming 先把所有的情況都看過一遍，才去挑出最佳的結果 考慮問題所有可能的情況，將最佳化問題的目標函數表示成一個遞迴關係式，結合Table的使用以找出最佳解 所謂具有限制條件的最佳化問題，是指可以將這一個問題表示成為具有一個目標函數 (Objective Function)與一些限制函數 (Constraint Function)的式子。 對於具有限制條件的最佳化問題的答案而言: 如果符合限制條件的所有答案，一般通稱為可行解 (Feasible Solution) 但是在這一群可行解中，如果能夠讓目標函數最佳化，則這一個可行解就稱為最佳解 (Optimal Solution) [找零錢問題]: 售貨員在找零錢問題中，不但要找對錢，而且還要找給顧客最少的銅板。 利用Greedy Approach如下： 選擇程序 (selection procedure): 售貨員開始找尋收銀機中最大幣值的硬幣，且此時在他腦中用來選擇的準則是究竟哪一枚硬幣的幣值是目前最佳的選擇 (局部最佳解) 可行性檢查 (feasibility check): 售貨員必須判斷他剛剛選擇出那一枚硬幣的幣值加上 “目前顧客方已經收到的幣值總數” 是否超過 “應找給顧客的最後總數”。 解答檢查 (solution check):售貨員必須檢查目前 “已找給顧客方的零錢總數” 是否等於 “應找給顧客的最後總數”。 如果兩者不相等，則售貨員必須繼續利用他的選擇硬幣機制拿出硬幣，並重複上述的過程直到 “已找給顧客方的零錢總數” 等於 “應找給顧客的最後總數”; 或是收銀機裡