動態規劃算法研究

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

【關鍵詞】動態規劃；矩陣連乘問題；最優子結構；遞歸算法；重疊子問題

1.動態規劃

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

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

1.1 基本思想

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

1.2 求解問題特征

動態規劃算法的有效性依賴于問題本身所具有的兩個重要性質：最優子結構性質和子問題重疊性質。

1.2.1 最優子結構

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

1.2.2 子問題重疊

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

1.3 設計步驟

3.總結

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

參考文獻

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

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

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

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