動態(tài)規(guī)劃算法的研究

石少儉 張弘 石崢

摘要：算法是計算機程序員必備的一項技術(shù)。動態(tài)規(guī)劃算法能解決具有最優(yōu)子結(jié)構(gòu)和重疊子問題的問題。通過構(gòu)造合適的遞歸方程，利用動態(tài)規(guī)劃算法或者備忘錄方法解決問題。

關(guān)鍵詞：算法;動態(tài)規(guī)劃算法;最優(yōu)子結(jié)構(gòu);重疊子問題

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

開放科學（資源服務(wù)）標識碼（OSID）：

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

1 引言

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

2 算法思想

動態(tài)規(guī)劃算法的基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。

定義1.[5]問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。

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

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

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

3 與其他算法的聯(lián)系與區(qū)別

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

4 應(yīng)用

例1.最少硬幣問題：設(shè)有n種不同面值的硬幣，各硬幣的面值存于數(shù)組T[1：n]中?，F(xiàn)要用這些面值的硬幣來找錢?？梢允褂玫母鞣N面值的硬幣個數(shù)存于數(shù)組C[1：n]中，設(shè)計一個用最少硬幣找錢m的方法。

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

規(guī)模為n的最少硬幣問題的解一定包含規(guī)模小于n的最少硬幣問題，所以問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題的重疊性質(zhì)，利用動態(tài)規(guī)劃算法求解。

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

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

解題思路：設(shè)n條直線的交點數(shù)為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個整數(shù)（包含負整數(shù)）組成的序列a1，a2，…，an，求該序列子段和的最大值。當所有整數(shù)均為負值時定義其最大子段和為0。

解題思路：問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，不滿足貪心性質(zhì)，考慮利用分治算法和動態(tài)規(guī)劃算法解決。

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

由上面的問題的解決算法看到，可以用不種方式刻劃問題的最優(yōu)子結(jié)構(gòu)，動態(tài)規(guī)劃算法的效率比分治算法的效率要高。

5 總結(jié)

動態(tài)規(guī)劃算法能解決具有最優(yōu)子結(jié)構(gòu)和重疊子問題的問題。動態(tài)規(guī)劃算法解決問題的關(guān)鍵是構(gòu)造合適的遞歸方程，好的遞歸方程能有效地提高算法的效率，然后利用動態(tài)規(guī)劃法或者備忘錄方法解決問題。

參考文獻：

[1]崔靜雅，侯亞林.關(guān)于動態(tài)分析問題的分析和應(yīng)用[Jl.農(nóng)家參謀，2019（15）：238.

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

[3]李小蓮.動態(tài)規(guī)劃法的應(yīng)用分析[J].計算機時代，2019（6）：53- 55.

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

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

【通聯(lián)編輯：王力】

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