算法設計技巧與分析

1、2022/4/10 linzhenjie12022/4/10 linzhenjie2 貪心算法總是作出在當前看來最好的選擇，也就貪心算法總是作出在當前看來最好的選擇，也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的選擇只是在某種意義上的局部最優(yōu)局部最優(yōu)選擇。選擇。 貪心算法不能對所有問題都得到整體最優(yōu)解，但貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產生整體最優(yōu)解。如單源最短路對許多問題它能產生整體最優(yōu)解。如單源最短路經問題，最小生成樹問題等。在一些情況下，即經問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整

2、體最優(yōu)解，其最終結果卻使貪心算法不能得到整體最優(yōu)解，其最終結果卻是最優(yōu)解的很好近似。是最優(yōu)解的很好近似。2022/4/10 linzhenjie3 貪心算法通常用于求解最優(yōu)化問題，即量的最大化或最小貪心算法通常用于求解最優(yōu)化問題，即量的最大化或最小化問題。算法每一步工作較少且基于信息，因此特別有效?；瘑栴}。算法每一步工作較少且基于信息，因此特別有效。 貪心算法通常包含一個用以尋找局部最優(yōu)解的迭代過程。貪心算法通常包含一個用以尋找局部最優(yōu)解的迭代過程。其在少量計算的基礎上做出了正確猜想而且不考慮以后情其在少量計算的基礎上做出了正確猜想而且不考慮以后情況，一步步來構筑解，每一次均建立在局部最優(yōu)解的

3、基礎況，一步步來構筑解，每一次均建立在局部最優(yōu)解的基礎上。每一步同時又擴大了部分解的規(guī)模，做出的選擇產生上。每一步同時又擴大了部分解的規(guī)模，做出的選擇產生最大的直接收益而又保持可行性。最大的直接收益而又保持可行性。 算法缺陷在于要證明該算法確實是求解了要解決的問題。算法缺陷在于要證明該算法確實是求解了要解決的問題。2022/4/10 linzhenjie4 活動安排問題活動安排問題活動安排問題是可以用貪心算法有效求解的活動安排問題是可以用貪心算法有效求解的一個很好的例子。該問題要求高效地安排一系列一個很好的例子。該問題要求高效地安排一系列爭用某一公共資源的活動。爭用某一公共資源的活動。 貪心算

4、法提供了一個簡單、貪心算法提供了一個簡單、 漂亮的方法使得盡可能多漂亮的方法使得盡可能多 的活動能兼容地使用公共的活動能兼容地使用公共 資源。資源。 貪心算法特性：貪心算法特性：由一個簡單的迭代過程由一個簡單的迭代過程構成，在維持可行性的構成，在維持可行性的前提下選擇產生最大直前提下選擇產生最大直接利益的項。接利益的項。2022/4/10 linzhenjie5 設有設有n個活動的集合個活動的集合e=1，2，n，其中每個，其中每個活動都要求使用同一資源，如演講會場等，而在活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個同一時間內只有一個活動能使用這一資源。每

5、個活動活動i都有一個要求使用該資源的起始時間都有一個要求使用該資源的起始時間si和一和一個結束時間個結束時間fi,且且sifi。如果選擇了活動。如果選擇了活動i，則它在，則它在半開時間區(qū)間半開時間區(qū)間si，fi內占用資源。若區(qū)間內占用資源。若區(qū)間si，fi與區(qū)間與區(qū)間sj，fj不相交，則稱活動不相交，則稱活動i與活動與活動j是相容是相容的。也就是說，當?shù)?。也就是說，當sifi或或sjfj時，活動時，活動i與活動與活動j相相容。活動安排問題就是要在所給的活動集合中選容?；顒影才艈栴}就是要在所給的活動集合中選出最大的相容活動子集合。出最大的相容活動子集合。 2022/4/10 linzhenjie

6、6 在下面所給出的解活動安排問題的貪心算法在下面所給出的解活動安排問題的貪心算法中，各活動的起始時間和結束時間存儲中，各活動的起始時間和結束時間存儲于數(shù)組于數(shù)組s和和f中且按結束時間的非減序：中且按結束時間的非減序：. f1f2 fn排列。排列。如果所給出的活動未按此序排列，如果所給出的活動未按此序排列，我們可以用我們可以用o(nlogn)的時間將它重排。的時間將它重排。 2022/4/10 linzhenjie7 活動安排問題活動安排問題int schedule(int s,int f,bool a,int r)int n=1;int j=0;a0=true;for(int i=1;i=fj

7、)ai=true;n+;j=i;elseai=false;coutthe least amount meeting place is :n;return n;2022/4/10 linzhenjie9 算法算法中用集合中用集合 來存儲所選擇的活動。來存儲所選擇的活動?；顒踊顒觟在集合在集合a中，當且僅當中，當且僅當ai的值為的值為true。變量。變量 n用以記錄最近一次加入到用以記錄最近一次加入到a中的活動。中的活動。 貪心算法貪心算法一開始選擇活動一開始選擇活動1，并將，并將n初始初始化為化為1。然后依次檢查活動。然后依次檢查活動i是否與當前已選擇的是否與當前已選擇的所有活動相容。若相容則將

8、活動所有活動相容。若相容則將活動i加人到已選擇活加人到已選擇活動的集合動的集合a中，否則不選擇活動中，否則不選擇活動i，而繼續(xù)檢查下，而繼續(xù)檢查下一活動與集合一活動與集合a中活動的相容性。中活動的相容性。 2022/4/10 linzhenjie10 完整程序完整程序 #include using namespace std; void sort(int f,int n) int temp; for(int i=1;in;i+) for(int j=0;jfj+1) temp=fj; fj=fj+1; fj+1=temp;coutthe sort result:endl;for( i=0;in

9、;i+) coutfi,;coutendl;2022/4/10 linzhenjie12int schedule(int s,int f,bool a,int r) int n=1; int j=0; a0=true; for(int i=1;i=fj) ai=true;n+;j=i; else ai=false; coutthe least amount meeting place is :n;2022/4/10 linzhenjie13 return n; void main() int r;/活動數(shù)活動數(shù) int p=0; coutplease input the activity quantityr; coutplease input the start_timeendl; int *st=new intr+1; bool *a=new boolr+1; for(int i=0;isti;2022/4/10 linzhenjie14coutplease inputthe end_timeendl;int *et=n