《算法導(dǎo)論》讀書筆記之第16章 貪心算法—活動選擇問題

　　前言：貪心算法也是用來解決最優(yōu)化問題，將一個(gè)問題分成子問題，在現(xiàn)在子問題最優(yōu)解的時(shí)，選擇當(dāng)前看起來是最優(yōu)的解，期望通過所做的局部最優(yōu)選擇來產(chǎn)生一個(gè)全局最優(yōu)解。書中先從活動選擇問題來引入貪心算法，分別采用動態(tài)規(guī)劃方法和貪心算法進(jìn)行分析。本篇筆記給出活動選擇問題的詳細(xì)分析過程，并給出詳細(xì)的實(shí)現(xiàn)代碼進(jìn)行測試驗(yàn)證。關(guān)于貪心算法的詳細(xì)分析過程，下次在討論。

1、活動選擇問題描述

　　? 有一個(gè)需要使用每個(gè)資源的n個(gè)活動組成的集合S=?{a₁，a₂，···，a_n?}，資源每次只能由一個(gè)活動使用。每個(gè)活動a_i都有一個(gè)開始時(shí)間s_i和結(jié)束時(shí)間f_i，且?0≤s_i<f_i<∞ 。一旦被選擇后，活動a_i就占據(jù)半開時(shí)間區(qū)間[s_i,f_i)。如果[s_i,f_i]和[s_j,f_j]互不重疊，則稱a_i和a_j兩個(gè)活動是兼容的。該問題就是要找出一個(gè)由互相兼容的活動組成的最大子集。例如下圖所示的活動集合S，其中各項(xiàng)活動按照結(jié)束時(shí)間單調(diào)遞增排序。

從圖中可以看出S中共有11個(gè)活動，最大的相互兼容的活動子集為:{a₁，a₄，a₈，a11，}和{a₂，a₄，a₉，a₁₁}。

2、動態(tài)規(guī)劃解決過程

（1）活動選擇問題的最優(yōu)子結(jié)構(gòu)

定義子問題解空間S_ij是S的子集，其中的每個(gè)獲得都是互相兼容的。即每個(gè)活動都是在a_i結(jié)束之后開始，且在a_j開始之前結(jié)束。

為了方便討論和后面的計(jì)算，添加兩個(gè)虛構(gòu)活動a₀和a_n+1，其中f₀=0，s_n+1=∞。

結(jié)論：當(dāng)i≥j時(shí)，S_ij為空集。

如果活動按照結(jié)束時(shí)間單調(diào)遞增排序，子問題空間被用來從S_ij中選擇最大兼容活動子集，其中0≤i＜j≤n+1，所以其他的S_ij都是空集。

最優(yōu)子結(jié)構(gòu)為：假設(shè)S_ij的最優(yōu)解A_ij包含活動a_k，則對S_ik的解A_ik和S_kj的解A_kj必定是最優(yōu)的。

通過一個(gè)活動a_k將問題分成兩個(gè)子問題，下面的公式可以計(jì)算出S_ij的解A_ij。

（2）一個(gè)遞歸解

　　設(shè)c[i][j]為S_ij中最大兼容子集中的活動數(shù)目，當(dāng)S_ij為空集時(shí)，c[i][j]=0；當(dāng)S_ij非空時(shí)，若a_k在S_ij的最大兼容子集中被使用，則則問題S_ik和S_kj的最大兼容子集也被使用，故可得到c[i][j] = c[i][k]+c[k][j]+1。

當(dāng)i≥j時(shí)，S_ij必定為空集，否則S_ij則需要根據(jù)上面提供的公式進(jìn)行計(jì)算，如果找到一個(gè)a_k，則S_ij非空（此時(shí)滿足f_i≤s_k且f_k≤s_j），找不到這樣的a_k，則S_ij為空集。

c[i][j]的完整計(jì)算公式如下所示：

?

（3）最優(yōu)解計(jì)算過程

　　根據(jù)遞歸公式，采用自底向下的策略進(jìn)行計(jì)算c[i][j]，引入復(fù)雜數(shù)組ret[n][n]保存中間劃分的k值。程序?qū)崿F(xiàn)如下所示：

1 void dynamic_activity_selector(int *s,int *f,int c[N+1][N+1],int ret[N+1][N+1]) 2 { 3 int i,j,k; 4 int temp; 5 //當(dāng)i>=j時(shí)候，子問題的解為空，即c[i][j]=0 6 for(j=1;j<=N;j++) 7 for(i=j;i<=N;i++) 8 c[i][j] = 0; 9 //當(dāng)i<j時(shí)，需要尋找子問題的最優(yōu)解，找到一個(gè)k使得將問題分成兩部分 10 for(j=2;j<=N;j++) 11 for(i=1;i<j;i++) 12 { 13 //尋找k，將問題分成兩個(gè)子問題c[i][k]、c[k][j] 14 for(k=i+1;k<j;k++) 15 if(s[k] >= f[i] && f[k] <= s[j]) //判斷k活動是否滿足兼容性 16 { 17 temp = c[i][k]+c[k][j]+1; 18 if(c[i][j] < temp) 19 { 20 c[i][j] =temp; 21 ret[i][j] = k; 22 } 23 } 24 } 25 }

?（4）構(gòu)造一個(gè)最優(yōu)解集合

　　根據(jù)第三保存的ret中的k值，遞歸調(diào)用輸出獲得集合。采用動態(tài)規(guī)劃方法解決上面的例子，完整程序如下所示：

?

1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define N 11 5 6 void dynamic_activity_selector(int *s,int *f,int c[N+1][N+1],int ret[N+1][N+1]); 7 void trace_route(int ret[N+1][N+1],int i,int j); 8 9 int main() 10 { 11 int s[N+1] = {-1,1,3,0,5,3,5,6,8,8,2,12}; 12 int f[N+1] = {-1,4,5,6,7,8,9,10,11,12,13,14}; 13 int c[N+1][N+1]={0}; 14 int ret[N+1][N+1]={0}; 15 int i,j; 16 dynamic_activity_selector(s,f,c,ret); 17 printf("c[i][j]的值如下所示：\n"); 18 for(i=1;i<=N;i++) 19 { 20 for(j=1;j<=N;j++) 21 printf("%d ",c[i][j]); 22 printf("\n"); 23 } 24 //包括第一個(gè)和最后一個(gè)元素 25 printf("最大子集的個(gè)數(shù)為: %d\n",c[1][N]+2); 26 printf("ret[i][j]的值如下所示：\n"); 27 for(i=1;i<=N;i++) 28 { 29 for(j=1;j<=N;j++) 30 printf("%d ",ret[i][j]); 31 printf("\n"); 32 } 33 printf("最大子集為:{ a1 "); 34 trace_route(ret,1,N); 35 printf("a%d}\n",N); 36 system("pause"); 37 return 0; 38 } 39 40 void dynamic_activity_selector(int *s,int *f,int c[N+1][N+1],int ret[N+1][N+1]) 41 { 42 int i,j,k; 43 int temp; 44 //當(dāng)i>=j時(shí)候，子問題的解為空，即c[i][j]=0 45 for(j=1;j<=N;j++) 46 for(i=j;i<=N;i++) 47 c[i][j] = 0; 48 //當(dāng)i>j時(shí)，需要尋找子問題的最優(yōu)解，找到一個(gè)k使得將問題分成兩部分 49 for(j=2;j<=N;j++) 50 for(i=1;i<j;i++) 51 { 52 //尋找k，將問題分成兩個(gè)子問題c[i][k]、c[k][j] 53 for(k=i+1;k<j;k++) 54 if(s[k] >= f[i] && f[k] <= s[j]) //判斷k活動是否滿足兼容性 55 { 56 temp = c[i][k]+c[k][j]+1; 57 if(c[i][j] < temp) 58 { 59 c[i][j] =temp; 60 ret[i][j] = k; 61 } 62 } 63 } 64 } 65 66 void trace_route(int ret[N+1][N+1],int i,int j) 67 { 68 if(i<j) 69 { 70 trace_route(ret,i,ret[i][j]); 71 if(ret[i][j] != 0 ) 72 printf("a%d ", ret[i][j]); 73 } 74 }

?

程序測試結(jié)果如下所示：

3、貪心算法解決過程

針對活動選擇問題，認(rèn)真分析可以得出以下定理：對于任意非空子問題S_ij，設(shè)a_m是S_ij中具有最早結(jié)束時(shí)間的活動，那么：

（1）活動a_m在S_ij中的某最大兼容活動子集中被使用。

（2）子問題S_im為空，所以選擇am將使子問題S_mj為唯一可能非空的子問題。

有這個(gè)定理，就簡化了問題，使得最優(yōu)解中只使用一個(gè)子問題，在解決子問題S_ij時(shí)，在S_ij中選擇最早結(jié)束時(shí)間的那個(gè)活動。

貪心算法自頂向下地解決每個(gè)問題，解決子問題S_ij，先找到S_ij中最早結(jié)束的活動a_m，然后將a_m添加到最優(yōu)解活動集合中，再來解決子問題S_mj。

基于這種思想可以采用遞歸和迭代進(jìn)行實(shí)現(xiàn)。遞歸實(shí)現(xiàn)過程如下所示：

1 void recursive_activity_selector(int *s,int* f,int i,int n,int *ret) 2 { 3 int *ptmp = ret; 4 int m = i+1; 5 //在S_in中尋找第一個(gè)結(jié)束的活動 6 while(m<=n && s[m] < f[i]) 7 m = m+1; 8 if(m<=n) 9 { 10 *ptmp++ = m; //添加到結(jié)果中 11 recursive_activity_selector(s,f,m,n,ptmp); 12 } 13 }

迭代實(shí)現(xiàn)過程如下：

1 void greedy_activity_selector(int *s,int *f,int *ret) 2 { 3 int i,m; 4 *ret++ = 1; 5 i =1; 6 for(m=2;m<=N;m++) 7 if(s[m] >= f[i]) 8 { 9 *ret++ = m; 10 i=m; 11 } 12 }

采用貪心算法實(shí)現(xiàn)上面的例子，完整代碼如下所示：

1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define N 11 5 6 void recursive_activity_selector(int *s,int* f,int i,int n,int *ret); 7 8 void greedy_activity_selector(int *s,int *f,int *ret); 9 10 int main() 11 { 12 int s[N+1] = {-1,1,3,0,5,3,5,6,8,8,2,12}; 13 int f[N+1] = {-1,4,5,6,7,8,9,10,11,12,13,14}; 14 int c[N+1][N+1]={0}; 15 int ret[N]={0}; 16 int i,j; 17 //recursive_activity_selector(s,f,0,N,ret); 18 greedy_activity_selector(s,f,ret); 19 printf("最大子集為:{ "); 20 for(i=0;i<N;i++) 21 { 22 if(ret[i] != 0) 23 printf("a%d ",ret[i]); 24 } 25 printf(" }\n"); 26 system("pause"); 27 return 0; 28 } 29 30 void recursive_activity_selector(int *s,int* f,int i,int n,int *ret) 31 { 32 int *ptmp = ret; 33 int m = i+1; 34 //在i和n中尋找第一個(gè)結(jié)束的活動 35 while(m<=n && s[m] < f[i]) 36 m = m+1; 37 if(m<=n) 38 { 39 *ptmp++ = m; //添加到結(jié)果中 40 recursive_activity_selector(s,f,m,n,ptmp); 41 } 42 } 43 44 void greedy_activity_selector(int *s,int *f,int *ret) 45 { 46 int i,m; 47 *ret++ = 1; 48 i =1; 49 for(m=2;m<=N;m++) 50 if(s[m] >= f[i]) 51 { 52 *ret++ = m; 53 i=m; 54 } 55 }

程序測試結(jié)果如下所示：

?4、總結(jié)

　　活動選擇問題分別采用動態(tài)規(guī)劃和貪心算法進(jìn)行分析并實(shí)現(xiàn)。動態(tài)規(guī)劃的運(yùn)行時(shí)間為O(n^3)，貪心算法的運(yùn)行時(shí)間為O(n)。動態(tài)規(guī)劃解決問題時(shí)全局最優(yōu)解中一定包含某個(gè)局部最優(yōu)解，但不一定包含前一個(gè)局部最優(yōu)解，因此需要記錄之前的所有最優(yōu)解。貪心算法的主要思想就是對問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇，產(chǎn)生一個(gè)局部最優(yōu)解。

?

?

?

《算法導(dǎo)論》讀書筆記之第16章 0-1背包問題—?jiǎng)討B(tài)規(guī)劃求解

1、前言

　　前段時(shí)間忙著搞畢業(yè)論文，看書效率不高，導(dǎo)致博客一個(gè)多月沒有更新了。前段時(shí)間真是有些墮落啊，混日子的感覺，很少不爽。今天開始繼續(xù)看算法導(dǎo)論。今天繼續(xù)學(xué)習(xí)動態(tài)規(guī)劃和貪心算法。首先簡單的介紹一下動態(tài)規(guī)劃與貪心算法的各自特點(diǎn)及其區(qū)別。然后針對0-1背包問題進(jìn)行討論。最后給出一個(gè)簡單的測試?yán)?#xff0c;聯(lián)系動態(tài)規(guī)劃實(shí)現(xiàn)0-1背包問題。

2、動態(tài)規(guī)劃與貪心算法

　　關(guān)于動態(tài)規(guī)劃的總結(jié)請參考http://www.cnblogs.com/Anker/archive/2013/03/15/2961725.html。這里重點(diǎn)介紹一下貪心算法的過程。貪心算法是通過一系列的選擇來給出某一個(gè)問題的最優(yōu)解，每次選擇一個(gè)當(dāng)前（看起來是）最佳的選擇。貪心算法解決問題的步驟為：

（1）決定問題的最優(yōu)子結(jié)構(gòu)

（2）設(shè)計(jì)出一個(gè)遞歸解

（3）證明在遞歸的任一階段，最優(yōu)選擇之一總是貪心選擇。保證貪心選擇總是安全的。

（4）證明通過貪心選擇，所有子問題（除一個(gè)意外）都為空。

（5）設(shè)計(jì)出一個(gè)實(shí)現(xiàn)貪心策略的遞歸算法。

（6）將遞歸算法轉(zhuǎn)換成迭代算法。

　　什么時(shí)候才能使用貪心算法的呢？書中給出了貪心算法的兩個(gè)性質(zhì)，只有最優(yōu)化問題滿足這些性質(zhì)，就可采用貪心算法解決問題。

（1）貪心選擇性質(zhì)：一個(gè)全局最優(yōu)解可以通過舉辦最優(yōu)解（貪心）選擇來達(dá)到。即：當(dāng)考慮做選擇時(shí)，只考慮對當(dāng)前問題最佳的選擇而不考慮子問題的結(jié)果。而在動態(tài)規(guī)劃中，每一步都要做出選擇，這些選擇依賴于子問題的解。動態(tài)規(guī)劃一般是自底向上，從小問題到大問題。貪心算法通常是自上而下，一個(gè)一個(gè)地做貪心選擇，不斷地將給定的問題實(shí)例規(guī)約為更小的子問題。

（2）最優(yōu)子結(jié)構(gòu)：問題的一個(gè)最優(yōu)解包含了其子問題的最優(yōu)解。

動態(tài)規(guī)劃與貪心的區(qū)別：

貪心算法：?
（1）貪心算法中，作出的每步貪心決策都無法改變，因?yàn)樨澬牟呗允怯缮弦徊降淖顑?yōu)解推導(dǎo)下一步的最優(yōu)解，而上一部之前的最優(yōu)解則不作保留；?
（2）由（1）中的介紹，可以知道貪心法正確的條件是：每一步的最優(yōu)解一定包含上一步的最優(yōu)解。?

動態(tài)規(guī)劃算法：?
（1）全局最優(yōu)解中一定包含某個(gè)局部最優(yōu)解，但不一定包含前一個(gè)局部最優(yōu)解，因此需要記錄之前的所有最優(yōu)解 ；
（2）動態(tài)規(guī)劃的關(guān)鍵是狀態(tài)轉(zhuǎn)移方程，即如何由以求出的局部最優(yōu)解來推導(dǎo)全局最優(yōu)解 ；
（3）邊界條件：即最簡單的，可以直接得出的局部最優(yōu)解。

3、0-1背包問題描述

　　有一個(gè)竊賊在偷竊一家商店時(shí)發(fā)現(xiàn)有n件物品，第i件物品價(jià)值為v_i元，重量為w_i，假設(shè)v_i和w_i都為整數(shù)。他希望帶走的東西越值錢越好，但他的背包中之多只能裝下W磅的東西，W為一整數(shù)。他應(yīng)該帶走哪幾樣?xùn)|西？

0-1背包問題中：每件物品或被帶走，或被留下，（需要做出0-1選擇）。小偷不能只帶走某個(gè)物品的一部分或帶走兩次以上同一個(gè)物品。

部分背包問題：小偷可以只帶走某個(gè)物品的一部分，不必做出0-1選擇。

4、0-1背包問題解決方法

　　0-1背包問題是個(gè)典型舉辦子結(jié)構(gòu)的問題，但是只能采用動態(tài)規(guī)劃來解決，而不能采用貪心算法。因?yàn)樵?-1背包問題中，在選擇是否要把一個(gè)物品加到背包中，必須把該物品加進(jìn)去的子問題的解與不取該物品的子問題的解進(jìn)行比較。這種方式形成的問題導(dǎo)致了許多重疊子問題，滿足動態(tài)規(guī)劃的特征。動態(tài)規(guī)劃解決0-1背包問題步驟如下：

0-1背包問題子結(jié)構(gòu)：選擇一個(gè)給定物品i，則需要比較選擇i的形成的子問題的最優(yōu)解與不選擇i的子問題的最優(yōu)解。分成兩個(gè)子問題，進(jìn)行選擇比較，選擇最優(yōu)的。

0-1背包問題遞歸過程：設(shè)有n個(gè)物品，背包的重量為w，C[i][w]為最優(yōu)解。即：

課后習(xí)題給出了偽代碼：

5、編程實(shí)現(xiàn)

　　現(xiàn)在給定3個(gè)物品，背包的容量為50磅。物品1重10磅，價(jià)值為60，物品2重20磅，價(jià)值為100，物品3重30磅，價(jià)值為120。采用動態(tài)規(guī)劃可以知道最優(yōu)解為220，選擇物品2和3。采用C++語言實(shí)現(xiàn)如下：

1 #include <iostream> 2 using namespace std; 3 4 //物品數(shù)據(jù)結(jié)構(gòu) 5 typedef struct commodity 6 { 7 int value; //價(jià)值 8 int weight; //重量 9 }commodity; 10 11 const int N = 3; //物品個(gè)數(shù) 12 const int W = 50; //背包的容量 13 14 //初始物品信息 15 commodity goods[N+1]={{0,0},{60,10},{100,20},{120,30}}; 16 int select[N+1][W+1]; 17 18 int max_value(); 19 20 int main() 21 { 22 int maxvalue = max_value(); 23 cout<<"The max value is: "; 24 cout<<maxvalue<<endl; 25 int remainspace = W; 26 //輸出所選擇的物品列表： 27 for(int i=N; i>=1; i--) 28 { 29 if (remainspace >= goods[i].weight) 30 { 31 if ((select[i][remainspace]-select[i-1][remainspace-goods[i].weight]==goods[i].value)) 32 { 33 cout << "item " << i << " is selected!" << endl; 34 remainspace = remainspace - goods[i].weight;//如果第i個(gè)物品被選擇，那么背包剩余容量將減去第i個(gè)物品的重量 ; 35 } 36 } 37 } 38 return 0; 39 } 40 int max_value() 41 { 42 //初始沒有物品時(shí)候，背包的價(jià)值為0 43 for(int w=1;w<=W;++w) 44 select[0][w] = 0; 45 for(int i=1;i<=N;++i) 46 { 47 select[i][0] = 0; //背包容量為0時(shí)，最大價(jià)值為0 48 for(int w=1;w<=W;++w) 49 { 50 if(goods[i].weight <= w) //當(dāng)前物品i的重量小于等于w，進(jìn)行選擇 51 { 52 if( (goods[i].value + select[i-1][w-goods[i].weight]) > select[i-1][w]) 53 select[i][w] = goods[i].value + select[i-1][w-goods[i].weight]; 54 else 55 select[i][w] = select[i-1][w]; 56 } 57 else //當(dāng)前物品i的重量大于w，不選擇 58 select[i][w] = select[i-1][w]; 59 } 60 } 61 return select[N][W]; //最終求得最大值 62 }

程序測試結(jié)果如下：

總結(jié)

以上是生活随笔為你收集整理的《算法导论》读书笔记(七)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。