算法設(shè)計技巧與分析ppt課件

1、 貪婪算法總是作出在當前看來最好的選擇，也就貪婪算法總是作出在當前看來最好的選擇，也就是說貪婪算法并不從整體最優(yōu)思索，它所作出的是說貪婪算法并不從整體最優(yōu)思索，它所作出的選擇只是在某種意義上的部分最優(yōu)選擇。選擇只是在某種意義上的部分最優(yōu)選擇。 貪婪算法不能對一切問題都得到整體最優(yōu)解，但貪婪算法不能對一切問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪婪算法不能得到整體最優(yōu)解，其最終結(jié)果卻使貪婪算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。

2、是最優(yōu)解的很好近似。 貪婪算法通常用于求解最優(yōu)化問題，即量的最大化或最小貪婪算法通常用于求解最優(yōu)化問題，即量的最大化或最小化問題。算法每一步任務(wù)較少且基于信息，因此特別有效。化問題。算法每一步任務(wù)較少且基于信息，因此特別有效。 貪婪算法通常包含一個用以尋覓部分最優(yōu)解的迭代過程。貪婪算法通常包含一個用以尋覓部分最優(yōu)解的迭代過程。其在少量計算的根底上做出了正確猜測而且不思索以后情其在少量計算的根底上做出了正確猜測而且不思索以后情況，一步步來構(gòu)筑解，每一次均建立在部分最優(yōu)解的根底況，一步步來構(gòu)筑解，每一次均建立在部分最優(yōu)解的根底上。每一步同時又擴展了部分解的規(guī)模，做出的選擇產(chǎn)生上。每一步同時又擴展了

3、部分解的規(guī)模，做出的選擇產(chǎn)生最大的直接納益而又堅持可行性。最大的直接納益而又堅持可行性。 算法缺陷在于要證明該算法確實是求解了要處理的問題。算法缺陷在于要證明該算法確實是求解了要處理的問題。 活動安排問題活動安排問題活動安排問題是可以用貪婪算法有效求活動安排問題是可以用貪婪算法有效求解的一個很好的例子。該問題要求高效地安排一解的一個很好的例子。該問題要求高效地安排一系列爭用某一公共資源的活動。系列爭用某一公共資源的活動。 貪婪算法提供了一個簡單、貪婪算法提供了一個簡單、 美麗的方法使得盡能夠多美麗的方法使得盡能夠多 的活動能兼容地運用公共的活動能兼容地運用公共 資源。資源。 貪婪算法特性：貪婪

4、算法特性：由一個簡單的迭代過程由一個簡單的迭代過程構(gòu)成，在維持可行性的構(gòu)成，在維持可行性的前提下選擇產(chǎn)生最大直前提下選擇產(chǎn)生最大直接利益的項。接利益的項。 設(shè)有設(shè)有n個活動的集合個活動的集合e=1，2，n，其中每個，其中每個活動都要求運用同一資源，如演講會場等，而在活動都要求運用同一資源，如演講會場等，而在同一時間內(nèi)只需一個活動能運用這一資源。每個同一時間內(nèi)只需一個活動能運用這一資源。每個活動活動i都有一個要求運用該資源的起始時間都有一個要求運用該資源的起始時間si和一和一個終了時間個終了時間fi,且且sifi。假設(shè)選擇了活動。假設(shè)選擇了活動i，那么它，那么它在半開時間區(qū)間在半開時間區(qū)間si，

5、fi內(nèi)占用資源。假設(shè)區(qū)間內(nèi)占用資源。假設(shè)區(qū)間si，fi與區(qū)間與區(qū)間sj，fj不相交，那么稱活動不相交，那么稱活動i與活動與活動j是是相容的。也就是說，當相容的。也就是說，當sifi或或sjfj時，活動時，活動i與活與活動動j相容。活動安排問題就是要在所給的活動集合相容?；顒影才艈栴}就是要在所給的活動集合中選出最大的相容活動子集合。中選出最大的相容活動子集合。 在下面所給出的解活動安排問題的貪婪算法在下面所給出的解活動安排問題的貪婪算法schedule中，各活動的起始時間和終了時間存儲中，各活動的起始時間和終了時間存儲于數(shù)組于數(shù)組s和和f中且按終了時間的非減序：中且按終了時間的非減序：. f1f

6、2 fn陳列。假設(shè)所給出的活動未按此序陳列，陳列。假設(shè)所給出的活動未按此序陳列，我們可以用我們可以用o(nlogn)的時間將它重排。的時間將它重排。 活動安排問題活動安排問題int 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;elseai=false;coutthe least amount meeting place is :n;return n; 算法算法schedule中用集合中用集合a來存儲所選擇的活動?；顏泶鎯λx擇的活動?；顒觿觟在集合在集合a中，

7、當且僅當中，當且僅當ai的值為的值為true。變量。變量 n用以記錄最近一次參與到用以記錄最近一次參與到a中的活動。中的活動。 貪婪算法貪婪算法schedule一開場選擇活動一開場選擇活動1，并將，并將n初始初始化為化為1。然后依次檢查活動。然后依次檢查活動i能否與當前已選擇的能否與當前已選擇的一切活動相容。假設(shè)相容那么將活動一切活動相容。假設(shè)相容那么將活動i加人到已選加人到已選擇活動的集合擇活動的集合a中，否那么不選擇活動中，否那么不選擇活動i，而繼續(xù)，而繼續(xù)檢查下一活動與集合檢查下一活動與集合a中活動的相容性。中活動的相容性。 完好程序完好程序 #include using namespa

8、ce 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;i+) coutfi,;coutendl;int 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; 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;coutplease inputthe end_timeendl;int *et=new intr+1;f