藍雯飛，吳子瑩，李　強，強小利

(中南民族大學(xué) 計算機科學(xué)學(xué)院，武漢 430074)

?

動態(tài)規(guī)劃算法的時間效率改進

藍雯飛，吳子瑩，李強，強小利

(中南民族大學(xué) 計算機科學(xué)學(xué)院，武漢 430074)

摘要分析了影響動態(tài)規(guī)劃算法時間復(fù)雜度的3個因素，分別從3個方面給出了改進動態(tài)規(guī)劃算法時間復(fù)雜度的優(yōu)化措施，從理論上分析了優(yōu)化方法的有效性和正確性.與傳統(tǒng)算法相比，優(yōu)化后的算法時間復(fù)雜度有一定程度的提高，能夠適用于數(shù)據(jù)規(guī)模更大的問題.

關(guān)鍵詞動態(tài)規(guī)劃；時間效率；優(yōu)化

動態(tài)規(guī)劃是求解決策過程最優(yōu)化的數(shù)學(xué)方法.20世紀50年代初，美國數(shù)學(xué)家R.E.Bellman等人[1]在研究多階段決策過程優(yōu)化問題時，提出了著名的最優(yōu)化原理，即把一個多階段決策問題轉(zhuǎn)化為一系列單階段問題，然后利用各階段之間的關(guān)系逐一求解，從而創(chuàng)立了解決這類過程優(yōu)化問題的新方法——動態(tài)規(guī)劃.

動態(tài)規(guī)劃在各個領(lǐng)域得到了廣泛的應(yīng)用[2,3].廣泛的應(yīng)用背景也對動態(tài)規(guī)劃的時間效率提出了更高的要求.用動態(tài)規(guī)劃方法解決問題時，常規(guī)設(shè)計的算法能解決一些基本的數(shù)據(jù)量，但當問題的數(shù)據(jù)規(guī)模龐大時，常規(guī)設(shè)計的動態(tài)規(guī)劃算法的時間效率將不能滿足要求，此時需要考慮算法的時間效率是否有優(yōu)化的余地.然而，現(xiàn)有的研究一般針對具體問題的特點設(shè)計算法優(yōu)化措施，當問題不同時，相應(yīng)的時間效率優(yōu)化措施就失去作用[4].本文將從構(gòu)成動態(tài)規(guī)劃算法時間復(fù)雜度的因素出發(fā)，給出優(yōu)化措施提高算法的時間效率，使動態(tài)規(guī)劃算法能夠適用于更大數(shù)據(jù)規(guī)模的領(lǐng)域.

1動態(tài)規(guī)劃算法的時間效率分析

用動態(tài)規(guī)劃思想解決問題的關(guān)鍵在于算法減少了重復(fù)或不必要的計算，問題中子問題的重疊程度是決定算法時間效率的關(guān)鍵.動態(tài)規(guī)劃算法在解決問題時，會存儲算法中出現(xiàn)的子問題的解，避免了重復(fù)求解同一子問題，這樣就提高了算法的時間效率[5].但是，在解決問題的過程中，算法仍然存在一定程度的冗余，如：對子問題無意義的引用，求解了無用的子問題等.

動態(tài)規(guī)劃算法的時間復(fù)雜度主要由3個因素決定：問題中狀態(tài)的總個數(shù)，每次狀態(tài)轉(zhuǎn)移所涉及的狀態(tài)數(shù)以及每次狀態(tài)轉(zhuǎn)移的時間[6].若對3個因素中的一個或者多個進行優(yōu)化，將會提高算法的時間效率.但是需要注意的是：這3個影響算法時間效率的因素并不是相互獨立的，而是有聯(lián)系的.在有些情況下，對某個因素進行了優(yōu)化，另外的因素也會隨之得到優(yōu)化；而在另一些情況下，優(yōu)化某個因素卻要以增大另一因素為代價[7].因此，在進行優(yōu)化時，要實現(xiàn)3個因素的平衡不能顧此失彼.

2狀態(tài)總數(shù)的優(yōu)化

用動態(tài)規(guī)劃思想解決問題實質(zhì)上是求解問題中所有的狀態(tài)，因此問題中狀態(tài)的總個數(shù)將直接影響算法的時間復(fù)雜度.減少問題的狀態(tài)總數(shù)對提高動態(tài)規(guī)劃算法的時間效率具有重要的意義.下面給出兩種減少狀態(tài)總數(shù)的方法.

2.1雙向動態(tài)規(guī)劃

動態(tài)規(guī)劃算法可以采用兩種方法：順推和逆推.在某些情況下，同一個動態(tài)規(guī)劃算法，采用不同的實現(xiàn)方法，程序的時間效率上會有一定的差異.一般地，若確定了問題的初始狀態(tài)，而結(jié)束狀態(tài)卻不確定，則可以通過“自頂向下”的順推方法實現(xiàn)；反之，若確定了問題的結(jié)束狀態(tài)，而初始狀態(tài)卻不確定，則可以考慮“自底向上”的逆推方法.若確定了問題的初始狀態(tài)和結(jié)束狀態(tài)，即上述兩種實現(xiàn)方法順推和逆推都可以采用的情況下，該選用哪種方法？或者，能否使用兩種方法的結(jié)合——雙向動態(tài)規(guī)劃[8]？

雙向廣度優(yōu)先搜索算法的思想是：搜索沿著兩個方向同時進行，一是正向搜索即從初始狀態(tài)向目標狀態(tài)方向搜索，另一個是逆向搜索即從目標狀態(tài)向初始狀態(tài)方向搜索.當兩個方向的搜索匯合時終止搜索過程，并進行判斷，得到問題的求解.

廣度優(yōu)先搜索算法可以結(jié)合雙向擴展的方法來減少狀態(tài)總量.借用雙向廣度優(yōu)先搜索算法，雙向動態(tài)規(guī)劃的思想是：當問題的狀態(tài)空間很大，并且確定了問題的初始狀態(tài)和結(jié)束狀態(tài)，而單向擴展會導(dǎo)致大量無效狀態(tài)計算的情況下，為了降低狀態(tài)的規(guī)模，可以從初始狀態(tài)和結(jié)束狀態(tài)開始在兩個方向上進行擴展，并在兩者擴展的交匯處進行最優(yōu)化的判斷，從而得到問題的求解.

實際問題中，可以確定問題的初始和結(jié)束狀態(tài)，問題的狀態(tài)數(shù)量龐大，每一階段的狀態(tài)變量快速增長，此時，可以考慮用雙向規(guī)劃方法來減少問題中需要計算的狀態(tài)總量[9].

2.2改進狀態(tài)的表示

問題中需要求解的狀態(tài)個數(shù)與狀態(tài)表示的方法直接相關(guān)，通?？梢酝ㄟ^改進狀態(tài)的表示方法來改變問題中狀態(tài)的總數(shù).在用動態(tài)規(guī)劃思想解決問題時，應(yīng)用不同的狀態(tài)表示方法設(shè)計出的算法，所需求解的狀態(tài)總數(shù)也不同[10].當影響動態(tài)規(guī)劃算法時間效率的另外兩個因素(每次狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)和每次狀態(tài)轉(zhuǎn)移的時間)不變、而問題中需要計算的狀態(tài)數(shù)減少時，這樣就可以從整體上提高算法的時間效率.動態(tài)規(guī)劃方法體現(xiàn)的是一種以空間換時間的思想，算法運行中需要存儲已經(jīng)計算過的狀態(tài)，再次遇到重復(fù)的狀態(tài)將直接返回結(jié)果，算法的空間復(fù)雜度主要取決于問題中需要計算的狀態(tài)個數(shù)，因此減少問題中所需計算的狀態(tài)總數(shù)將會降低算法的空間復(fù)雜度.當問題中狀態(tài)的維數(shù)較多，導(dǎo)致算法的時空復(fù)雜度較大時，就可以考慮換一種方式來表示原有狀態(tài).通過改進狀態(tài)的表示方法從而達到減少狀態(tài)總數(shù)是比較常見的動態(tài)規(guī)劃優(yōu)化方法.

3每次狀態(tài)轉(zhuǎn)移所涉及的狀態(tài)數(shù)的優(yōu)化

用動態(tài)規(guī)劃算法解決問題的過程就是計算問題中所有的狀態(tài)(子問題).對當前狀態(tài)的計算都是通過已經(jīng)求解過的狀態(tài)和在此狀態(tài)上的決策，這就是狀態(tài)轉(zhuǎn)移過程.計算狀態(tài)時每次狀態(tài)轉(zhuǎn)移所涉及的狀態(tài)數(shù)是影響動態(tài)規(guī)劃算法時間效率的關(guān)鍵因素.本文討論減少每次狀態(tài)轉(zhuǎn)移所涉及的狀態(tài)數(shù)的一些優(yōu)化措施.

3.1四邊形不等式與決策量的優(yōu)化

運用動態(tài)規(guī)劃方法解決問題，問題的規(guī)劃模型為：

(1)

其中w(i,j)表示問題中第i階段到第j階段的度量值和，這個度量在不同的問題中含義不同，可以為利潤、產(chǎn)量和資源的消耗等.f(i,j)表示問題在(i,j)階段所處的狀態(tài)，狀態(tài)轉(zhuǎn)移方程的含義是將原問題分解成兩個子問題的形式，然后再進行求解，相關(guān)問題如最少矩陣鏈乘法[11]、最優(yōu)二叉查找樹[12]等問題，都用到了這個狀態(tài)轉(zhuǎn)移方程.

其中，如果權(quán)值函數(shù)w滿足條件：

w(i,j)≤w(i′,j′),(i,j)?(i′,j′),

(2)

則稱函數(shù)w滿足關(guān)于區(qū)間包含關(guān)系單調(diào)性.

若函數(shù)w滿足條件：

(3)

則稱函數(shù)w滿足四邊形不等式.

在討論具體的優(yōu)化措施前，先給出兩個推論(其證明過程略).

推論1若函數(shù)w同時滿足區(qū)間包含關(guān)系單調(diào)性和四邊形不等式，則狀態(tài)函數(shù)f也滿足四邊形不等式，即f(a,c)+f(b,d)≤f(b,c)+f(a,d),a≤b≤c≤d.

推論2當狀態(tài)函數(shù)f(a,b)滿足四邊形不等式性質(zhì)，定義v(a,b)為狀態(tài)f(a,b)取最小值時的決策，則有:

v(a,b-1)≤v(a,b)≤v(a+1,b).

(4)

利用決策變量的性質(zhì)，得到優(yōu)化后的狀態(tài)轉(zhuǎn)移方程如下：

(5)

(5)式計算狀態(tài)f(i,j)時，決策點k的范圍由算法(1)中的(i,j)優(yōu)化到(v(i,j-1),v(i+1,j)).這樣就縮小了決策變量v(i,j)的取值范圍，減少了每次狀態(tài)轉(zhuǎn)移所需要考慮的狀態(tài)數(shù)，提高了算法的時間效率.算法以l=j-i的大小劃分階段，因此在計算f(i,j)時，決策范圍(v(i,j-1),v(i+1,j))都已求出.

公式(1)的時間復(fù)雜度為O(n3)[13]，在此基礎(chǔ)上進行優(yōu)化后的(5)式的時間復(fù)雜度計算如下：

可見(5)式的時間復(fù)雜度為O(n2).

上述動態(tài)規(guī)劃的優(yōu)化措施具有普遍性，若問題的狀態(tài)轉(zhuǎn)移方程與(1)式類似，且權(quán)值函數(shù)w(i,j)同時滿足區(qū)間包含關(guān)系單調(diào)性和四邊形不等式，則可采用上述優(yōu)化措施.

利用狀態(tài)轉(zhuǎn)移方程滿足四邊形不等式，對狀態(tài)之間的關(guān)系進行分析，然后推導(dǎo)出最優(yōu)決策具有較小的范圍.在計算狀態(tài)時，減少了每次狀態(tài)轉(zhuǎn)移所需要考慮的狀態(tài)數(shù)，從而降低了算法的時間復(fù)雜度.我們可以從這個優(yōu)化措施中得到啟發(fā)，在運用動態(tài)規(guī)劃算法解決問題的過程中，不僅可以通過減少狀態(tài)總數(shù)來優(yōu)化算法，還可以充分利用最優(yōu)決策的性質(zhì)來優(yōu)化算法.

3.2合理組織已求解的狀態(tài)

在用動態(tài)規(guī)劃方法解決問題的過程中，問題中已經(jīng)計算出來的狀態(tài)會不斷被引用.因此，深入地分析已求解出的狀態(tài)間關(guān)系，并對其進行合理地組織，有時可以簡化問題中狀態(tài)間的依賴關(guān)系，這樣有助于提高動態(tài)規(guī)劃算法的時間效率.

通過一個實例進行說明，問題的規(guī)劃模型如下：

(6)

其中m(i)表示問題第i階段的條件值，f(i)表示問題第i階段時的狀態(tài)值，狀態(tài)轉(zhuǎn)移方程表示只有在問題當前階段的條件值大于先前階段的條件值時，狀態(tài)才會轉(zhuǎn)移，相關(guān)問題有“最長遞增子序列問題”等[14].狀態(tài)轉(zhuǎn)移模型中有O(n)個待求解的狀態(tài)，每次轉(zhuǎn)移的時間為O(1)，每次轉(zhuǎn)移的狀態(tài)數(shù)為O(i),i=1,2,…,n-1，算法的時間復(fù)雜度為O(0+1+2+…+n-1)=O(n(n-1)/2)=O(n2).

分析問題中已求解狀態(tài)之間的關(guān)系：

1) 當m(i)i，k>j,若m(k)>m(j)，則第k階段的狀態(tài)f(k)可由第i與第j階段的狀態(tài)做出轉(zhuǎn)移，若m(i)

由此可見，當兩個階段的狀態(tài)值相等時，保留較小的元素值m(i)，即可完成問題后續(xù)的狀態(tài)轉(zhuǎn)移過程.

2) 當m(i)f(j).對于k>i，k>j,若m(k)m(j)時，狀態(tài)f(k)可以由第i階段的狀態(tài)f(i)決策得出.無論條件值m(k)與m(i)、m(j)的大小關(guān)系如何，狀態(tài)f(k)都不需要通過狀態(tài)f(j)轉(zhuǎn)移得到.

綜上所述，若狀態(tài)f(i)可以在i

對于任意的i,j∈D，均有m(i)≠m(j)，若m(i)

考慮問題中狀態(tài)求解的過程：若狀態(tài)f(1,2,…,i-1)已被求解出，將已經(jīng)求解的狀態(tài)組織成集合D，求解狀態(tài)f(i)：

1) 若j∈D，有m(i)=m(j)，則有f(i)=f(j)，此時不必將狀態(tài)f(i)保留在集合D中.

2) 若j∈D，k∈D,m(j)m(j)，則f(i)=max{f(j),j∈D}+1，將m(i)加到集合D中，此時m(i)是集合D中的最大元素，3種情況下都維持了集合D的單調(diào)關(guān)系.

優(yōu)化后的狀態(tài)轉(zhuǎn)移方程為：

f(i)=

(7)

集合D中元素m(i)是單調(diào)遞增的，因此上述狀態(tài)轉(zhuǎn)移過程中，可以用高效的查找算法——二分查找，這樣每次轉(zhuǎn)移的時間為O(log2n)，而每次狀態(tài)轉(zhuǎn)移涉及的狀態(tài)數(shù)僅為O(1).優(yōu)化后，增加了每次狀態(tài)轉(zhuǎn)移的時間(從O(1)到O(log2n))，但狀態(tài)轉(zhuǎn)移的數(shù)量卻減少了(由O(n)降為O(1)).這體現(xiàn)了在優(yōu)化過程中，時間效率影響因素之間的矛盾.優(yōu)化后，算法的時間復(fù)雜度為O(nlog2n)，因此，在總體上提高了算法的時間效率.

上述優(yōu)化過程，首先分析問題中已求解狀態(tài)之間的關(guān)系，根據(jù)狀態(tài)轉(zhuǎn)移關(guān)系推導(dǎo)出條件值與狀態(tài)之間的單調(diào)關(guān)系.合理地保留已計算出的狀態(tài)，從而減少了每次狀態(tài)轉(zhuǎn)移過程中涉及的狀態(tài)數(shù)，在狀態(tài)轉(zhuǎn)移時，利用集合中條件值的單調(diào)性用二分查找實現(xiàn)快速查找，最后在整體上實現(xiàn)了算法的優(yōu)化.

3.3運用貪心思想優(yōu)化動態(tài)規(guī)劃算法

動態(tài)規(guī)劃方法解決實際問題的過程中，常常會面臨兩大困難：一是當問題的條件錯綜復(fù)雜，導(dǎo)致無法建立有效的規(guī)劃模型時，此時常規(guī)的動態(tài)規(guī)劃方法將難以下手[15]；二是問題可以用動態(tài)規(guī)劃方法求解，但由于問題的狀態(tài)空間龐大，轉(zhuǎn)移關(guān)系復(fù)雜等一系列因素，導(dǎo)致算法的時間效率并不樂觀.此時，可以考慮將貪心思想運用到解決問題的過程中，能夠簡化問題的求解.

貪心思想在解決問題時，會依據(jù)特定的貪心策略，選擇問題當前狀態(tài)下的最優(yōu)解而不從問題全局最優(yōu)考慮，因此算法不能對所有的優(yōu)化問題都得到最優(yōu)解，但這種局部最優(yōu)的做法往往能達到簡化問題模型的效果.

用動態(tài)規(guī)劃方法解決問題，當問題的狀態(tài)空間龐大、模型復(fù)雜，常規(guī)的動態(tài)規(guī)劃方法效率不高時，此時可以考慮在動態(tài)規(guī)劃中運用貪心思想，深入分析問題的本質(zhì)，找出算法中的冗余，減少可能產(chǎn)生最優(yōu)解的允許決策集合的范圍，進而達到優(yōu)化算法時間效率的目的[16].

在實際的問題中會遇到如下狀態(tài)轉(zhuǎn)移方程：

(8)

這是典型的區(qū)間模型的動態(tài)規(guī)劃，問題一般是求整段區(qū)間的最優(yōu)值，這類問題的基本特征是可以將問題分解成兩個子問題合并的形式[17].解決方法是枚舉合并點，將問題分解成左右兩個子問題，然后將左右兩個部分的最優(yōu)解進行合并從而得到原問題的最優(yōu)解.

(8)式中狀態(tài)的個數(shù)為O(n2)，每個狀態(tài)的計算需要O(n)的狀態(tài)做出決策，每次決策的時間為O(1)，因此，算法總的時間復(fù)雜度為O(n3)，空間復(fù)雜度為O(n2).當(8)式中的函數(shù)opt表示取最小值(min)，權(quán)值函數(shù)w(i,j)同時滿足四邊形不等式和區(qū)間包含關(guān)系單調(diào)性時，可以利用推論1和推論2，通過縮小決策的范圍來減少問題中計算每個狀態(tài)時所涉及的狀態(tài)數(shù)，從而將算法的時間效率優(yōu)化到O(n2).

f(i,j)=

(9)

優(yōu)化后轉(zhuǎn)移方程中狀態(tài)總數(shù)仍然是O(n2)，但每次狀態(tài)的計算只需涉及O(1)的狀態(tài)做出決策.因此，算法總的時間復(fù)雜度為O(n2).

(9)式的優(yōu)化過程是通過對問題最優(yōu)解的構(gòu)成進行分析，找出問題狀態(tài)依賴的關(guān)系，從而避免了一些無效狀態(tài)的枚舉，降低了算法的時間復(fù)雜度，這是貪心思想的經(jīng)典體現(xiàn)[18].“貪心的動態(tài)規(guī)劃”并不是一種具體的算法，是一種優(yōu)化的思想，想要在動態(tài)規(guī)劃算法中靈活地運用貪心思想，關(guān)鍵在于對問題深入地分析和理解，從原始動態(tài)規(guī)劃模型入手，分析算法的整體結(jié)構(gòu)，然后巧妙地運用貪心思想解決原始動態(tài)規(guī)劃算法中的冗余，從而達到優(yōu)化算法的目的.

3.4小結(jié)

使用動態(tài)規(guī)劃方法進行算法設(shè)計時，對當前狀態(tài)的計算都是進行一些決策并引用相應(yīng)的已經(jīng)計算過的狀態(tài)，計算每個狀態(tài)所涉及的狀態(tài)數(shù)是決定動態(tài)規(guī)劃算法時間復(fù)雜度的一個重要因素.

以上針對不同類型的問題提出了相應(yīng)的優(yōu)化措施.當狀態(tài)轉(zhuǎn)移方程滿足四邊形不等式性質(zhì)時，對狀態(tài)之間關(guān)系進行分析，縮小了問題的最優(yōu)解集合；將已求解的狀態(tài)合理地組織以及將貪心思想運用于動態(tài)規(guī)劃算法中來減少每次狀態(tài)轉(zhuǎn)移所涉及的狀態(tài)數(shù)，算法優(yōu)化后的時間效率如表1所示.

表1　算法的時間復(fù)雜度比較

4狀態(tài)轉(zhuǎn)移時間的優(yōu)化

當問題的狀態(tài)轉(zhuǎn)移決策很復(fù)雜時，可以考慮用“細化狀態(tài)轉(zhuǎn)移”方式來減少問題整體狀態(tài)轉(zhuǎn)移的時間[19].“細化狀態(tài)轉(zhuǎn)移”就是將原問題中的一次復(fù)合決策細化為若干次相互聯(lián)系的子決策.這種問題的決策往往是復(fù)合決策，也就是由一些子策略組成，這種決策的規(guī)模很大，每一次狀態(tài)轉(zhuǎn)移花費的時間會很多[20].而現(xiàn)在將問題每一次的復(fù)合決策細化為若干次子決策，并在進行了每次子決策后給予判斷，只有在當前的子決策到達了最優(yōu)解后，后面的子決策才進行轉(zhuǎn)移(類似搜索算法里的“剪枝”策略).能運用這種優(yōu)化思想的問題必須滿足最優(yōu)化原理和無后效性，原問題的復(fù)合策略的每個子策略也需要滿足這兩個條件.也就是復(fù)合策略的每個子策略也需要是最優(yōu)的策略(最優(yōu)化原理).前面的子策略的結(jié)果不會影響到后面的子策略的決策(無后效性).

將復(fù)雜的狀態(tài)轉(zhuǎn)移細化是一種很好的優(yōu)化思想.優(yōu)化后，雖然問題中決策總數(shù)會有所增加(因為把復(fù)合的決策細化為子決策)，但是由于只有在子決策取得最優(yōu)解后才進行接下來的決策，因此問題中最終的決策時間會減少，算法的時間復(fù)雜度也會相應(yīng)降低.

5結(jié)語

本文對動態(tài)規(guī)劃算法的時間效率優(yōu)化措施進行了討論.對算法進行優(yōu)化的過程中，一方面要對問題的屬性進行深入地分析，找出問題的本質(zhì)；另一方面可以從原有算法的不足之處著手，不斷改進，不斷優(yōu)化.

運用動態(tài)規(guī)劃思想設(shè)計算法需要較強的創(chuàng)造力，動態(tài)規(guī)劃是一種思想，并沒有一個統(tǒng)一的標準狀態(tài)模型可供所有問題使用.實際問題不同，其動態(tài)規(guī)劃狀態(tài)模型可能完全不同，因此需要對具體的問題進行具體的分析.同樣，算法的優(yōu)化也具有很強的靈活性，本文所討論的只是一些常規(guī)優(yōu)化措施，高效的優(yōu)化方法需要在具體的問題中繼續(xù)深入挖掘.后續(xù)工作是將本文所提出的優(yōu)化措施運用到實際問題中.

參考文獻

[1]BellmanRE.Dynamicprogramming[M].Princeton:PrincetonUniversityPress, 1957:52-57.

[2]吳軍. 數(shù)學(xué)之美[M]. 北京：人民郵電出版社, 2012:115-117.

[3]李端，錢富才，李力，等. 動態(tài)規(guī)劃問題研究[J]. 系統(tǒng)工程理論與實踐，2007，27(8):56-64.

[4]SitarzS.Dynamicprogrammingwithorderedstructures:theory,examplesandapplications[J].FuzzySetsandSystems, 2010, 161:2623-2641.

[5]HuTC,MorgenthalerJD.Dynamicprogrammingandgraphoptimizationproblems[J].Computers&MathematicswithApplications, 1994,27(10):53-58.

[6]SniedovichM.Dynamicprogrammingandprinciplesofoptimality[J].JournalofMathematicalAnalysisandApplications, 1978,65(10): 586-606.

[7]FabioB.Dynamicprogrammingforsomeoptimalcontrolproblemswithhysteresis[J].NonlinearDifferentialEquationsandApplicationsNoDEA,2002,9:149-174.

[8]ShapiroA.Analysisofstochasticdualdynamicprogrammingmethod[J].EuropeanJournalofOperationalResearch, 2011,209(2):63-72.

[9]袁小玲，李心科. 基于雙向動態(tài)規(guī)劃質(zhì)量有保障的組合服務(wù)選取[J]. 合肥工業(yè)大學(xué)學(xué)報(自然科學(xué)版),2009,32(4):465-499.

[10]ChenS.Adynamicprogrammingimplementedresourcecompetitiongametheoreticmodel[J].EcologicalModeling, 2010,221:1847-1851.

[11]KnuthDE.Optinumbinarysearchtrees[J].ActaInformatica, 1971,1:14-25.

[12]CormenTH,LeisersonCE,RivestRL,etal.Introductiontoalgorithms[M].Massachusetts:TheMITPress, 2012:104-108.

[13]FavreB,PeuporterB.Applicationofdynamicprogrammingtostudyloadshiftinginbuildings[J].EnergyandBuildings, 2014,82:57-64.

[14]霍紅衛(wèi)，莊心谷. 實時系統(tǒng)資源分配的動態(tài)規(guī)劃算法[J]. 計算機學(xué)報, 1997,20(3):269-274.

[15]趙銅鐵鋼，雷曉輝，蔣云鐘，等. 水庫調(diào)度決策單調(diào)性與動態(tài)規(guī)劃算法改進[J]. 水利學(xué)報，2012,43(4):414-421.

[16]段鷹，段文澤. 大規(guī)模時滯系統(tǒng)的動態(tài)規(guī)劃模型與優(yōu)化算法[J]. 機械工程學(xué)報, 2007,43(4):217-223.

[17]WuYJ,WangL,ZhuDX,etal.AnefficientdynamicprogrammingalgorithmforthegeneralizedLCSproblemwithmultiplesubstringexclusiveconstraints[J].JournalofDiscreteAlgorithm, 2014,26:68-105.

[18]KatanyukulT,DuffWS,EdiwinKP,etal.Approximatedynamicprogrammingforaninventoryproblem:empiricalcomparison[J].ComputersIndustrialEngineer, 2011,60:719-743.

[19]張化光，張欣，羅艷紅，等. 自適應(yīng)動態(tài)規(guī)劃綜述[J]. 自動化學(xué)報，2013,39(4):303-311.

[20]張鵬. 連續(xù)型動態(tài)規(guī)劃的新算法研究[J]. 運籌學(xué)學(xué)報，2012,16(1):97-105.

TimeEfficiencyImprovementofDynamicProgrammingAlgorithm

Lan Wenfei, Wu Ziying, Li Qiang, Qiang Xiaoli

(CollegeofComputerScience,South-CentralUniversityforNationalities,Wuhan430074,China)

AbstractInthispaper,wetriedtooptimizethedynamicprogrammingalgorithminthreeaspectsoftimecomplexity,proposedthemeasurestoimprovetimeefficiency,andanalyzedthevalidityandcorrectnessofmeasuresintheory.Comparedwiththetraditionalalgorithm,thetimecomplexityoftheoptimizedalgorithmisimprovedtoacertainextent,andthedynamicprogrammingisfittedfortheproblemwithlarge-sizedata.

Keywordsdynamicprogramming；timeefficiency；optimization

收稿日期2016-01-14

作者簡介藍雯飛(1966-)，女，教授，研究方向：數(shù)據(jù)庫技術(shù)和軟件新技術(shù)，E-mail:lanwenfei1@163.com

基金項目國家自然科學(xué)基金資助項目(61379059)

中圖分類號TP391

文獻標識碼A

文章編號1672-4321(2016)02-0135-06