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

1、 貪婪算法總是作出在當(dāng)前看來最好的選擇，也就貪婪算法總是作出在當(dāng)前看來最好的選擇，也就是說貪婪算法并不從整體最優(yōu)思索，它所作出的是說貪婪算法并不從整體最優(yōu)思索，它所作出的選擇只是在某種意義上的部分最優(yōu)選擇。選擇只是在某種意義上的部分最優(yōu)選擇。 貪婪算法不能對(duì)一切問題都得到整體最優(yōu)解，但貪婪算法不能對(duì)一切問題都得到整體最優(yōu)解，但對(duì)許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路對(duì)許多問題它能產(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ù)較少且基于信息，因此特別有效。 貪婪算法通常包含一個(gè)用以尋覓部分最優(yōu)解的迭代過程。貪婪算法通常包含一個(gè)用以尋覓部分最優(yōu)解的迭代過程。其在少量計(jì)算的根底上做出了正確猜測(cè)而且不思索以后情其在少量計(jì)算的根底上做出了正確猜測(cè)而且不思索以后情況，一步步來構(gòu)筑解，每一次均建立在部分最優(yōu)解的根底況，一步步來構(gòu)筑解，每一次均建立在部分最優(yōu)解的根底上。每一步同時(shí)又?jǐn)U展了部分解的規(guī)模，做出的選擇產(chǎn)生上。每一步同時(shí)又?jǐn)U展了

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

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

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

6、2 fn陳列。假設(shè)所給出的活動(dòng)未按此序陳列，陳列。假設(shè)所給出的活動(dòng)未按此序陳列，我們可以用我們可以用o(nlogn)的時(shí)間將它重排。的時(shí)間將它重排。 活動(dòng)安排問題活動(dòng)安排問題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來存儲(chǔ)所選擇的活動(dòng)?；顏泶鎯?chǔ)所選擇的活動(dòng)?；顒?dòng)動(dòng)i在集合在集合a中，

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