貪心算法

郝文姣

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

貪心算法是一種重要的算法設(shè)計(jì)策略而且具有高效性，因其不從整體最優(yōu)考慮，只在局部最優(yōu)中進(jìn)行選擇，即當(dāng)前看來最好的選擇。貪心算法具有良好的爬坡能力，可較快求出滿足計(jì)算精度要求的近似最優(yōu)解。相比動(dòng)態(tài)規(guī)劃法更加簡(jiǎn)單和直觀。

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

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