Dijkstra Algorithm for Single-pair Shortest Path Problem 最短路径.PPT

Algorithms (Dr. Shi-Jay Chen, National United University) Course 7貪婪法則Greedy Approach ▓ Outlines 本章重點 Dynamic Programming v.s. Greedy Approach Concepts of Greedy Approach Minimum Spanning Trees The Greedy Approach versus Dynamic Programming: The Knapsack Problem Dijkstra Algorithm for Single-pair Shortest Path Problem ▓ Dynamic Programming v.s. Greedy Approach 對於具有限制的最佳化問題，可以採用 “貪婪法則” 或 “動態規劃” 來設計演算法則。 所謂具有限制條件的最佳化問題，是指可以將這一個問題表示成為具有一個目標函數 (Objective Function)與一些限制函數 (Constraint Function；或稱限制條件)的式子。 對於求解具有限制條件的最佳化問題時所得到的不同答案類型而言: 符合限制函數 (條件) 的所有答案，一般通稱為可行解 (Feasible Solution) 但是在這一群可行解中，如果能夠讓目標函數最佳化，則這一個可行解就稱為最佳解 (Optimal Solution) Greedy Approach 是一種階段性 (Stage) 的方法 具有一選擇程序 (Selection Procedure)，自某起始點(值) 開始，在每一個階段逐一檢查每一個輸入是否適合加入答案中，重複經過多個階段後，即可順利獲得最佳解 一個選擇程序正確與否，會影響貪婪法則所設計出之演算法在執行過後的答案是否為最佳答案。 較為簡單 如果所要處理的最佳化問題無法找到一個選擇程序，則需要考慮所有的可能情況，就是屬於Dynamic Programming Dynamic Programming 先把所有的情況都看過一遍，才去挑出最佳的結果 考慮問題所有可能的情況，將最佳化問題的目標函數表示成一個遞迴關係式，結合Table的使用以找出最佳解 ▓ Concepts of Greedy Approach Greedy approach 從一組資料序列中抓取資料時，每一階段要抓一個該階段最佳的資料是根據一些準則 (選擇程序) 來決定，且此次的決定和先前及往後的階段所做之任何一個決定無關。 設計方法： 根據問題的目標函數，找出一個選擇程序 (Selection Procedure)。 根據這一個選擇程序，由所有的輸入中，每次逐一選擇一個最佳的輸入加以檢查，如果這一個輸入可以符合問題的限制條件，則將這一個輸入加入；反之則必須捨棄這一個輸入。 每一階段可以重覆上述選擇、檢查的程序。所有階段執行完畢後，最後可以得到一個最佳解或是不存在任何一組可行解。 貪婪演算法的演算過程由一個空的解集合開始，藉由循序的加入新的解直到符合問題需求的最終解得到為止。 重複下列程序: 選擇程序 (Selection procedure) 挑選出下一個項目加入到解集合中。 選擇程序的執行，是根據滿足每一階段之局部最佳化條件(locally optimal consideration)的貪婪原則來進行。 可行性檢查 (Feasibility check) 決定加入新項目後的新的解集合，是否在可行解的範圍之內。 解答檢查 (Solution check) 決定此新的解集合是否為此問題的最終結果。 [找零錢問題]: 售貨員在找零錢問題中，不但要找對錢 (限制條件)，而且還要找給顧客最少的銅板 (目標函數)。 利用Greedy Approach如下 (例：要找給客人75元)： 選擇程序 (selection procedure): 售貨員開始找尋收銀機中最大幣值的硬幣時，選擇的準則是究竟哪一枚硬幣的幣值是目前最佳的選擇 (局部最佳解) 可行性檢查 (feasibility check): 售貨員必須判斷他剛剛選擇出那一枚硬幣的幣值加上 “目前顧客方已經收到的幣值總數” 是否超過 “應找給顧客的最後總數”。(是否有超過75元) 解答檢查 (solution check): 售貨員必須檢查目前 “已找給顧客方的零錢總數” 是否等於 “應找給顧客的最後總數”。(是否已經等於75元) 如果兩者不相等，則售貨員必須繼續利用他的選擇硬幣機制拿出硬幣，並重複上述三個過程直到 “已找給顧客方的零錢總數” 等於 “應找給顧客的最後總數”; 或是收銀機裡的硬幣全部用盡為止。 ▓ Minimum Spanning Tre