動(dòng)態(tài)規(guī)劃算法時(shí)間效率的優(yōu)化課件

動(dòng)態(tài)規(guī)劃算法時(shí)間效率的優(yōu)化

動(dòng)態(tài)規(guī)劃算法時(shí)間效率的優(yōu)化1動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度=

狀態(tài)總數(shù)*每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)*每次狀態(tài)轉(zhuǎn)移的時(shí)間動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度=2一、減少狀態(tài)總數(shù)二、減少每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)三、減少狀態(tài)轉(zhuǎn)移的時(shí)間1、改進(jìn)狀態(tài)表示；（例一）1、減少?zèng)Q策時(shí)間（例三）

方法：采用恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)；2、減少計(jì)算遞推式的時(shí)間方法：進(jìn)行預(yù)處理，利用計(jì)算結(jié)果等；2、其他方法：選取恰當(dāng)?shù)囊?guī)劃方向等；1、根據(jù)最優(yōu)解的性質(zhì)減少?zèng)Q策量；（例二）2、其他方法：利用四邊形不等式證明決策的單調(diào)性等；一、減少狀態(tài)總數(shù)1、改進(jìn)狀態(tài)表示；（例一）1、減少?zèng)Q策時(shí)間3

例一、

RaucousRockers演唱組（USACO`96）[問(wèn)題描述]

現(xiàn)有n首由RaucousRockers演唱組錄制的歌曲，計(jì)劃從中選擇一些歌曲來(lái)發(fā)行m張唱片，每張唱片至多包含t分鐘的音樂(lè)，唱片中的歌曲不能重疊。按下面的標(biāo)準(zhǔn)進(jìn)行選擇：

(1)這組唱片中的歌曲必須按照它們創(chuàng)作的順序排序；

(2)包含歌曲的總數(shù)盡可能多。輸入n，m，t，和n首歌曲的長(zhǎng)度，它們按照創(chuàng)作順序排序，沒(méi)有一首歌超出一張唱片的長(zhǎng)度，而且不可能將所有歌曲的放在唱片中。輸出所能包含的最多的歌曲數(shù)目。例一、

RaucousRockers演4

設(shè)n首歌曲按照創(chuàng)作順序排序后的長(zhǎng)度為long[1..n]，則動(dòng)態(tài)規(guī)劃的狀態(tài)表示描述為：

g[i,j,k]，(0≤i≤n，0≤j≤m，0≤k<t),表示前i首歌曲，用j張唱片另加k分鐘來(lái)錄制，最多可以錄制的歌曲數(shù)目。狀態(tài)轉(zhuǎn)移方程為：當(dāng)k≥long[i]，i≥1時(shí)：g[i,j,k]=max{g[i-1,j,k-long[i]]+1，g[i-1,j,k]}當(dāng)k<long[i]，i≥1時(shí)：g[i,j,k]=max{g[i-1,j-1,t-long[i]]+1，g[i-1,j,k]}規(guī)劃的邊界條件為：當(dāng)0≤j≤m，0≤k<t時(shí)：g[0,j,k]=0;問(wèn)題的最優(yōu)解為：g[n,m,0]。算法的時(shí)間復(fù)雜度為：O(n*m*t)。設(shè)n首歌曲按照創(chuàng)作順序排序后的長(zhǎng)度為long[1.5改進(jìn)的狀態(tài)表示描述為：

g[i,j]=(a,b)，0≤i≤n，0≤j≤i，0≤a≤m，0≤b≤t，表示在前i首歌曲中選取j首錄制所需的最少唱片為：a張唱片另加b分鐘。狀態(tài)轉(zhuǎn)移方程為：g[i,j]=min{g[i-1,j]，g[i-1,j-1]+long[i]}其中(a,b)+long[i]=(a’,b’)的計(jì)算方法為：當(dāng)b+long[i]≤t時(shí)：a’=a;b’=b+long[i];當(dāng)b+long[i]＞t時(shí)：a’=a+1;b’=long[i];規(guī)劃的邊界條件：當(dāng)0≤i≤n時(shí)，g[i,0]=(0,0)題目所求的最大值是：answer=max{k|g[n,k]≤(m-1,t)}算法的時(shí)間復(fù)雜度為：O(n2)。Back改進(jìn)的狀態(tài)表示描述為：算法的時(shí)間復(fù)雜度為：O(n2)。Bac6例三、石子合并問(wèn)題(NOI`95)[問(wèn)題描述]

在一個(gè)操場(chǎng)上擺放著一圈n堆石子?，F(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆的石子數(shù)記為該次合并的得分。試編程求出將n堆石子合并成一堆的最小得分和最大得分以及相應(yīng)的合并方案。本例只考慮最大得分。例三、石子合并問(wèn)題(NOI`95)7i<j

規(guī)劃的邊界條件為：m[i,i]=0

令s[i,j]=k，表示合并的最優(yōu)斷開(kāi)位置。算法的時(shí)間復(fù)雜度為O(n3)。設(shè)各堆的石子數(shù)依次為d[1..n]，則動(dòng)態(tài)規(guī)劃的狀態(tài)表示為：

m[i,j]，1≤i,j≤n，表示合并d[i..j]所得到的最大得分：令，則狀態(tài)轉(zhuǎn)移方程為：i<j規(guī)劃的邊界條件為：m[i,i]=0設(shè)各堆的石子數(shù)依8

合并第i堆到第j堆石子的最優(yōu)斷開(kāi)位置s[i,j]要么等于i，要么等于j-1，也就是說(shuō)最優(yōu)合并方案只可能是：

{(i)(i+1…j)}

或

{(i…j-1)(j)}證明：設(shè)合并第i堆到第j堆石子的最優(yōu)斷開(kāi)位置s[i,j]=p，且i<p<j-1。情況1、t[i,p]≤t[p+1,j]

由于i<p，所以可以設(shè)q=s[i,p]。于是最優(yōu)合并方案為：

{[(i…q)(q+1...p)](p+1…j)}

它的得分F1=m[i,q]+m[q+1,p]+m[p+1,j]+t[i,j]+t[i,p]

我們可以構(gòu)造如下的合并方案：

{(i…q)[(q+1...p)(p+1…j)]}

它的得分F2=m[i,q]+m[q+1,p]+m[p+1,j]+t[i,j]+t[q+1,j]

由于q<p，所以t[i,p]≤t[p+1,j]<t[q+1,j]

所以F1<F2，這與合并第i堆到第j堆石子的最優(yōu)斷開(kāi)位置s[i,j]=p矛盾情況2、t[i,p]>t[p+1,j]與情況1是對(duì)稱的。合并第i堆到第j堆石子的最優(yōu)斷開(kāi)位置s[i,9狀態(tài)轉(zhuǎn)移方程優(yōu)化為：m[i,j]=max{m[i+1,j],m[i,j-1]}+t[i,j]i<j規(guī)劃的邊界條件是：m[i,i]=0算法的時(shí)間復(fù)雜度O(n2)。Back狀態(tài)轉(zhuǎn)移方程優(yōu)化為：Back10例三、LOSTCITY(NOI`2000)[問(wèn)題描述]現(xiàn)給出一張單詞表、特定的語(yǔ)法規(guī)則和一篇文章：文章和單詞表中只含26個(gè)小寫(xiě)英文字母a…z。單詞表中的單詞只有名詞，動(dòng)詞和輔詞這三種詞性，且相同詞性的單詞互不相同。單詞的個(gè)數(shù)不超過(guò)1000，單詞的長(zhǎng)度均不超過(guò)20。語(yǔ)法規(guī)則可簡(jiǎn)述為：名詞短語(yǔ)：任意個(gè)輔詞前綴接上一個(gè)名詞；動(dòng)詞短語(yǔ)：任意個(gè)輔詞前綴接上一個(gè)動(dòng)詞；句子：以名詞短語(yǔ)開(kāi)頭，名詞短語(yǔ)與動(dòng)詞短語(yǔ)相間連接而成。文章的長(zhǎng)度不超過(guò)5k。且已知文章是由有限個(gè)句子組成的，句子只包含有限個(gè)單詞。編程將這篇文章劃分成最少的句子，在此前提之下，要求劃分出的單詞數(shù)最少。例三、LOSTCITY(NOI`2000)11我們分別用v,u,a表示動(dòng)詞，名詞和輔詞，給出的文章用L[1..M]表示，則狀態(tài)表示描述為：F(v,i)：表示將L的前i個(gè)字符劃分為以動(dòng)詞結(jié)尾（當(dāng)i<>M時(shí)，可帶任意個(gè)輔詞后綴）的最優(yōu)分解方案下劃分的句子數(shù)與單詞數(shù)；F(u,i)：表示將L的前i個(gè)字符劃分為以名詞結(jié)尾（當(dāng)i<>M時(shí)，可帶任意個(gè)輔詞后綴）的最優(yōu)分解方案下劃分的句子數(shù)與單詞數(shù)。狀態(tài)轉(zhuǎn)移方程為：F(v,i)=min{F(u,j)+(0,1)，

L(j+1..i)為動(dòng)詞；

F(v,j)+(0,1)，

L(j+1..i)為輔詞，i<>M；}F(u,i)=min{F(u,j)+(1,1),L(j+1..i)為名詞；

F(v,j)+(0,1),L(j+1..i)為名詞；

F(u,j)+(0,1),L(j+1..i)為輔詞，i<>M；}邊界條件：F(v,0)=(1,0)；

F(u,0)=(∞,∞)；問(wèn)題的解為：min{F(v,M),F(u,M)}；我們分別用v,u,a表示動(dòng)詞，名詞和輔詞，給出的文章用L[112順序查找二分查找哈希表檢索樹(shù)算法的時(shí)間復(fù)雜度O(20*M*N)O(20*M*log2N)O(20*M)O(M)最壞情況下的比較次數(shù)1081061055*103Input.009超時(shí)1.27s0.32s0.05sInput.010超時(shí)1.33s0.33s0.05sBack采用不同的方法查找字符串的比較：設(shè)單詞表的規(guī)模為N（N的最大值為1000）設(shè)文章的長(zhǎng)度為M（M的最大值為5000）（測(cè)試環(huán)境：Pentium200/32MB）順序查找二分查找哈希表檢索樹(shù)算法的時(shí)間復(fù)雜度O(20*M*N13動(dòng)態(tài)規(guī)劃算法時(shí)間效率的優(yōu)化

動(dòng)態(tài)規(guī)劃算法時(shí)間效率的優(yōu)化14動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度=

狀態(tài)總數(shù)*每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)*每次狀態(tài)轉(zhuǎn)移的時(shí)間動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度=15一、減少狀態(tài)總數(shù)二、減少每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)三、減少狀態(tài)轉(zhuǎn)移的時(shí)間1、改進(jìn)狀態(tài)表示；（例一）1、減少?zèng)Q策時(shí)間（例三）

方法：采用恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)；2、減少計(jì)算遞推式的時(shí)間方法：進(jìn)行預(yù)處理，利用計(jì)算結(jié)果等；2、其他方法：選取恰當(dāng)?shù)囊?guī)劃方向等；1、根據(jù)最優(yōu)解的性質(zhì)減少?zèng)Q策量；（例二）2、其他方法：利用四邊形不等式證明決策的單調(diào)性等；一、減少狀態(tài)總數(shù)1、改進(jìn)狀態(tài)表示；（例一）1、減少?zèng)Q策時(shí)間16

例一、

RaucousRockers演唱組（USACO`96）[問(wèn)題描述]

現(xiàn)有n首由RaucousRockers演唱組錄制的歌曲，計(jì)劃從中選擇一些歌曲來(lái)發(fā)行m張唱片，每張唱片至多包含t分鐘的音樂(lè)，唱片中的歌曲不能重疊。按下面的標(biāo)準(zhǔn)進(jìn)行選擇：

(1)這組唱片中的歌曲必須按照它們創(chuàng)作的順序排序；

(2)包含歌曲的總數(shù)盡可能多。輸入n，m，t，和n首歌曲的長(zhǎng)度，它們按照創(chuàng)作順序排序，沒(méi)有一首歌超出一張唱片的長(zhǎng)度，而且不可能將所有歌曲的放在唱片中。輸出所能包含的最多的歌曲數(shù)目。例一、

RaucousRockers演17

設(shè)n首歌曲按照創(chuàng)作順序排序后的長(zhǎng)度為long[1..n]，則動(dòng)態(tài)規(guī)劃的狀態(tài)表示描述為：

g[i,j,k]，(0≤i≤n，0≤j≤m，0≤k<t),表示前i首歌曲，用j張唱片另加k分鐘來(lái)錄制，最多可以錄制的歌曲數(shù)目。狀態(tài)轉(zhuǎn)移方程為：當(dāng)k≥long[i]，i≥1時(shí)：g[i,j,k]=max{g[i-1,j,k-long[i]]+1，g[i-1,j,k]}當(dāng)k<long[i]，i≥1時(shí)：g[i,j,k]=max{g[i-1,j-1,t-long[i]]+1，g[i-1,j,k]}規(guī)劃的邊界條件為：當(dāng)0≤j≤m，0≤k<t時(shí)：g[0,j,k]=0;問(wèn)題的最優(yōu)解為：g[n,m,0]。算法的時(shí)間復(fù)雜度為：O(n*m*t)。設(shè)n首歌曲按照創(chuàng)作順序排序后的長(zhǎng)度為long[1.18改進(jìn)的狀態(tài)表示描述為：

g[i,j]=(a,b)，0≤i≤n，0≤j≤i，0≤a≤m，0≤b≤t，表示在前i首歌曲中選取j首錄制所需的最少唱片為：a張唱片另加b分鐘。狀態(tài)轉(zhuǎn)移方程為：g[i,j]=min{g[i-1,j]，g[i-1,j-1]+long[i]}其中(a,b)+long[i]=(a’,b’)的計(jì)算方法為：當(dāng)b+long[i]≤t時(shí)：a’=a;b’=b+long[i];當(dāng)b+long[i]＞t時(shí)：a’=a+1;b’=long[i];規(guī)劃的邊界條件：當(dāng)0≤i≤n時(shí)，g[i,0]=(0,0)題目所求的最大值是：answer=max{k|g[n,k]≤(m-1,t)}算法的時(shí)間復(fù)雜度為：O(n2)。Back改進(jìn)的狀態(tài)表示描述為：算法的時(shí)間復(fù)雜度為：O(n2)。Bac19例三、石子合并問(wèn)題(NOI`95)[問(wèn)題描述]

在一個(gè)操場(chǎng)上擺放著一圈n堆石子。現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆的石子數(shù)記為該次合并的得分。試編程求出將n堆石子合并成一堆的最小得分和最大得分以及相應(yīng)的合并方案。本例只考慮最大得分。例三、石子合并問(wèn)題(NOI`95)20i<j

規(guī)劃的邊界條件為：m[i,i]=0

令s[i,j]=k，表示合并的最優(yōu)斷開(kāi)位置。算法的時(shí)間復(fù)雜度為O(n3)。設(shè)各堆的石子數(shù)依次為d[1..n]，則動(dòng)態(tài)規(guī)劃的狀態(tài)表示為：

m[i,j]，1≤i,j≤n，表示合并d[i..j]所得到的最大得分：令，則狀態(tài)轉(zhuǎn)移方程為：i<j規(guī)劃的邊界條件為：m[i,i]=0設(shè)各堆的石子數(shù)依21

合并第i堆到第j堆石子的最優(yōu)斷開(kāi)位置s[i,j]要么等于i，要么等于j-1，也就是說(shuō)最優(yōu)合并方案只可能是：

{(i)(i+1…j)}

或

{(i…j-1)(j)}證明：設(shè)合并第i堆到第j堆石子的最優(yōu)斷開(kāi)位置s[i,j]=p，且i<p<j-1。情況1、t[i,p]≤t[p+1,j]

由于i<p，所以可以設(shè)q=s[i,p]。于是最優(yōu)合并方案為：

{[(i…q)(q+1...p)](p+1…j)}

它的得分F1=m[i,q]+m[q+1,p]+m[p+1,j]+t[i,j]+t[i,p]

我們可以構(gòu)造如下的合并方案：

{(i…q)[(q+1...p)(p+1…j)]}

它的得分F2=m[i,q]+m[q+1,p]+m[p+1,j]+t[i,j]+t[q+1,j]

由于q<p，所以t[i,p]≤t[p+1,j]<t[q+1,j]

所以F1<F2，這與合并第i堆到第j堆石子的最優(yōu)斷開(kāi)位置s[i,j]=p矛盾情況2、t[i,p]>t[p+1,j]與情況1是對(duì)稱的。合并第i堆到第j堆石子的最優(yōu)斷開(kāi)位置s[i,22狀態(tài)轉(zhuǎn)移方程優(yōu)化為：m[i,j]=max{m[i+1,j],m[i,j-1]}+t[i,j]i<j規(guī)劃的邊界條件是：m[i,i]=0算法的時(shí)間復(fù)雜度O(n2)。Back狀態(tài)轉(zhuǎn)移方程優(yōu)化為：Back23例三、LOSTCITY(NOI`2000)[問(wèn)題描述]現(xiàn)給出一張單詞表、特定的語(yǔ)法規(guī)則和一篇文章：文章和單詞表中只含26個(gè)小寫(xiě)英文字母a…z。單詞表中的單詞只有名詞，動(dòng)詞和輔詞這三種詞性，且相同詞性的單詞互不相同。單詞的個(gè)數(shù)不超過(guò)1000，單詞的長(zhǎng)度均不超過(guò)20。語(yǔ)法規(guī)則可簡(jiǎn)述為：名詞短語(yǔ)：任意個(gè)輔詞前綴接上一個(gè)名詞；動(dòng)詞短語(yǔ)：任意個(gè)輔詞前綴接上一個(gè)動(dòng)詞；句子：以名詞短語(yǔ)開(kāi)頭，名詞短語(yǔ)與動(dòng)詞短語(yǔ)相間連接而成。文章的長(zhǎng)度不超過(guò)5k。且已知文章是由有限個(gè)句子組成的，句子只包含有限個(gè)單詞。編程將這篇文章劃分成最少的句子，在此前提之下，要求劃分出的單詞數(shù)最少。例三、LOSTCITY(NOI`2000)24我們分別用v,u,a表示動(dòng)詞，名詞和輔詞，給出的文章用L[1..M]表示，則狀態(tài)表示描述為：F(v,i)：表示將L的前i個(gè)字符劃分為以動(dòng)詞結(jié)尾（當(dāng)i<>M時(shí)，