Greedy 策略簡介

Greedy 策略 是種解決問題的策略。

類似於動態規劃 ，Greedy 策略 也是透過把原本問題拆解成子問題去解。每次解決子問題都選擇最佳解的解決方案，從而導出整體的最佳解。

Greedy 策略特別適合有最佳子結構且子問題不重複的問題。

所謂最佳子結構的意思是局部最佳解能決定全域最佳解。

簡單地說，問題能夠分解成子問題來解決，子問題的最佳解能遞推到最終問題的最佳解。

Greedy 策略的最大特性就是每個子問題都選取最佳解來往下推導全局最佳解。

另一個不同於動態規劃，Greedy 策略對於每個子問題解決方案都必須做選擇，且選擇了不能往上個結果去尋找，也就是只有一個最佳解。

局部的最佳解可以決定全局的最佳解。

Greedy 策略可以用來解決一些最佳化的問題，比如圖論中的最小生成樹問題，霍夫曼編碼 等等。

而其他問題，使用Greedy 策略不一定找的出解法。

Greedy 策略可以說是 動態規劃的一種特例。

換硬幣問題 - 說明使用 Greedy 策略的時機

換最少硬幣個數問題(在每個幣值之間如果都具有倍數關係的情況下)

舉例來說： 幣值有 1, 5, 10, 50 ，其中 50 是 10, 5, 1的倍數，且 10 是 5, 1 的倍數， 5 是倍數。

在這時適合用 Greedy 策略，

因為這個問題具有以下特性：

1. 具有最佳子問題結構
2. 局部最佳解可以組成全局最佳解
3. 子問題彼此不重疊

也就是：幣值最大使用愈多換得的硬幣愈少

使用 Greedy 策略 就是幣值愈大愈先兌換

假設要換 120 -> 50 * 2 + 10 * 2 => 一共 4 枚硬幣

換最少硬幣個數問題(在每個幣值之間不一定倍數關係的情況下)

然而，一般來說大部分的問題，局部最佳解未必是全域最佳解。

所以子問題的最佳解未必能能組成整個問題的最佳解

換最少硬幣問題中，假設幣值並非都有倍數關係

舉例來說： 幣值 1, 3, 4, 5 要兌換 7

如果使用 Greedy 策略 就是幣值愈大愈先兌換

會得到 7 -> 5 * 1 + 1* 2 => 一共 3 枚硬幣

然而卻有更少的換法 7 -> 3 * 1 + 4 * 1 => 一共 2枚硬幣 的換法

其原因是當幣值之間不一定是倍數關係時，此問題局部最佳解不一定組成全局最佳解

使用幣值最大使用愈多換得的硬幣不一定愈少

小故事

某個公司會議中

老闆：這次的新產品主題希望是夠創新且有發展性的東西，不知道大家有什麼想法？

主管a: 現在 ai 似互很流行，舉例： ai 在量化交易

主管b: Web3 也不錯，一堆公司要做 Dapp 應用。

同事c: 聽說 ar 很多硬體大廠都支援了，元宇宙正夯。

同事d: iot 然後蒐集大數據，然後做資料分析，好像也很流行！

老闆： 那不如把這些主體都結合在一起，大家覺得如何？

ar 內容然後加入 iot 把資料寫入 blockchain 用 智能合約跑數據分析

所有創新且有發展性都主題都放在一起了

同事e: 是沒聽過這麼酷的產品！

但我知道國產零零七的達文西為了對付金槍客

把七種獨當一面的武器集合起來合成"要你命3000"

後話

有時候局部最佳解不一定是全局最佳解。

手把青秧插滿田，低頭便見水中天，心地清靜方為道，退步原來是向前。 - 插秧歌