貪心算法

郝文姣

貪心算法最早由J.C.Warnsdorff于1823年提出，是指在對問題求解時，總是做出當前最優選擇，即局部最優解。貪心算法有兩個基本要素：即貪心選擇和最優子結構。它是最接近人類日常思維方式的一種解題策略，本質上是一種改進了的分級處理方法。雖不保證所求解是最佳選擇，但可為所求問題確定可行范圍，它采用自頂向下的方式，以迭代方法做出選擇，相比其他算法更具速度優勢。

貪心算法是一種重要的算法設計策略而且具有高效性，因其不從整體最優考慮，只在局部最優中進行選擇，即當前看來最好的選擇。貪心算法具有良好的爬坡能力，可較快求出滿足計算精度要求的近似最優解。相比動態規劃法更加簡單和直觀。

貪心算法在科學計算和工程中的應用越來越廣泛，例如在三角部分的指紋匹配這一高科技領域已經取得重大進展。未來，在排課系統、貪心聚類算法以及在遙感圖像分類和壓縮中的應用也會更加成熟。只要符合貪心策略，就可利用貪心算法求解。

貪心算法對許多問題不能總是產生最優解，但可以解決最短路徑問題、最小生成樹問題、哈夫曼編碼等問題。隨著問題規模和復雜度的不斷提升，單一算法在其收斂性和求解速度等方面已經表現出局限性。此外，貪心算法的高效性也只適用于少量實例。