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

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

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

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

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

1.1 基本思想

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

1.2 求解問題特征

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

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

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

1.2.2 子問題重疊

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

1.3 設(shè)計步驟

3.總結(jié)

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

參考文獻

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

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

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

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