算法——貪心算法

貪心算法通過一系列的選擇來得到問題的解。它所做的每一個選擇都是目前狀态下局部的最好選擇，即貪心選擇。

貪心選擇的一般特征：貪心選擇性質和最優子結構性質。

所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動态規劃算法的主要差別。在動态規劃算法中，每步所做的選擇往往依賴于相關子問題的解。因而隻有在解出相關子問題後，才能做出選擇。而在貪心算法中，僅在目前狀态下做出最好選擇，即局部最優選擇。然後再去解出做出這個選擇後産生的相應的子問題。貪心算法所做的貪心選擇可以依賴于以往所做過的選擇，但決不依賴于将來所做的選擇，也不依賴于子問題的解。正是由于這種差别，動态規劃算法通常以自底向上的方式解各個問題，而貪心算法則通常以自頂向下的方式進行，以疊代的方式做出相繼的貪心選擇，沒做一次貪心選擇就将所求問題簡化為規模更小的子問題。

對于一個具體問題，要确定它是否具有貪心選擇性質，必須證明每一步所做的貪心選擇最終導緻問題的整體最優解。

當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。

貪心算法和動态規劃算法都要求問題具有最優子結構性質，這是兩類算法的一個共同點。大多數時候，能用貪心算法求解的問題，都可以用動态規劃算法求解。但是能用動态規劃求解的，不一定能用貪心算法進行求解。

設有n個活動的集合E={1,2,...,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間内隻有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間Si和一個結束時間Fi，且Si<Fi。如果選擇了活動i，則它在半開時間區間[Si,Fi)内占用資源。若區間[Si,Fi)與區間[Sj，Fj）不相交，則稱活動i與活動j是相容的。也就是說Si>=Fj或Sj>=Fi時，活動i與活動j相容。活動安排問題就是要在所給的活動集合中選擇出最大的相容活動子集合。

這個問題可以使用貪心算法進行求解。其實這個問題的關鍵并不是如何用貪心算法求解，而是如何證明這個問題可以用貪心算法求解。鑒于證明的複雜性，還是不在此讨論證明問題。其實貪心算法問題的證明無非都是用數學歸納法證明，不錯就是那個傳說中萬能證明法，數學歸納法。還是直接讨論實作過程吧。

首先将活動按照活動的結束時間非遞減：F1<=F2<=...<=Fn排序。如果所給的活動未排序，則先将活動按此序排列，時間複雜度一般為O(nlogn)可解決。以下是解決問題的算法。

<a></a>

該算法的貪心選擇的意義是使剩餘的可安排的時間段極大化，以便安排盡可能多的相容活動。也就是說，每次選擇完了之後，保證這次的選擇之後留下的時間是最多的。

GreedySelector算法效率極高。當輸入的資料是已經按照結束時間非遞減排序好的時候，算法隻需要O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。

貪心算法并不能總求得問題的整體最優解。但對于某些問題，卻總能求得整體最優解，這要看問題時什麼了。隻要能滿足貪心算法的兩個性質：貪心選擇性質和最優子結構性質，貪心算法就可以出色地求出問題的整體最優解。即使某些問題，貪心算法不能求得整體的最優解，貪心算法也能求出大概的整體最優解。如果你的要求不是太高，貪心算法是一個很好的選擇。最優子結構性質是比較容易看出來的，但是貪心選擇性質就沒那麼容易了，這個時候需要證明。證明往往使用數學歸納法。

适用範圍個人總結的一句話，能證明用就可以用。（因為個人覺得證明比算法實作還難）

計算機算法設計與分析/王曉東編著。-3版。-北京：電子工業出版社，2007.5

本文轉自 Ron Ngai 部落格園部落格，原文連結：http://www.cnblogs.com/rond/archive/2012/07/07/2580737.html  ，如需轉載請自行聯系原作者