小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

從零開始學(xué)貪心算法

 紫荊花書屋61 2017-02-28
本文在寫作過程中參考了大量資料，不能一一列舉，還請(qǐng)見諒。
貪心算法的定義：
貪心算法是指在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，只做出在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個(gè)狀態(tài)以前的過程不會(huì)影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。
解題的一般步驟是：
1.建立數(shù)學(xué)模型來描述問題；
2.把求解的問題分成若干個(gè)子問題；
3.對(duì)每一子問題求解，得到子問題的局部最優(yōu)解；
4.把子問題的局部最優(yōu)解合成原來問題的一個(gè)解。
如果大家比較了解動(dòng)態(tài)規(guī)劃，就會(huì)發(fā)現(xiàn)它們之間的相似之處。最優(yōu)解問題大部分都可以拆分成一個(gè)個(gè)的子問題，把解空間的遍歷視作對(duì)子問題樹的遍歷，則以某種形式對(duì)樹整個(gè)的遍歷一遍就可以求出最優(yōu)解，大部分情況下這是不可行的。貪心算法和動(dòng)態(tài)規(guī)劃本質(zhì)上是對(duì)子問題樹的一種修剪，兩種算法要求問題都具有的一個(gè)性質(zhì)就是子問題最優(yōu)性(組成最優(yōu)解的每一個(gè)子問題的解，對(duì)于這個(gè)子問題本身肯定也是最優(yōu)的)。動(dòng)態(tài)規(guī)劃方法代表了這一類問題的一般解法，我們自底向上構(gòu)造子問題的解，對(duì)每一個(gè)子樹的根，求出下面每一個(gè)葉子的值，并且以其中的最優(yōu)值作為自身的值，其它的值舍棄。而貪心算法是動(dòng)態(tài)規(guī)劃方法的一個(gè)特例，可以證明每一個(gè)子樹的根的值不取決于下面葉子的值，而只取決于當(dāng)前問題的狀況。換句話說，不需要知道一個(gè)節(jié)點(diǎn)所有子樹的情況，就可以求出這個(gè)節(jié)點(diǎn)的值。由于貪心算法的這個(gè)特性，它對(duì)解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優(yōu)的路，一直走到底就可以了。
話不多說，我們來看幾個(gè)具體的例子慢慢理解它：
1.活動(dòng)選擇問題
 這是《算法導(dǎo)論》上的例子，也是一個(gè)非常經(jīng)典的問題。有n個(gè)需要在同一天使用同一個(gè)教室的活動(dòng)a1,a2,…,an，教室同一時(shí)刻只能由一個(gè)活動(dòng)使用。每個(gè)活動(dòng)ai都有一個(gè)開始時(shí)間si和結(jié)束時(shí)間fi 。一旦被選擇后，活動(dòng)ai就占據(jù)半開時(shí)間區(qū)間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個(gè)活動(dòng)就可以被安排在這一天。該問題就是要安排這些活動(dòng)使得盡量多的活動(dòng)能不沖突的舉行。例如下圖所示的活動(dòng)集合S，其中各項(xiàng)活動(dòng)按照結(jié)束時(shí)間單調(diào)遞增排序。


考慮使用貪心算法的解法。為了方便，我們用不同顏色的線條代表每個(gè)活動(dòng)，線條的長度就是活動(dòng)所占據(jù)的時(shí)間段，藍(lán)色的線條表示我們已經(jīng)選擇的活動(dòng)；紅色的線條表示我們沒有選擇的活動(dòng)。
如果我們每次都選擇開始時(shí)間最早的活動(dòng)，不能得到最優(yōu)解：


如果我們每次都選擇持續(xù)時(shí)間最短的活動(dòng)，不能得到最優(yōu)解：


可以用數(shù)學(xué)歸納法證明，我們的貪心策略應(yīng)該是每次選取結(jié)束時(shí)間最早的活動(dòng)。直觀上也很好理解，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。這也是把各項(xiàng)活動(dòng)按照結(jié)束時(shí)間單調(diào)遞增排序的原因。

  1. #include<cstdio>  
  2. #include<iostream>   
  3. #include<algorithm>   
  4. using namespace std;      
  5. int N;  
  6. struct Act  
  7. {  
  8.     int start;  
  9.     int end;  
  10. }act[100010];  
  11.   
  12. bool cmp(Act a,Act b)    
  13. {    
  14.     return a.end<b.end;    
  15. }   
  16.   
  17. int greedy_activity_selector()    
  18. {    
  19.     int num=1,i=1;     
  20.     for(int j=2;j<=N;j++)    
  21.     {    
  22.         if(act[j].start>=act[i].end)    
  23.         {    
  24.             i=j;    
  25.             num++;    
  26.         }    
  27.     }    
  28.     return num;  
  29. }  
  30.   
  31. int main()    
  32. {    
  33.     int t;  
  34.     scanf("%d",&t);  
  35.     while(t--)  
  36.     {  
  37.         scanf("%d",&N);  
  38.         for(int i=1;i<=N;i++)  
  39.         {  
  40.             scanf("%lld %lld",&act[i].start,&act[i].end);  
  41.         }  
  42.         act[0].start=-1;  
  43.         act[0].end=-1;  
  44.         sort(act+1,act+N+1,cmp);   
  45.         int res=greedy_activity_selector();  
  46.         cout<<res<<endl;    
  47.     }  
  48. }    
2.錢幣找零問題
這個(gè)問題在我們的日常生活中就更加普遍了。假設(shè)1元、2元、5元、10元、20元、50元、100元的紙幣分別有c0, c1, c2, c3, c4, c5, c6張?，F(xiàn)在要用這些錢來支付K元，至少要用多少張紙幣？用貪心算法的思想，很顯然，每一步盡可能用面值大的紙幣即可。在日常生活中我們自然而然也是這么做的。在程序中已經(jīng)事先將Value按照從小到大的順序排好。
  1. #include<iostream>  
  2. #include<algorithm>  
  3. using namespace std;  
  4. const int N=7;   
  5. int Count[N]={3,0,2,1,0,3,5};  
  6. int Value[N]={1,2,5,10,20,50,100};  
  7.     
  8. int solve(int money)   
  9. {  
  10.     int num=0;  
  11.     for(int i=N-1;i>=0;i--)   
  12.     {  
  13.         int c=min(money/Value[i],Count[i]);  
  14.         money=money-c*Value[i];  
  15.         num+=c;  
  16.     }  
  17.     if(money>0) num=-1;  
  18.     return num;  
  19. }  
  20.    
  21. int main()   
  22. {  
  23.     int money;  
  24.     cin>>money;  
  25.     int res=solve(money);  
  26.     if(res!=-1) cout<<res<<endl;  
  27.     else cout<<"NO"<<endl;  
  28. }  
3.再論背包問題
在從零開始學(xué)動(dòng)態(tài)規(guī)劃中我們已經(jīng)談過三種最基本的背包問題：零一背包，部分背包，完全背包。很容易證明，背包問題不能使用貪心算法。然而我們考慮這樣一種背包問題：在選擇物品i裝入背包時(shí)，可以選擇物品的一部分，而不一定要全部裝入背包。這時(shí)便可以使用貪心算法求解了。計(jì)算每種物品的單位重量價(jià)值作為貪心選擇的依據(jù)指標(biāo)，選擇單位重量價(jià)值最高的物品，將盡可能多的該物品裝入背包，依此策略一直地進(jìn)行下去，直到背包裝滿為止。在零一背包問題中貪心選擇之所以不能得到最優(yōu)解原因是貪心選擇無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。在程序中已經(jīng)事先將單位重量價(jià)值按照從大到小的順序排好。
  1. #include<iostream>     
  2. using namespace std;     
  3. const int N=4;    
  4. void knapsack(float M,float v[],float w[],float x[]);    
  5.     
  6. int main()    
  7. {    
  8.     float M=50;  
  9.     //背包所能容納的重量     
  10.     float w[]={0,10,30,20,5};  
  11.     //每種物品的重量    
  12.     float v[]={0,200,400,100,10};    
  13.     //每種物品的價(jià)值   
  14.     float x[N+1]={0};    
  15.     //記錄結(jié)果的數(shù)組   
  16.     knapsack(M,v,w,x);    
  17.     cout<<"選擇裝下的物品比例："<<endl;    
  18.     for(int i=1;i<=N;i++) cout<<"["<<i<<"]:"<<x[i]<<endl;    
  19. }    
  20.     
  21. void knapsack(float M,float v[],float w[],float x[])    
  22. {    
  23.     int i;    
  24.     //物品整件被裝下    
  25.     for(i=1;i<=N;i++)  
  26.     {    
  27.         if(w[i]>M) break;     
  28.         x[i]=1;    
  29.         M-=w[i];    
  30.     }     
  31.     //物品部分被裝下    
  32.     if(i<=N) x[i]=M/w[i];     
  33. }   

4.多機(jī)調(diào)度問題
n個(gè)作業(yè)組成的作業(yè)集，可由m臺(tái)相同機(jī)器加工處理。要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。作業(yè)不能拆分成更小的子作業(yè)；每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理。這個(gè)問題是NP完全問題，還沒有有效的解法(求最優(yōu)解)，但是可以用貪心選擇策略設(shè)計(jì)出較好的近似算法(求次優(yōu)解)。當(dāng)n<=m時(shí)，只要將作業(yè)時(shí)間區(qū)間分配給作業(yè)即可；當(dāng)n>m時(shí)，首先將n個(gè)作業(yè)從大到小排序，然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機(jī)。也就是說從剩下的作業(yè)中，選擇需要處理時(shí)間最長的，然后依次選擇處理時(shí)間次長的，直到所有的作業(yè)全部處理完畢，或者機(jī)器不能再處理其他作業(yè)為止。如果我們每次是將需要處理時(shí)間最短的作業(yè)分配給空閑的機(jī)器，那么可能就會(huì)出現(xiàn)其它所有作業(yè)都處理完了只剩所需時(shí)間最長的作業(yè)在處理的情況，這樣勢必效率較低。在下面的代碼中沒有討論n和m的大小關(guān)系，把這兩種情況合二為一了。

  1. #include<iostream>    
  2. #include<algorithm>      
  3. using namespace std;    
  4. int speed[10010];    
  5. int mintime[110];    
  6.   
  7. bool cmp( const int &x,const int &y)    
  8. {    
  9.     return x>y;    
  10. }    
  11.   
  12. int main()    
  13. {    
  14.     int n,m;           
  15.     memset(speed,0,sizeof(speed));    
  16.     memset(mintime,0,sizeof(mintime));    
  17.     cin>>n>>m;    
  18.     for(int i=0;i<n;++i) cin>>speed[i];    
  19.     sort(speed,speed+n,cmp);    
  20.     for(int i=0;i<n;++i)     
  21.     {   
  22.         *min_element(mintime,mintime+m)+=speed[i];     
  23.     }     
  24.     cout<<*max_element(mintime,mintime+m)<<endl;   
  25. }  

5.小船過河問題
POJ1700是一道經(jīng)典的貪心算法例題。題目大意是只有一艘船，能乘2人，船的運(yùn)行速度為2人中較慢一人的速度，過去后還需一個(gè)人把船劃回來，問把n個(gè)人運(yùn)到對(duì)岸，最少需要多久。先將所有人過河所需的時(shí)間按照升序排序，我們考慮把單獨(dú)過河所需要時(shí)間最多的兩個(gè)旅行者送到對(duì)岸去，有兩種方式：
1.最快的和次快的過河，然后最快的將船劃回來；次慢的和最慢的過河，然后次快的將船劃回來，所需時(shí)間為：t[0]+2*t[1]+t[n-1]；
2.最快的和最慢的過河，然后最快的將船劃回來，最快的和次慢的過河，然后最快的將船劃回來，所需時(shí)間為：2*t[0]+t[n-2]+t[n-1]。
算一下就知道，除此之外的其它情況用的時(shí)間一定更多。每次都運(yùn)送耗時(shí)最長的兩人而不影響其它人，問題具有貪心子結(jié)構(gòu)的性質(zhì)。
AC代碼：

  1. #include<iostream>  
  2. #include<algorithm>  
  3. using namespace std;  
  4.   
  5. int main()  
  6. {  
  7.     int a[1000],t,n,sum;  
  8.     scanf("%d",&t);  
  9.     while(t--)  
  10.     {  
  11.         scanf("%d",&n);  
  12.         sum=0;  
  13.         for(int i=0;i<n;i++) scanf("%d",&a[i]);  
  14.         while(n>3)  
  15.         {  
  16.             sum=min(sum+a[1]+a[0]+a[n-1]+a[1],sum+a[n-1]+a[0]+a[n-2]+a[0]);  
  17.             n-=2;  
  18.         }  
  19.         if(n==3) sum+=a[0]+a[1]+a[2];  
  20.         else if(n==2) sum+=a[1];  
  21.         else sum+=a[0];  
  22.         printf("%d\n",sum);  
  23.     }  
  24. }  

6.區(qū)間覆蓋問題
POJ1328是一道經(jīng)典的貪心算法例題。題目大意是假設(shè)海岸線是一條無限延伸的直線。陸地在海岸線的一側(cè)，而海洋在另一側(cè)。每一個(gè)小的島嶼是海洋上的一個(gè)點(diǎn)。雷達(dá)坐落于海岸線上，只能覆蓋d距離，所以如果小島能夠被覆蓋到的話，它們之間的距離最多為d。題目要求計(jì)算出能夠覆蓋給出的所有島嶼的最少雷達(dá)數(shù)目。對(duì)于每個(gè)小島，我們可以計(jì)算出一個(gè)雷達(dá)所在位置的區(qū)間。


問題轉(zhuǎn)化為如何用盡可能少的點(diǎn)覆蓋這些區(qū)間。先將所有區(qū)間按照左端點(diǎn)大小排序，初始時(shí)需要一個(gè)點(diǎn)。如果兩個(gè)區(qū)間相交而不重合，我們什么都不需要做；如果一個(gè)區(qū)間完全包含于另外一個(gè)區(qū)間，我們需要更新區(qū)間的右端點(diǎn)；如果兩個(gè)區(qū)間不相交，我們需要增加點(diǎn)并更新右端點(diǎn)。
AC代碼：

  1. #include<cmath>  
  2. #include<iostream>  
  3. #include<algorithm>  
  4. using namespace std;  
  5. struct Point  
  6. {  
  7.     double x;  
  8.     double y;  
  9. }point[1000];  
  10.   
  11. int cmp(const void *a, const void *b)  
  12. {  
  13.     return (*(Point *)a).x>(*(Point *)b).x?1:-1;  
  14. }  
  15.   
  16. int main()  
  17. {  
  18.     int n,d;  
  19.     int num=1;  
  20.     while(cin>>n>>d)  
  21.     {  
  22.         int counting=1;  
  23.         if(n==0&&d==0) break;  
  24.         for(int i=0;i<n;i++)  
  25.         {  
  26.             int x,y;  
  27.             cin>>x>>y;  
  28.             if(y>d)  
  29.             {  
  30.                 counting=-1;  
  31.             }  
  32.             double t=sqrt(d*d-y*y);  
  33.             //轉(zhuǎn)化為最少區(qū)間的問題   
  34.             point[i].x=x-t;  
  35.             //區(qū)間左端點(diǎn)   
  36.             point[i].y=x+t;  
  37.             //區(qū)間右端點(diǎn)   
  38.         }  
  39.         if(counting!=-1)  
  40.         {  
  41.             qsort(point,n,sizeof(point[0]),cmp);  
  42.             //按區(qū)間左端點(diǎn)排序   
  43.             double s=point[0].y;  
  44.             //區(qū)間右端點(diǎn)   
  45.             for(int i=1;i<n;i++)  
  46.             {  
  47.                 if(point[i].x>s)  
  48.                 //如果兩個(gè)區(qū)間沒有重合,增加雷達(dá)數(shù)目并更新右端點(diǎn)   
  49.                 {  
  50.                     counting++;  
  51.                     s=point[i].y;   
  52.                 }  
  53.                 else if(point[i].y<s)  
  54.                 //如果第二個(gè)區(qū)間被完全包含于第一個(gè)區(qū)間,更新右端點(diǎn)   
  55.                 {  
  56.                     s=point[i].y;  
  57.                 }  
  58.             }  
  59.         }  
  60.         cout<<"Case "<<num<<':'<<' '<<counting<<endl;  
  61.         num++;   
  62.     }  
  63. }     

7.銷售比賽
在學(xué)校OJ上做的一道比較好的題，這里碼一下。假設(shè)有偶數(shù)天，要求每天必須買一件物品或者賣一件物品，只能選擇一種操作并且不能不選，開始手上沒有這種物品。現(xiàn)在給你每天的物品價(jià)格表，要求計(jì)算最大收益。首先要明白，第一天必須買，最后一天必須賣，并且最后手上沒有物品。那么除了第一天和最后一天之外我們每次取兩天，小的買大的賣，并且把賣的價(jià)格放進(jìn)一個(gè)最小堆。如果買的價(jià)格比堆頂還大，就交換。這樣我們保證了賣的價(jià)格總是大于買的價(jià)格，一定能取得最大收益。

  1. #include<queue>  
  2. #include<vector>  
  3. #include<cstdio>  
  4. #include<cstdlib>  
  5. #include<cstring>  
  6. #include<iostream>  
  7. #include<algorithm>  
  8. using namespace std;  
  9. long long int price[100010],t,n,res;  
  10.          
  11. int main()  
  12. {  
  13.     ios::sync_with_stdio(false);  
  14.     cin>>t;  
  15.     while(t--)  
  16.     {  
  17.         cin>>n;  
  18.         priority_queue<long long int, vector<long long int>, greater<long long int> > q;  
  19.         res=0;  
  20.         for(int i=1;i<=n;i++)  
  21.         {  
  22.             cin>>price[i];  
  23.         }  
  24.         res-=price[1];  
  25.         res+=price[n];  
  26.         for(int i=2;i<=n-1;i=i+2)  
  27.         {  
  28.             long long int buy=min(price[i],price[i+1]);  
  29.             long long int sell=max(price[i],price[i+1]);  
  30.             if(!q.empty())  
  31.             {  
  32.                 if(buy>q.top())  
  33.                 {  
  34.                     res=res-2*q.top()+buy+sell;  
  35.                     q.pop();  
  36.                     q.push(buy);  
  37.                     q.push(sell);  
  38.                 }  
  39.                 else  
  40.                 {  
  41.                     res=res-buy+sell;  
  42.                     q.push(sell);  
  43.                 }  
  44.             }  
  45.             else  
  46.             {  
  47.                 res=res-buy+sell;  
  48.                 q.push(sell);  
  49.             }  
  50.         }       
  51.         cout<<res<<endl;  
  52.     }  
  53. }  

下面我們結(jié)合數(shù)據(jù)結(jié)構(gòu)中的知識(shí)講解幾個(gè)例子。
8.Huffman編碼
這同樣是《算法導(dǎo)論》上的例子。Huffman編碼是廣泛用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。我們可以有多種方式表示文件中的信息，如果用01串表示字符，采用定長編碼表示，則需要3位表示一個(gè)字符，整個(gè)文件編碼需要300000位；采用變長編碼表示，給頻率高的字符較短的編碼，頻率低的字符較長的編碼，達(dá)到整體編碼減少的目的，則整個(gè)文件編碼需要(45×1+13×3+12×3+16×3+9×4+5×4)×1000=224000位，由此可見，變長碼比定長碼方案好，總碼長減小約25%。


 對(duì)每一個(gè)字符規(guī)定一個(gè)01串作為其代碼，并要求任一字符的代碼都不是其他字符代碼的前綴，這種編碼稱為前綴碼?？赡軣o前綴碼是一個(gè)更好的名字，但是前綴碼是一致認(rèn)可的標(biāo)準(zhǔn)術(shù)語。編碼的前綴性質(zhì)可以使譯碼非常簡單：例如001011101可以唯一的分解為0,0,101,1101，因而其譯碼為aabe。譯碼過程需要方便的取出編碼的前綴，為此可以用二叉樹作為前綴碼的數(shù)據(jù)結(jié)構(gòu)：樹葉表示給定字符；從樹根到樹葉的路徑當(dāng)作該字符的前綴碼；代碼中每一位的0或1分別作為指示某節(jié)點(diǎn)到左兒子或右兒子的路標(biāo)。


從上圖可以看出，最優(yōu)前綴編碼碼的二叉樹總是一棵完全二叉樹，而定長編碼的二叉樹不是一棵完全二叉樹。 給定編碼字符集C及頻率分布f，C的一個(gè)前綴碼編碼方案對(duì)應(yīng)于一棵二叉樹T。字符c在樹T中的深度記為dT(c)，dT(c)也是字符c的前綴碼長。則平均碼長定義為：


使平均碼長達(dá)到最小的前綴碼編碼方案稱為C的最優(yōu)前綴碼。     
Huffman編碼的構(gòu)造方法：先合并最小頻率的2個(gè)字符對(duì)應(yīng)的子樹，計(jì)算合并后的子樹的頻率；重新排序各個(gè)子樹；對(duì)上述排序后的子樹序列進(jìn)行合并；重復(fù)上述過程，將全部結(jié)點(diǎn)合并成1棵完整的二叉樹；對(duì)二叉樹中的邊賦予0、1，得到各字符的變長編碼。


POJ3253一道就是利用這一思想的典型例題。題目大意是有把一塊無限長的木板鋸成幾塊給定長度的小木板，每次鋸都需要一定費(fèi)用，費(fèi)用就是當(dāng)前鋸的木板的長度。給定各個(gè)要求的小木板的長度以及小木板的個(gè)數(shù)，求最小的費(fèi)用。以要求3塊長度分別為5,8,5的木板為例：先從無限長的木板上鋸下長度為21的木板，花費(fèi)21；再從長度為21的木板上鋸下長度為5的木板，花費(fèi)5；再從長度為16的木板上鋸下長度為8的木板，花費(fèi)8；總花費(fèi)=21+5+8=34。利用Huffman思想，要使總費(fèi)用最小，那么每次只選取最小長度的兩塊木板相加，再把這些和累加到總費(fèi)用中即可。為了提高效率，使用優(yōu)先隊(duì)列優(yōu)化，并且還要注意使用long long int保存結(jié)果。
AC代碼：

  1. #include<queue>  
  2. #include<cstdio>  
  3. #include<iostream>  
  4. using namespace std;  
  5.   
  6. int main()  
  7. {  
  8.     long long int sum;  
  9.     int i,n,t,a,b;  
  10.     while(~scanf("%d",&n))  
  11.     {  
  12.         priority_queue<int,vector<int>,greater<int> >q;  
  13.         for(i=0;i<n;i++)  
  14.         {  
  15.             scanf("%d",&t);  
  16.             q.push(t);  
  17.         }  
  18.         sum=0;  
  19.         if(q.size()==1)  
  20.         {  
  21.             a=q.top();  
  22.             sum+=a;  
  23.             q.pop();  
  24.         }  
  25.         while(q.size()>1)  
  26.         {  
  27.             a=q.top();  
  28.             q.pop();  
  29.             b=q.top();  
  30.             q.pop();  
  31.             t=a+b;  
  32.             sum+=t;  
  33.             q.push(t);  
  34.         }  
  35.         printf("%lld\n",sum);  
  36.     }  
  37. }  

9.Dijkstra算法
Dijkstra算法是由E.W.Dijkstra于1959年提出，是目前公認(rèn)的最好的求解最短路徑的方法，使用的條件是圖中不能存在負(fù)邊。算法解決的是單個(gè)源點(diǎn)到其他頂點(diǎn)的最短路徑問題，其主要特點(diǎn)是每次迭代時(shí)選擇的下一個(gè)頂點(diǎn)是標(biāo)記點(diǎn)之外距離源點(diǎn)最近的頂點(diǎn)，簡單的說就是bfs+貪心算法的思想。

  1. #include<iostream>  
  2. #include<algorithm>   
  3. #define INF 1000   
  4. #define MAX_V 100  
  5. using namespace std;    
  6.   
  7. int main()  
  8. {  
  9.     int V,E;  
  10.     int i,j,m,n;  
  11.     int cost[MAX_V][MAX_V];  
  12.     int d[MAX_V];  
  13.     bool used[MAX_V];  
  14.     cin>>V>>E;  
  15.     fill(d,d+V+1,INF);  
  16.     fill(used,used+V,false);  
  17.     for(i=0;i<V;i++)  
  18.     {  
  19.         for(j=0;j<V;j++)  
  20.         {  
  21.             if(i==j) cost[i][j]=0;  
  22.             else cost[i][j]=INF;  
  23.         }  
  24.     }  
  25.     for(m=0;m<E;m++)  
  26.     {  
  27.         cin>>i>>j>>cost[i][j];  
  28.         cost[j][i]=cost[i][j];  
  29.     }  
  30.     cin>>n;  
  31.     d[n]=0;  
  32.     //源點(diǎn)   
  33.     while(true)  
  34.     {  
  35.         int v=V;  
  36.         for(m=0;m<V;m++)  
  37.         {     
  38.             if((!used[m])&&(d[m]<d[v])) v=m;  
  39.         }     
  40.         if(v==V) break;  
  41.         used[v]=true;  
  42.         for(m=0;m<V;m++)  
  43.         {  
  44.             d[m]=min(d[m],d[v]+cost[v][m]);   
  45.         }  
  46.     }  
  47.     for(i=0;i<V;i++)  
  48.     {  
  49.         cout<<"the shortest distance between "<<n<<" and "<<i<<" is "<<d[i]<<endl;  
  50.     }  
  51. }  
10.最小生成樹算法
設(shè)一個(gè)網(wǎng)絡(luò)表示為無向連通帶權(quán)圖G =(V, E) , E中每條邊(v,w)的權(quán)為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點(diǎn)的樹，則稱G’為G的生成樹。生成樹的代價(jià)是指生成樹上各邊權(quán)的總和，在G的所有生成樹中，耗費(fèi)最小的生成樹稱為G的最小生成樹。例如在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費(fèi)用，最小生成樹給出建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)方案。


構(gòu)造最小生成樹的Kruskal算法和Prim算法都利用了MST(最小生成樹)性質(zhì)：設(shè)頂點(diǎn)集U是V的真子集(可以任意選取)，如果(u,v)∈E為橫跨點(diǎn)集U和V—U的邊，即u∈U，v∈V- U，并且在所有這樣的邊中，(u,v)的權(quán)c[u][v]最小，則一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。



使用反證法可以很簡單的證明此性質(zhì)。假設(shè)對(duì)G的任意一個(gè)最小生成樹T，針對(duì)點(diǎn)集U和V—U，(u,v)∈E為橫跨這2個(gè)點(diǎn)集的最小權(quán)邊，T不包含該最小權(quán)邊<u, v>，但T包括節(jié)點(diǎn)u和v。將<u,v>添加到樹T中，樹T將變?yōu)楹芈返淖訄D，并且該回路上有一條不同于<u,v>的邊<u’,v’>,u’∈U,v’∈V-U。將<u’,v’>刪去，得到另一個(gè)樹T’，即樹T’是通過將T中的邊<u’,v’>替換為<u,v>得到的。由于這2條邊的耗費(fèi)滿足c[u][v]≤c[u’][v’]，故即T’耗費(fèi)≤T的耗費(fèi)，這與T是任意最小生成樹的假設(shè)相矛盾，從而得證。


Prim算法每一步都選擇連接U和V-U的權(quán)值最小的邊加入生成樹。


  1. #include<iostream>  
  2. #include<algorithm>  
  3. #define MAX_V 100  
  4. #define INF 1000   
  5. using namespace std;    
  6.   
  7. int main()  
  8. {  
  9.     int V,E;  
  10.     int i,j,m,n;  
  11.     int cost[MAX_V][MAX_V];  
  12.     int mincost[MAX_V];  
  13.     bool used[MAX_V];  
  14.     cin>>V>>E;  
  15.     fill(mincost,mincost+V+1,INF);  
  16.     fill(used,used+V,false);  
  17.     for(i=0;i<V;i++)  
  18.     {  
  19.         for(j=0;j<V;j++)  
  20.         {  
  21.             if(i==j) cost[i][j]=0;  
  22.             else cost[i][j]=INF;   
  23.         }  
  24.     }  
  25.     for(m=0;m<E;m++)  
  26.     {  
  27.         cin>>i>>j>>cost[i][j];  
  28.         cost[j][i]=cost[i][j];  
  29.     }  
  30.     mincost[0]=0;  
  31.     int res=0;  
  32.     while(true)  
  33.     {  
  34.         int v=V;  
  35.         for(m=0;m<V;m++)  
  36.         {     
  37.             if((!used[m])&&(mincost[m]<mincost[v]))  
  38.                 v=m;  
  39.         }     
  40.         if(v==V) break;  
  41.         used[v]=true;  
  42.         res+=mincost[v];  
  43.         for(m=0;m<V;m++)  
  44.         {  
  45.             mincost[m]=min(mincost[m],cost[v][m]);   
  46.         }  
  47.     }  
  48.     cout<<res<<endl;  
  49. }  
Kruskal算法每一步直接將權(quán)值最小的不成環(huán)的邊加入生成樹，我們借助并查集這一數(shù)據(jù)結(jié)構(gòu)可以完美實(shí)現(xiàn)它。


  1. #include<iostream>  
  2. #include<algorithm>   
  3. #define MAX_E 100   
  4. using namespace std;    
  5. struct edge  
  6. {  
  7.     int u,v,cost;     
  8. };  
  9. int pre[MAX_E];  
  10. edge es[MAX_E];  
  11. int find(int x);  
  12. void initvalue(int x);  
  13. bool same(int x,int y);  
  14. void unite(int x,int y);  
  15. bool comp(const edge& e1,const edge& e2);  
  16.   
  17. int main()  
  18. {  
  19.     int V,E;  
  20.     int i,j,m,n;   
  21.     cin>>V>>E;  
  22.     initvalue(V);  
  23.     for(i=0;i<E;i++) cin>>es[i].u>>es[i].v>>es[i].cost;          
  24.     sort(es,es+E,comp);  
  25.     int res=0;  
  26.     for(i=0;i<E;i++)  
  27.     {  
  28.         edge e=es[i];  
  29.         if(!same(e.u,e.v))  
  30.         {  
  31.             unite(e.u,e.v);  
  32.             res+=e.cost;  
  33.         }  
  34.     }  
  35.     cout<<res<<endl;      
  36. }  
  37.   
  38. bool comp(const edge& e1,const edge& e2)  
  39. {  
  40.     return e1.cost<e2.cost;    
  41. }  
  42.   
  43. void initvalue(int x)  
  44. {  
  45.     for(int i=0;i<x;i++) pre[i]=i;  
  46. }  
  47.   
  48. int find(int x)  
  49. {  
  50.     int r=x;  
  51.     while(pre[r]!=r) r=pre[r];  
  52.     int i=x,j;  
  53.     while(pre[i]!=r)  
  54.     {  
  55.         j=pre[i];  
  56.         pre[i]=r;  
  57.         i=j;  
  58.     }  
  59.     return r;  
  60. }  
  61.   
  62. bool same(int x,int y)  
  63. {  
  64.     if(find(x)==find(y)) return true;  
  65.     else return false;    
  66. }  
  67.   
  68. void unite(int x,int y)  
  69. {  
  70.     int fx=find(x);  
  71.     int fy=find(y);  
  72.     if(fx!=fy) pre[fx]=fy;    
  73. }  
關(guān)于貪心算法的基礎(chǔ)知識(shí)就簡要介紹到這里，希望能作為大家繼續(xù)深入學(xué)習(xí)的基礎(chǔ)。

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類似文章 更多