動(dòng)態(tài)規(guī)劃算法的時(shí)間效率改進(jìn)

藍(lán)雯飛，吳子瑩，李　強(qiáng)，強(qiáng)小利

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

?

動(dòng)態(tài)規(guī)劃算法的時(shí)間效率改進(jìn)

藍(lán)雯飛，吳子瑩，李強(qiáng)，強(qiáng)小利

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

運(yùn)用動(dòng)態(tài)規(guī)劃方法解決問(wèn)題，問(wèn)題的規(guī)劃模型為：

(1)

其中w(i,j)表示問(wèn)題中第i階段到第j階段的度量值和，這個(gè)度量在不同的問(wèn)題中含義不同，可以為利潤(rùn)、產(chǎn)量和資源的消耗等.f(i,j)表示問(wèn)題在(i,j)階段所處的狀態(tài)，狀態(tài)轉(zhuǎn)移方程的含義是將原問(wèn)題分解成兩個(gè)子問(wèn)題的形式，然后再進(jìn)行求解，相關(guān)問(wèn)題如最少矩陣鏈乘法[11]、最優(yōu)二叉查找樹[12]等問(wèn)題，都用到了這個(gè)狀態(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)化措施前，先給出兩個(gè)推論(其證明過(guò)程略).

推論1若函數(shù)w同時(shí)滿足區(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當(dāng)狀態(tài)函數(shù)f(a,b)滿足四邊形不等式性質(zhì)，定義v(a,b)為狀態(tài)f(a,b)取最小值時(shí)的決策，則有:

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

(4)

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

(5)

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

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

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

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

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

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

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

通過(guò)一個(gè)實(shí)例進(jìn)行說(shuō)明，問(wèn)題的規(guī)劃模型如下：

(6)

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

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

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

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

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

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

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

考慮問(wèn)題中狀態(tài)求解的過(guò)程：若狀態(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)，此時(shí)不必將狀態(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中，此時(shí)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)移過(guò)程中，可以用高效的查找算法——二分查找，這樣每次轉(zhuǎn)移的時(shí)間為O(log2n)，而每次狀態(tài)轉(zhuǎn)移涉及的狀態(tài)數(shù)僅為O(1).優(yōu)化后，增加了每次狀態(tài)轉(zhuǎn)移的時(shí)間(從O(1)到O(log2n))，但狀態(tài)轉(zhuǎn)移的數(shù)量卻減少了(由O(n)降為O(1)).這體現(xiàn)了在優(yōu)化過(guò)程中，時(shí)間效率影響因素之間的矛盾.優(yōu)化后，算法的時(shí)間復(fù)雜度為O(nlog2n)，因此，在總體上提高了算法的時(shí)間效率.

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

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

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

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

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

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

(8)

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

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

f(i,j)=

(9)

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

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

3.4小結(jié)

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

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

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

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

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

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

5結(jié)語(yǔ)

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

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

參考文獻(xiàn)

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

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

[3]李端，錢富才，李力，等. 動(dòng)態(tài)規(guī)劃問(wèn)題研究[J]. 系統(tǒng)工程理論與實(shí)踐，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]袁小玲，李心科. 基于雙向動(dòng)態(tài)規(guī)劃質(zhì)量有保障的組合服務(wù)選取[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(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)，莊心谷. 實(shí)時(shí)系統(tǒng)資源分配的動(dòng)態(tài)規(guī)劃算法[J]. 計(jì)算機(jī)學(xué)報(bào), 1997,20(3):269-274.

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

[16]段鷹，段文澤. 大規(guī)模時(shí)滯系統(tǒng)的動(dòng)態(tài)規(guī)劃模型與優(yōu)化算法[J]. 機(jī)械工程學(xué)報(bào), 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)動(dòng)態(tài)規(guī)劃綜述[J]. 自動(dòng)化學(xué)報(bào)，2013,39(4):303-311.

[20]張鵬. 連續(xù)型動(dòng)態(tài)規(guī)劃的新算法研究[J]. 運(yùn)籌學(xué)學(xué)報(bào)，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

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

基金項(xiàng)目國(guó)家自然科學(xué)基金資助項(xiàng)目(61379059)

中圖分類號(hào)TP391

文獻(xiàn)標(biāo)識(shí)碼A

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