這篇文章主要用來記錄我對(duì)《算法導(dǎo)論》 貪心算法一章中的“活動(dòng)選擇問題”的動(dòng)態(tài)規(guī)劃求解和貪心算法求解 的思路和理解。

主要涉及到以下幾個(gè)方面的內(nèi)容：

①什么是活動(dòng)選擇問題---粗略提下，詳細(xì)請(qǐng)參考《算法導(dǎo)論》

②活動(dòng)選擇問題的DP(Dynamic programming)求解--DP求解問題的思路

③活動(dòng)選擇問題的貪心算法求解

④為什么這個(gè)問題可以用貪心算法求解？

⑤動(dòng)態(tài)規(guī)劃與貪心算法的一些區(qū)別與聯(lián)系

⑥活動(dòng)選擇問題的DP求解的JAVA語言實(shí)現(xiàn)以及時(shí)間復(fù)雜度分析

⑦活動(dòng)選擇問題的Greedy算法JAVA實(shí)現(xiàn)和時(shí)間復(fù)雜度分析

⑧一些有用的參考資料

?

①活動(dòng)選擇問題

給定N個(gè)活動(dòng)，以及它們的開始時(shí)間和結(jié)束時(shí)間，求N個(gè)活動(dòng)中，最大兼容的活動(dòng)個(gè)數(shù)。比如：

活動(dòng) i:???????????? 1???? 2???? 3????? 4.....

開始時(shí)間 si:???? 1????? 3???? 0????? 5....

結(jié)束時(shí)間 fi:???? 4????? 5???? 6?????? 7.....

活動(dòng)1的開始時(shí)間s(1)=1，結(jié)束時(shí)間f(1)=4，它與活動(dòng)2是不兼容的。因?yàn)?#xff0c;活動(dòng)1還沒有結(jié)束，活動(dòng)2就開始了(s(2) < f(1))。

活動(dòng)2 與 活動(dòng)4 是兼容的。因?yàn)?#xff0c;活動(dòng)2的進(jìn)行區(qū)間是[3,5) 而活動(dòng)4的進(jìn)行區(qū)間是[5,7)

目標(biāo)是：在N個(gè)活動(dòng)中，找出最大兼容的活動(dòng)個(gè)數(shù)。

?

②活動(dòng)選擇問題的DP(Dynamic programming)求解

1）建模

活動(dòng) i 用 a(i)來表示，開始時(shí)間用 s(i)表示，結(jié)束時(shí)間用 f(i)表示，所有活動(dòng)的集合為S

定義一個(gè)合適的子問題空間，設(shè) S(i,j) 是與 a(i) 和 a(j)兼容的活動(dòng)集合。S(i,j)={a(k), a(k) belongs to S: f(i)<=s(k)<f(k)<=s(j)}

2）問題一般化(不是很理解)

這里第一個(gè)活動(dòng)和最后一個(gè)活動(dòng)有點(diǎn)特殊。為了完整表示問題，構(gòu)造兩個(gè)虛擬的活動(dòng): a(0) 和 a(n+1)

其中,s(0)=f(0)=0，s(n+1)=f(n+1)=Integer.MAX_VALUE

于是，S=S(0,n+1)，從N個(gè)活動(dòng)中找出最大兼容的活動(dòng)，就轉(zhuǎn)化成了求解 S(0,n+1)集合中包含的最多元素個(gè)數(shù)

3）子問題分析

假設(shè)所有的活動(dòng)都按結(jié)束時(shí)間遞增排序。子問題空間就是 從S(i,j)中選擇最大兼容活動(dòng)子集，即max{S(i,j)}

max{S(i,j)}表示與 a(i) a(j) 兼容的最大活動(dòng)集合。稱為為S(i,j)的解

假設(shè) a(k)是 S(i,j)的解包含的一個(gè)活動(dòng)。S(i,j)就分解為 max{S(i,k)} + max{S(k,j)}+1

從這里可以看到，將原問題分解成了兩個(gè)子問題。原問題就是：求解與活動(dòng) a(i) a(j) 兼容的最大活動(dòng)個(gè)數(shù)，即max{S(i,j)}

而子問題則是：max{S(i,k)}? 和? max{S(k,j)}

設(shè)A(i,j)就是S(i,j)的解。那么，A(i,j)=A(i,k) U A(k,j) U {a(k)}

A(0,n+1)就是我們所求的整個(gè)問題的最優(yōu)解。

4）子問題的 選擇個(gè)數(shù) 分析

設(shè)c[i,j]為S(i,j)中最大兼容子集中的活動(dòng)數(shù)，S(i,j)為空集時(shí)，c[i,j]=0，這是顯而易見的。因?yàn)镾(i,j)中都沒有活動(dòng)嘛，更別談什么兼容活動(dòng)了呀。

若 i>=j，c[i,j]=0。這個(gè)也很好理解，因?yàn)樗环铣ＷR(shí)。因?yàn)?#xff0c;我們假設(shè)活動(dòng)是以結(jié)束時(shí)間來遞增排序的，在S(i,j)中，是f(i)<s(j)的。那 i 就不會(huì)大于 j

畢竟一個(gè)活動(dòng)它不可能 即在 某個(gè)活動(dòng)之前結(jié)束，又在該活動(dòng)之后開始。哈哈。。。。。

前面提到 ：假設(shè) a(k)是 S(i,j)的解包含的一個(gè)活動(dòng)。S(i,j)就分解為 max{S(i,k)} + max{S(k,j)}+1

這意味著，求S(i,j)的最優(yōu)解，就需要知道 S(i,k) 和 S(k,j) 的最優(yōu)解。那關(guān)鍵是怎么知道 S(i,k) 和 S(k,j) 的最優(yōu)解呢？

答案是：一個(gè) 一個(gè) 地嘗試。k 的取值范圍是 (i,j)，遍歷(i,j)內(nèi)所有的值，計(jì)算 S(i,k) 和 S(k,j)的解。就可以找到S(i,j)的最優(yōu)解了。

?因此，當(dāng)S(i,j)不為空時(shí)，c[i,j] = max{c[i,k] + c[k,j] + 1}? 其中, k belongs to (i,j)? a(k) belongs to S(i,j)

下面，就是DP中的狀態(tài)轉(zhuǎn)移方程(遞歸表達(dá)式)，根據(jù)它，就可以寫代碼實(shí)現(xiàn)了。

從上面分析可以看出：原問題分解成了兩個(gè)子問題，要解決原問題，一共有 j-i+1中選擇，然后一 一遍歷求出所有的選擇。這就是動(dòng)態(tài)規(guī)劃的特點(diǎn)，先分析最優(yōu)子問題，然后再做選擇。

?

③活動(dòng)選擇問題的貪心算法求解

所謂貪心算法，就是每次在做選擇時(shí)，總是先選擇具有相同特征的那個(gè)解，即“貪心”解。在這里，“貪心”的那個(gè)解則是： 結(jié)束時(shí)間最早的那個(gè)活動(dòng)

具體步驟是怎樣的呢？

第一步：先對(duì)活動(dòng)按照結(jié)束時(shí)間進(jìn)行排序。因?yàn)槲覀兛偸莾?yōu)先選擇結(jié)束時(shí)間最早的活動(dòng)的嘛。排序之后，方便選擇嘛。。。

第二步：按照貪心原則 選中一個(gè)活動(dòng)，然后排除 所有與該活動(dòng) 有沖突的活動(dòng)。

第三步：繼續(xù)選擇下一個(gè)活動(dòng)。其實(shí)，第二步與第三步合起來就是：每次都選結(jié)束時(shí)間最早的活動(dòng)，但是后面選擇的活動(dòng)不能與前面選擇的活動(dòng)有沖突。

從這里可以看出，貪心算法是在原問題上先做貪心選擇，然后得到一個(gè)子問題，再求解子問題。（求解子問題的過程，就是一個(gè)不斷貪心選擇的過程）

?

④為什么這個(gè)問題可以用貪心算法求解？

看了貪心算法之后，就會(huì)有疑問？憑什么這樣選就能得到最優(yōu)解啊？或者說，這樣做到底對(duì)不對(duì)？

別急嘛，我們可以用數(shù)學(xué)來證明這樣做是正確的。而且從這個(gè)證明過程中，可以窺出動(dòng)態(tài)規(guī)劃與貪心算法的區(qū)別。

對(duì)于活動(dòng)選擇問題而言：當(dāng)可用貪心算法解時(shí)，貪心的效率要比動(dòng)態(tài)規(guī)劃高。為什么要高呢？后面再詳細(xì)講。

這個(gè)證明具體可參考《算法導(dǎo)論》上的證明。它的大致證明過程就是：

當(dāng)選擇了貪心解時(shí)(結(jié)束時(shí)間最小的活動(dòng))，也是將原問題劃分成了兩個(gè)子問題，但是其中一個(gè)子問題是空的，而我們只需要考慮另一個(gè)非空的子問題就可以了。

具體而言就是：假設(shè) a(m) 是 S(i,j)中具有最早結(jié)束時(shí)間的那個(gè)活動(dòng)，那按照我們的貪心選擇，我們肯定會(huì)選擇a(m)的嘛。選了a(m)之后，就將問題分解成了兩個(gè)子問題:S(i,m) 和 S(m,j)。前面提到，活動(dòng)是按結(jié)束時(shí)間排序了的，而現(xiàn)在a(m)又是最早結(jié)束的活動(dòng)，因?yàn)?#xff0c;S(i,m)就是個(gè)空集，而我們只需要考慮S(m,j)

但是，這里有個(gè)重大的疑問還未解決---憑什么說 a(m) 就是 S(i,j)的最優(yōu)解中的活動(dòng)呢？或者說憑什么 活動(dòng)m 就是最大兼容活動(dòng)集合中的活動(dòng)？

這里就用到經(jīng)常用來證明貪心算法正確性的一個(gè)技巧---剪枝。關(guān)于這個(gè)技巧，可參考一篇博文：漫談算法（一）如何證明貪心算法是最優(yōu)

對(duì)于活動(dòng)選擇問題，咱就來簡要證明下吧。。。其實(shí)還是《算法導(dǎo)論》中講的證明，只不過我又復(fù)述一遍罷了。

慢著，我們要證明的是啥？再說一遍：憑什么說 a(m) 就是 S(i,j)的最優(yōu)解中的活動(dòng)呢？，我們證明的就是：a(m)是S(i,j)的最優(yōu)解中的元素，即a(m)是S(i,j)最大兼容活動(dòng)子集中的活動(dòng)。

設(shè)A(i,j)是S(i,j)的最大兼容活動(dòng)子集---也就是說，在所有與 活動(dòng)a(i) 和 活動(dòng)a(j) 相兼容的活動(dòng)中，A(i,j)含有的活動(dòng)個(gè)數(shù)最多。

將A(i,j)中的活動(dòng)按結(jié)束時(shí)間遞增排序。設(shè)a(k)是A(i,j)中的第一個(gè)活動(dòng)。若a(k)=a(m)，那沒話說了。a(m)就是a(k)嘛，那a(m)肯定在A(i,j)中噻

若a(k) != a(m)，這說明A(i,j)中的第一個(gè)元素(活動(dòng))不是a(m)。那我們可以運(yùn)用剪枝思想，剪掉A(i,j)中的第一個(gè)活動(dòng)a(k)，再把活動(dòng)a(m)貼到A(i,j)里面去。

這樣，A(i,j)中的活動(dòng)個(gè)數(shù)還是沒有變化---少了個(gè)a(k)，加了個(gè)a(m)啊

那么，可能你就會(huì)問了，憑什么能把 a(m)貼到 A(i,j)里面去啊？？？？？我們可以這樣想想：a(k)是A(i,j)中的第一個(gè)活動(dòng)，那為什么a(k)可以在A(i,j)中呢？

廢話！上面帶下劃線且加粗的的都說了假設(shè) a(k)是A(i,j)中的第一個(gè)活動(dòng)了啊！！

其實(shí)，這不是本質(zhì) ，本質(zhì)就是：a(k)是與 a(i) 和 a(j)兼容的活動(dòng)啊，而且沒有和A(i,j)中的其他活動(dòng)沖突啊！因?yàn)?#xff0c;S(i,j)的解 就是求與 a(i) 和 a(j)兼容的一組活動(dòng)啊，而A(i,j)就是這樣的一組活動(dòng)且它是最大的(活動(dòng)個(gè)數(shù)最多)，能夠放在A(i,j)中的活動(dòng)，它一定是與a(i) 和 a(j) 兼容的。

那么，再回到a(m)，a(m)同樣也具有 ”本質(zhì)“ 中提到的兩個(gè)性質(zhì)：?a(m)是與a(i) 和 a(j) 兼容的活動(dòng)? ?a(m)沒有與A(i,j)中其他活動(dòng)沖突。

下面來說明下為什么 a(m)沒有與A(i,j)中其他活動(dòng)沖突？因?yàn)閍(k)是沒有與A(i,j)中的其他活動(dòng)沖突的，而a(m)又是S(i,j)中結(jié)束時(shí)間最早的活動(dòng)

故：，完成時(shí)間：f(m)<f(k) ，a(m)都比a(k)更早完成，而a(k)都沒有與A(i,j)中的其他活動(dòng)沖突，那a(m)就更不可能與A(i,j)中的其他活動(dòng)沖突了。

整個(gè)思路就是：在證明中先考察一個(gè)全局最優(yōu)解，然后證明可以對(duì)該解加以修改(比如運(yùn)用“剪枝”技巧)，使其采用貪心選擇(將貪心的那個(gè)選擇貼上去)，這個(gè)選擇將原問題變成一個(gè)相似的、但更小的問題。

終于完成了證明。好累。

?

⑤動(dòng)態(tài)規(guī)劃與貪心算法的一些區(qū)別與聯(lián)系

這里只針對(duì)活動(dòng)選擇問題作一下比較。其他的我也不懂。

a)動(dòng)態(tài)規(guī)劃是先分析子問題，再做選擇。而貪心算法則是先做貪心選擇，做完選擇后，生成了子問題，然后再去求解子問題。

b)從 a) 中可以看出，動(dòng)態(tài)規(guī)劃是自底向上解決問題，而貪心算法則是自頂向下解決問題。

c)動(dòng)態(tài)規(guī)劃每一步可能會(huì)產(chǎn)生多個(gè)子問題，而貪心算法每一步只會(huì)產(chǎn)生一個(gè)子問題。（比如這里的貪心算法產(chǎn)生了“二個(gè)”子問題，但是其中一個(gè)是空的。）

?

⑥活動(dòng)選擇問題的DP求解的JAVA語言實(shí)現(xiàn)以及時(shí)間復(fù)雜度分析

1 /** 2 * //算法導(dǎo)論中活動(dòng)選擇問題動(dòng)態(tài)規(guī)劃求解 3 * @param s 活動(dòng)的開始時(shí)間 4 * @param f 活動(dòng)的結(jié)束時(shí)間 5 * @param n 活動(dòng)數(shù)目 6 * @return 最大兼容的活動(dòng)個(gè)數(shù) 7 */ 8 public static int maxCompatiableActivity(int[] s, int[] f, int n){ 9 int[][] c = new int[n + 2][n + 2]; 10 11 for(int j = 0; j <= n+1; j++) 12 for(int i = n+1; i >= j; i--) 13 c[i][j] = 0;//if i>=j S(i,j)是空集合 14 15 int maxTemp = 0; 16 for(int j = 1; j <= n+1; j++) 17 { 18 for(int i = 0; i < j; i++)//i < j 19 { 20 for(int k = i+1; k < j; k++)// i< k <j 21 { 22 if(s[k] >= f[i] && f[k] <= s[j])//S(i,j)不空 23 { 24 if(c[i][k] + c[k][j] + 1 > maxTemp) 25 maxTemp = c[i][k] + c[k][j] + 1; 26 } 27 }//inner for 28 c[i][j] = maxTemp; 29 maxTemp = 0; 30 }//media for 31 }//outer for 32 return c[0][n+1]; 33 }

DP時(shí)間復(fù)雜度與問題的個(gè)數(shù)以及每個(gè)問題的選擇數(shù) 有關(guān)。

比如這里的 S(i,j)一共大約有N^2個(gè)， 因?yàn)?1=<j<=N， 1=<i<j? ，這里求和大約是 (N^2)/2（對(duì)于S(i,j) i>j沒有實(shí)際意義嘛）,每個(gè)S(i,j)一共有 j-i+1種 選擇

故時(shí)間復(fù)雜度為O(N^3)

?

⑦活動(dòng)選擇問題的Greedy算法JAVA實(shí)現(xiàn)和時(shí)間復(fù)雜度分析

貪心算法即可以用遞歸實(shí)現(xiàn)，也可以用非遞歸實(shí)現(xiàn)。

1 //貪心算法的遞歸解 2 public static ArrayList<Integer> greedyActivitySelection(int[] s, int[] f, int i, int n, ArrayList<Integer> activities){ 3 //初始調(diào)用時(shí) i = 0, 所以a(1)是必選的(注意:活動(dòng)編號(hào)已經(jīng)按結(jié)束時(shí)間排序) 4 int m = i + 1; 5 6 //s[m] < f[i] 意味著活動(dòng) a(m) 與 a(i)沖突了 7 while(m <= n && s[m] < f[i]) 8 m++;//選擇下一個(gè)活動(dòng) 9 10 if(m <= n){ 11 activities.add(m); 12 greedyActivitySelection(s, f, m, n, activities); 13 } 14 return activities; 15 } 16 17 //貪心算法的非遞歸解, assume f[] has been sorted and actId 0/n+1 is virtually added 18 public static ArrayList<Integer> greedyActivitySelection2(int[] s, int[] f, int n, ArrayList<Integer> acitivities){ 19 //所有真正的活動(dòng)(不包括 活動(dòng)0和 活動(dòng)n+1)中,結(jié)束時(shí)間最早的那個(gè)活動(dòng)一定是最大兼容活動(dòng)集合中的 活動(dòng). 20 int m = 1; 21 acitivities.add(m); 22 23 for(int actId = 2; actId <= n; actId++){ 24 if(s[actId] >= f[m])//actId的開始時(shí)間在 m 號(hào)活動(dòng)之后.--actId 與 m 沒有沖突 25 { 26 m = actId; 27 acitivities.add(m); 28 } 29 } 30 return acitivities; 31 }

貪心算法的時(shí)間復(fù)雜度為O(N)，why?你可以看代碼啊。只有一個(gè)循環(huán)啊。每個(gè)活動(dòng)只會(huì)遍歷一次啊。

這里從理論上來分析下：因?yàn)閷?duì)于貪心算法而言，每次只有一種選擇即貪心選擇，而DP中每個(gè)問題S(i,j)中 j-i+1種選擇。

貪心算法做出一次貪心選擇后，即選中某個(gè)活動(dòng)后，活動(dòng)個(gè)數(shù)減少1，即問題規(guī)模減少1。

?

⑧參考資料

https://www.zhihu.com/question/23995189

《背包九講》

http://www.cnblogs.com/hapjin/p/5572483.html

?

附完整代碼：

import java.util.ArrayList; public class ActivitySelection {/*** //算法導(dǎo)論中活動(dòng)選擇問題動(dòng)態(tài)規(guī)劃求解* @param s 活動(dòng)的開始時(shí)間* @param f 活動(dòng)的結(jié)束時(shí)間* @param n 活動(dòng)數(shù)目* @return 最大兼容的活動(dòng)個(gè)數(shù)*/public static int maxCompatiableActivity(int[] s, int[] f, int n){int[][] c = new int[n + 2][n + 2];for(int j = 0; j <= n+1; j++)for(int i = n+1; i >= j; i--)c[i][j] = 0;//if i>=j S(i,j)是空集合int maxTemp = 0;for(int j = 1; j <= n+1; j++){for(int i = 0; i < j; i++)//i < j {for(int k = i+1; k < j; k++)// i< k <j {if(s[k] >= f[i] && f[k] <= s[j])//S(i,j)不空 {if(c[i][k] + c[k][j] + 1 > maxTemp)maxTemp = c[i][k] + c[k][j] + 1;}}//inner forc[i][j] = maxTemp;maxTemp = 0;}//media for}//outer forreturn c[0][n+1];}//貪心算法的遞歸解public static ArrayList<Integer> greedyActivitySelection(int[] s, int[] f, int i, int n, ArrayList<Integer> activities){//初始調(diào)用時(shí) i = 0, 所以a(1)是必選的(注意:活動(dòng)編號(hào)已經(jīng)按結(jié)束時(shí)間排序)int m = i + 1;//s[m] < f[i] 意味著活動(dòng) a(m) 與 a(i)沖突了while(m <= n && s[m] < f[i])m++;//選擇下一個(gè)活動(dòng)if(m <= n){activities.add(m);greedyActivitySelection(s, f, m, n, activities);}return activities;}//貪心算法的非遞歸解, assume f[] has been sorted and actId 0/n+1 is virtually addedpublic static ArrayList<Integer> greedyActivitySelection2(int[] s, int[] f, int n, ArrayList<Integer> acitivities){//所有真正的活動(dòng)(不包括 活動(dòng)0和 活動(dòng)n+1)中,結(jié)束時(shí)間最早的那個(gè)活動(dòng)一定是最大兼容活動(dòng)集合中的 活動(dòng).int m = 1;acitivities.add(m);for(int actId = 2; actId <= n; actId++){if(s[actId] >= f[m])//actId的開始時(shí)間在 m 號(hào)活動(dòng)之后.--actId 與 m 沒有沖突 {m = actId;acitivities.add(m);}}return acitivities;}//for test purposepublic static void main(String[] args) {//添加了 a(0) 和 a(n+1)活動(dòng). 其中s(0)=f(0)=0, s(n+1)=f(n+1)=Integer.MAX_VALUEint[] s = {0,1,3,0,5,3,5,6,8,8,2,12,Integer.MAX_VALUE};//start timeint[] f = {0,4,5,6,7,8,9,10,11,12,13,14,Integer.MAX_VALUE};//finish timeint n = 11;//活動(dòng)的個(gè)數(shù)int result = maxCompatiableActivity(s, f, n);System.out.println("最大兼容活動(dòng)個(gè)數(shù): " + result);ArrayList<Integer> acts = new ArrayList<Integer>();greedyActivitySelection(s, f, 0, n, acts);for (Integer activityId : acts)System.out.print(activityId + " ");System.out.println();ArrayList<Integer> acts2 = new ArrayList<Integer>();greedyActivitySelection2(s, f, n, acts2);for (Integer activityId : acts2)System.out.print(activityId + " ");} }

?

總結(jié)

以上是生活随笔為你收集整理的从 活动选择问题 看动态规划和贪心算法的区别与联系的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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