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

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

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

狀態(tài)總數(shù)*每個狀態(tài)轉移的狀態(tài)數(shù)*每次狀態(tài)轉移的時間動態(tài)規(guī)劃算法的時間復雜度=2一、減少狀態(tài)總數(shù)二、減少每個狀態(tài)轉移的狀態(tài)數(shù)三、減少狀態(tài)轉移的時間1、改進狀態(tài)表示；（例一）1、減少決策時間（例三）

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

例一、

RaucousRockers演唱組（USACO`96）[問題描述]

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

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

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

RaucousRockers演4

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

g[i,j,k]，(0≤i≤n，0≤j≤m，0≤k<t),表示前i首歌曲，用j張唱片另加k分鐘來錄制，最多可以錄制的歌曲數(shù)目。狀態(tài)轉移方程為：當k≥long[i]，i≥1時：g[i,j,k]=max{g[i-1,j,k-long[i]]+1，g[i-1,j,k]}當k<long[i]，i≥1時：g[i,j,k]=max{g[i-1,j-1,t-long[i]]+1，g[i-1,j,k]}規(guī)劃的邊界條件為：當0≤j≤m，0≤k<t時：g[0,j,k]=0;問題的最優(yōu)解為：g[n,m,0]。算法的時間復雜度為：O(n*m*t)。設n首歌曲按照創(chuàng)作順序排序后的長度為long[1.5改進的狀態(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)轉移方程為：g[i,j]=min{g[i-1,j]，g[i-1,j-1]+long[i]}其中(a,b)+long[i]=(a’,b’)的計算方法為：當b+long[i]≤t時：a’=a;b’=b+long[i];當b+long[i]＞t時：a’=a+1;b’=long[i];規(guī)劃的邊界條件：當0≤i≤n時，g[i,0]=(0,0)題目所求的最大值是：answer=max{k|g[n,k]≤(m-1,t)}算法的時間復雜度為：O(n2)。Back改進的狀態(tài)表示描述為：算法的時間復雜度為：O(n2)。Bac6例三、石子合并問題(NOI`95)[問題描述]

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

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

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

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

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

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

或

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

由于i<p，所以可以設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]

我們可以構造如下的合并方案：

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

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

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

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

狀態(tài)總數(shù)*每個狀態(tài)轉移的狀態(tài)數(shù)*每次狀態(tài)轉移的時間動態(tài)規(guī)劃算法的時間復雜度=15一、減少狀態(tài)總數(shù)二、減少每個狀態(tài)轉移的狀態(tài)數(shù)三、減少狀態(tài)轉移的時間1、改進狀態(tài)表示；（例一）1、減少決策時間（例三）

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

例一、

RaucousRockers演唱組（USACO`96）[問題描述]

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

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

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

RaucousRockers演17

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

g[i,j,k]，(0≤i≤n，0≤j≤m，0≤k<t),表示前i首歌曲，用j張唱片另加k分鐘來錄制，最多可以錄制的歌曲數(shù)目。狀態(tài)轉移方程為：當k≥long[i]，i≥1時：g[i,j,k]=max{g[i-1,j,k-long[i]]+1，g[i-1,j,k]}當k<long[i]，i≥1時：g[i,j,k]=max{g[i-1,j-1,t-long[i]]+1，g[i-1,j,k]}規(guī)劃的邊界條件為：當0≤j≤m，0≤k<t時：g[0,j,k]=0;問題的最優(yōu)解為：g[n,m,0]。算法的時間復雜度為：O(n*m*t)。設n首歌曲按照創(chuàng)作順序排序后的長度為long[1.18改進的狀態(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)轉移方程為：g[i,j]=min{g[i-1,j]，g[i-1,j-1]+long[i]}其中(a,b)+long[i]=(a’,b’)的計算方法為：當b+long[i]≤t時：a’=a;b’=b+long[i];當b+long[i]＞t時：a’=a+1;b’=long[i];規(guī)劃的邊界條件：當0≤i≤n時，g[i,0]=(0,0)題目所求的最大值是：answer=max{k|g[n,k]≤(m-1,t)}算法的時間復雜度為：O(n2)。Back改進的狀態(tài)表示描述為：算法的時間復雜度為：O(n2)。Bac19例三、石子合并問題(NOI`95)[問題描述]

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

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

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

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

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

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

或

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

由于i<p，所以可以設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]

我們可以構造如下的合并方案：

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