貪婪演算法 (Greedy algorithm)

文藝復興
高級會員
發表於 2021年3月15日 12:40*
點閱數 88

貪婪演算法(英語:greedy algorithm),又稱貪心演算法,是一種在每一步選擇中都採取在當前狀態下最好或最佳(即最有利)的選擇,從而希望導致結果是最好或最佳的演算法。

利用逐步遞增的方式解決問題,完成大小為的工作任務。在每個步驟中,貪婪演算法會作出最佳局部決策,而提供有用的資訊,通常會將待解決問題的大小降為 1 來進行處理。在所有 n 個步驟完成之後,演算法會傳回運算的結果。

簡單來說,就是把一個大問題分割成好幾個小問題,在每一步採用當前看起來最好的選擇,進而希望使最終答案最好的方法

一些關於貪婪法的細節

  1. 建立數學模型來描述問題。
  2. 把求解的問題分成若干個子問題。
  3. 對每一子問題求解,得到子問題的局部最佳解。
  4. 把子問題的解局部最佳解合成原來解問題的一個解。

用程式舉個例子,為了對內含 n 個數值的陣列 A 進行排序,貪婪作法的選擇排序(Selection Sort)演算法會找出 A[0, n-1]中的最大值元素,並將它與 A[n-1]位置元素交換內容,以確保 A[n-1]為此最大值的適當擺放位置。

接著重複上述程序找出在 A[0, n-2]內容中的最大值,並同樣的將它與 A[n-2]位置元素互換內容。持續此重複程序直到整個陣列的元素皆以排序為止。

可以藉由演算法在處理輸入內容時,觀察待解決的子問題規模縮小緩慢的現象,來辨認是否為貪婪法。當子問題能夠以 O(log n)解決完成,則貪婪法會顯現 O(n log n)效能。如果子問題需求 O(n)的行為,而在此用選擇排序處理,則整體的效能會是 O(n^2)。

貪婪法可以解決一些最佳化問題,如:最小生成樹、哈夫曼編碼……對於大部分的問題,貪婪法通常都不能找出最佳解(不過也有例外),因為他們一般沒有測試所有可能的解。貪婪法的缺點就是容易過早做決定,因此在大多數的問題中沒辦法達到最佳解。

資料圖片來源:維基百科

標籤:演算法貪婪法
(使用 Facebook 留言外掛程式 留言無法滿足本網站參加活動之資格,僅供非會員討論使用)

© 2021 - 耐美知識網