動態規劃算法的研究

石少儉 張弘 石崢

摘要：算法是計算機程序員必備的一項技術。動態規劃算法能解決具有最優子結構和重疊子問題的問題。通過構造合適的遞歸方程，利用動態規劃算法或者備忘錄方法解決問題。

關鍵詞：算法;動態規劃算法;最優子結構;重疊子問題

中圖分類號：0158 文獻標識碼：A

開放科學（資源服務）標識碼（OSID）：

文章編號：1009-3044（2020）18-0048-02

1 引言

算法，晦澀難懂，但又是IT領域最受重視的素養之一。動態規劃算法是一種比較抽象的算法。動態規劃法最早是在應用數學中被大家認同，由美國的著名數學家貝爾曼在研究應用數學的最優控制問題時提出的。動態規劃法有著廣泛的應用[1-4]。

2 算法思想

動態規劃算法的基本要素：最優子結構性質和子問題重疊性質。

定義1.[5]問題的最優解包含著其子問題的最優解。這種性質稱為最優子結構性質。

定義2.[5]把問題分解成子問題時，如果每次產生的子問題有一些是重復的，這種性質稱為子問題的重疊性質。

定義3.[5]為每個解過的子問題建立了備忘錄，這種方法稱為備忘錄方法。

利用動態規劃算法解決問題的基本步驟：首先由問題的定義分析問題是否具有最優子結構性質和重疊子問題的特性，如果問題有這兩個特性，該問題就可以利用動態規劃算法解決;利用最優子結構性質構造出最優值的遞推方程;利用動態規劃算法或者備忘錄方法進行求解。

3 與其他算法的聯系與區別

解決實際問題時，經常使用的經典算法除動態規劃算法外，還有分治算法和貪心算法，這些算法共同的特性是都具有最優子結構性質。動態規劃算法的本質特性是最優子結構性質和子問題的重疊性質。分治算法的本質特性是最優子結構性質和獨立子問題。所以判斷一個問題是用分治算法還是用動態規劃算法解決的根本點是原問題分解成子問題的重疊性。子問題沒有重疊的或者很少重疊的問題利用分治算法求解，重疊子問題多的問題利用動態規劃算法解決。貪心算法的本質特性是最優子結構性質和貪心選擇性質。問題如果具有貪心選擇性質，利用貪心算法解決。否則考慮利用分治算法或者動態規劃算法解決。

4 應用

例1.最少硬幣問題：設有n種不同面值的硬幣，各硬幣的面值存于數組T[1：n]中。現要用這些面值的硬幣來找錢。可以使用的各種面值的硬幣個數存于數組C[1：n]中，設計一個用最少硬幣找錢m的方法。

解題思路：問題最容易想到的解決方法是利用貪心算法，一個簡單例子：T[1，3]=[1，5，11]，m=15，貪心算法的最優解是5個硬幣，而問題的最優解為3個硬幣，所以最少硬幣問題不能用貪心算法解決。

規模為n的最少硬幣問題的解一定包含規模小于n的最少硬幣問題，所以問題具有最優子結構性質和子問題的重疊性質，利用動態規劃算法求解。

數學模型：設xi表示第i個面值硬幣所用的數量。

例2.平面直線交點問題：平面上有n條直線，且無三線共點，問這些直線能有多少種不同交點數。

解題思路：設n條直線的交點數為p（n），考慮它的子問題，p（k），k

遞歸方程：第n+l條直線與這n條直線相交的情況為：僅與這n條直線中的i條平行。p（n+I）=p（n -ij+（i -I）.（n-i ），i=0，l…k，利用該遞推方程，很容易地解決此問題。

例如n=5，P（5）=0，4，6，7，8，9，10。

例3.最大子段和問題：給定由n個整數（包含負整數）組成的序列a1，a2，…，an，求該序列子段和的最大值。當所有整數均為負值時定義其最大子段和為0。

解題思路：問題滿足最優子結構性質，不滿足貪心性質，考慮利用分治算法和動態規劃算法解決。

分治算法：將所給的序列a[1：n]分為長度相等的兩段a[1;n/2]和a[n/2+1：n]，分別求出這兩段的最大子段和，再合并成原問題的值。算法復雜性為T（n）= O（nlogn）。

由上面的問題的解決算法看到，可以用不種方式刻劃問題的最優子結構，動態規劃算法的效率比分治算法的效率要高。

5 總結

動態規劃算法能解決具有最優子結構和重疊子問題的問題。動態規劃算法解決問題的關鍵是構造合適的遞歸方程，好的遞歸方程能有效地提高算法的效率，然后利用動態規劃法或者備忘錄方法解決問題。

參考文獻：

[1]崔靜雅，侯亞林.關于動態分析問題的分析和應用[Jl.農家參謀，2019（15）：238.

[2]陳超，王飛，盛玉萍，等.移動云計算基于隨機數據模型的最優控制策略[J]-計算機工程與設計，2019，40（6）：1585-1589，1600.

[3]李小蓮.動態規劃法的應用分析[J].計算機時代，2019（6）：53- 55.

[4]來學偉.動態規劃法在TSP問題中的應用[Jl.吉林化工學院學報，2017，34（3）：65-67.

[5]王曉東.計算機算法設計與分析[M].5版，北京：清華大學出版社，2018.

【通聯編輯：王力】

作者簡介：石少儉（1965-），山東淄博人，碩士，副教授，主要研究方向：計算機算法、信息安全等。