My friends, my life, my style - James S.F. Hsieh

2/02/2009

Greedy algorithm and Greedy strategy

學過演算法的朋友們應該都學過一個有名的演算策略那就是貪婪法 Greedy algorithm, 這個演算法有容易實做, 控制狀態少, 並且效率高的幾個特點. 但是, 它往往會被誤用, 為什麼呢? 原則上貪婪法是一種動態規劃的特殊形式, 怎樣的問題才能使用動態規劃 Dynamic programming 來找出解呢? 那就是問題必須要符合 Optimal substructure 這種特性, 以下就是對這種特性有名的描述

A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems. Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 16 "Greedy Algorithms".

當然, 貪婪法比動態規劃的限制要多的更多, 因為只有當每次選擇的 sub-optimal solution 所組合出來的 solution 也會是整體的 optimal solution 時, 這個演算策略才有意義. 這也就是為什麼貪婪法常常會被誤用的原因, 因為它容易思考, 直覺與並且易於實踐, 但要證明該問題適用於貪婪法是相對的困難.

很多事情也是如此, 不只有在演算法這個範疇, 就以我常遇到道的軟體開發來說, 這個問題也時常出現, 許多的貪婪策略一直不斷的被誤用. 軟體發展到現行的商業競爭中, 是種跟時間賽跑的競爭模式, 因為, 似乎大家的創新跟點子都差不了太多, 能夠早點切入市場變成為關鍵性的因素. 由這樣的特質導致軟體需要快速的被開發, 但是 "快速" 這個需求就產生了截然不同的多種策略. 首先我相信軟體設計這個問題是具有 Optimal substructure 的特性, 簡單的說它是可以利用多個 sub-optimal solution 產生出最佳的 optimal solution, 但是, 有兩個盲點: 1. 所謂的最佳有很多種相度, 最短時間, 最佳的設計, 最少人力, 最安全, 最高品質, 讓使用者最上手的操作流程等等, 軟體開發的相度遠比我們想像的多 2. 即使有個綜合所有相度的衡量標準, 在每次選擇當下最佳解的策略進行發展下, 也無法得到整體性的最佳解, 何況這個衡量標準也不一定存在, 因為這些相度可能是互斥的. 基於上述的論點, Greedy strategy 在軟體開發上是不可行的, 這樣的策略下, 往往只是疊床架屋, 浮沙築高台.

每當要評估軟體開發的時程時, 最常看到的就是

Could you comment which way take less engineer effort to maintain? Please consider schedule as well.....

明顯的貪婪策略, 至於 Effort 這個字, 我想翻譯成 "麻煩" 是最恰當的, 可以見得, 發展軟體的態度與文化深深影響著軟體品質, 這也是決定整體是否正向循環的決定性因素.