石少儉 張弘 石崢

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

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

中圖分類號(hào)：0158 文獻(xiàn)標(biāo)識(shí)碼：A

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

文章編號(hào)：1009-3044（2020）18-0048-02

1 引言

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

2 算法思想

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

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

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

定義3.[5]為每個(gè)解過(guò)的子問(wèn)題建立了備忘錄，這種方法稱為備忘錄方法。

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

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

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

4 應(yīng)用

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

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

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

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

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

解題思路：設(shè)n條直線的交點(diǎn)數(shù)為p（n），考慮它的子問(wèn)題，p（k），k

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

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

例3.最大子段和問(wèn)題：給定由n個(gè)整數(shù)（包含負(fù)整數(shù)）組成的序列a1，a2，…，an，求該序列子段和的最大值。當(dāng)所有整數(shù)均為負(fù)值時(shí)定義其最大子段和為0。

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

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

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

5 總結(jié)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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