1. 貪婪算法很簡單：每步都采取最優(yōu)的做法撞蚕。用專業(yè)術(shù)語說，就是你每步都選擇局部最優(yōu)解聪富，最終得到的就是全局最優(yōu)解愕宋。
2. NP完全問題
所有的非確定性多項式時間可解的判定問題構(gòu)成NP類問題
-
世界七大數(shù)學(xué)難題之一
美國麻州的[克雷]（Clay）數(shù)學(xué)研究所于2000年5月24日在巴黎法蘭西學(xué)院宣布了一件被媒體炒得火熱的大事：對七個“千僖年數(shù)學(xué)難題”的每一個懸賞一百萬美元玻靡。“千僖難題”之一：P （確定性多項式算法）對NP （非確定性多項式算法）
“千僖難題”之二：霍奇（Hodge）猜想
“千僖難題”之三：龐加萊（Poincare）猜想
“千僖難題”之四：黎曼（Riemann）假設(shè)
“千僖難題”之五：楊－米爾斯（Yang-Mills）存在性和質(zhì)量缺口
“千僖難題”之六：納維葉－斯托克斯（Navier-Stokes）方程的存在性與光滑性
“千僖難題”之七：貝赫（Birch）和斯維訥通－戴爾（Swinnerton-Dyer）猜想
NP完全問題排在百萬美元大獎的首位，足見他的顯赫地位和無窮魅力中贝。
3.如何識別NP問題
- 元素較少時算法的運行速度非扯谀恚快，但隨著元素數(shù)量的增加邻寿，速度會變得非常慢蝎土。
- 涉及“所有組合”的問題通常是NP完全問題视哑。
- 不能將問題分成小問題，必須考慮各種可能的情況誊涯。這可能是NP完全問題挡毅。
- 如果問題涉及序列（如旅行商問題中的城市序列）且難以解決，它可能就是NP完全問題醋拧。
- 如果問題涉及集合（如廣播臺集合）且難以解決慷嗜，它可能就是NP完全問題。
- 如果問題可轉(zhuǎn)換為集合覆蓋問題或旅行商問題丹壕，那它肯定是NP完全問題庆械。
4.小結(jié)
- 貪婪算法尋找局部最優(yōu)解，企圖以這種方式獲得全局最優(yōu)解菌赖。
- 對于NP完全問題缭乘，還沒有找到快速解決方案。
- 面臨NP完全問題時琉用，最佳的做法是使用近似算法堕绩。
- 貪婪算法易于實現(xiàn)、運行速度快邑时，是不錯的近似算法奴紧。
