動(dòng)態(tài)規(guī)劃算法研究

【摘要】動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題，在這類問(wèn)題中，可能會(huì)有許多可行解，每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。本文主要研究動(dòng)態(tài)規(guī)劃算法的特點(diǎn)、基本思想以及其解決問(wèn)題的具體步驟，詳細(xì)分析其用于解決矩陣連乘問(wèn)題的上的算法設(shè)計(jì)，并給出算法實(shí)現(xiàn)。

【關(guān)鍵詞】動(dòng)態(tài)規(guī)劃；矩陣連乘問(wèn)題；最優(yōu)子結(jié)構(gòu)；遞歸算法；重疊子問(wèn)題

1.動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃[1]是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)，提出了著名的最優(yōu)化原理，把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，逐個(gè)求解，創(chuàng)立了解決這類過(guò)程優(yōu)化問(wèn)題的新方法——?jiǎng)討B(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃問(wèn)世以來(lái)，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用，例如庫(kù)存管理、資源分配、設(shè)備更新、排序、裝載等問(wèn)題。

動(dòng)態(tài)規(guī)劃是一種將復(fù)雜的問(wèn)題分解為更小的、相似的子問(wèn)題，并存儲(chǔ)子問(wèn)題的解而避免計(jì)算重復(fù)的子問(wèn)題，以解決最優(yōu)化問(wèn)題的算法策略。

1.1 基本思想

動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往往不是相互獨(dú)立的，可以用一個(gè)表來(lái)記錄所有已解決的子問(wèn)題的答案，不管該子問(wèn)題以后是否被用到，只要它被計(jì)算過(guò)，就將其結(jié)果填入表中，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。[2]

1.2 求解問(wèn)題特征

動(dòng)態(tài)規(guī)劃算法的有效性依賴于問(wèn)題本身所具有的兩個(gè)重要性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊性質(zhì)。

1.2.1 最優(yōu)子結(jié)構(gòu)

原問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解，這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。在分析問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問(wèn)題的最優(yōu)解導(dǎo)出的子問(wèn)題的解不是最優(yōu)的，然后再設(shè)法說(shuō)明在這個(gè)假設(shè)下可構(gòu)造出比原問(wèn)題最優(yōu)解更好的解，從而導(dǎo)致矛盾。利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提。

1.2.2 子問(wèn)題重疊

遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次，這種性質(zhì)稱為子問(wèn)題的重疊性質(zhì)。動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問(wèn)題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。通常不同的子問(wèn)題個(gè)數(shù)隨問(wèn)題的大小呈多項(xiàng)式增長(zhǎng)。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。

1.3 設(shè)計(jì)步驟

3.總結(jié)

動(dòng)態(tài)規(guī)劃方法中每步所作的選擇往往依賴于相關(guān)子問(wèn)題的解，因而只有在解出相關(guān)子問(wèn)題后才能做出選擇所以動(dòng)態(tài)規(guī)劃，算法通常是以自底向上的方式解各子問(wèn)題的解進(jìn)而求出原問(wèn)題的解。動(dòng)態(tài)規(guī)劃是一種很靈活的算法設(shè)計(jì)方法，在動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)中，類似的技巧還有很多。要掌握動(dòng)態(tài)規(guī)劃的技巧，有兩條途徑：一是要深刻理解動(dòng)態(tài)規(guī)劃的本質(zhì)，這也是為什么一開(kāi)始就探討它的本質(zhì)的原因；二是要多實(shí)踐，不但要多應(yīng)用，還要學(xué)會(huì)從應(yīng)用中探尋規(guī)律，總結(jié)技巧。運(yùn)用動(dòng)態(tài)規(guī)劃算法解決的還有很多現(xiàn)實(shí)問(wèn)題，如背包問(wèn)題、最長(zhǎng)公共子序列問(wèn)題、凸多邊形最優(yōu)三角剖分問(wèn)題、電路布線等問(wèn)題，在本文中沒(méi)有介紹。動(dòng)態(tài)規(guī)劃算法雖然復(fù)雜，但只要掌握它的本質(zhì)特征并多加練習(xí)，就可以靈活運(yùn)用，并加以擴(kuò)展，來(lái)提高程序的時(shí)效性。

參考文獻(xiàn)

[1]百度百科.http：//baike.baidu.com

[2]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析（第四版）[M].北京：電子工業(yè)出版社，2012.

[3]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析（第四版）[M].北京：電子工業(yè)出版社，2012.

[4]GiliesBrassard等著.邱仲潘等譯.算法基礎(chǔ)（第1版）[M].北京：清華大學(xué)出版社，2005.