[Pre class]Greedy algorithm

"

貪心法Greedy algorithm ,直譯:貪心演算法) 是一種在每一步選擇中都採取在當前狀態下最好或最優(即最有利)的選擇,從而希望導致結果是最好或最優的演算法。比如在旅行推銷員問題中,如果旅行員每次都選擇最近的城市,那這就是一種貪心演算法。

貪心演算法在有最優子結構的問題中尤為有效。最優子結構的意思是局部最優解能決定全局最優解。簡單地說,問題能夠分解成子問題來解決,子問題的最優解能遞推到最終問題的最優解。

貪心演算法與動態規劃的不同在於它每對每個子問題的解決方案都做出選擇,不能回退。動態規劃則會保存以前的運算結果,並根據以前的結果對當前進行選擇,有回退功能。

貪心法可以解決一些最優性問題,如:求中的最小生成樹、求哈夫曼編碼……對於其他問題,貪心法一般不能得到我們所要求的答案。一旦一個問題可以通過貪心法來解決,那麼貪心法一般是解決這個問題的最好辦法。由於貪心法的高效性以及其所求得的答案比較接近最優結果,貪心法也可以用作輔助演算法或者直接解決一些要求結果不特別精確的問題。

 資料來源:維基百科(http://zh.wikipedia.org/w/index.php?title=%E9%A6%96%E9%A1%B5&variant=zh-tw)

[@more@]"