蠻力法、分治法和動態(tài)規(guī)劃法求解最大子數(shù)組問題的思考

陳 艷，文曉棠

（廣州華商學(xué)院數(shù)據(jù)科學(xué)學(xué)院，廣州 510520）

0 引言

最大子數(shù)組問題是一個眾所周知的算法問題，在計算機(jī)科學(xué)、金融和工程等各個領(lǐng)域都有許多實(shí)際應(yīng)用。這個問題涉及到在一維數(shù)字?jǐn)?shù)組中找到具有最大和的連續(xù)子數(shù)組。有幾種方法可以解決這個問題，包括蠻力算法、分治算法和動態(tài)規(guī)劃算法［1］。在本文中，對這些方法進(jìn)行了比較，并提供了實(shí)驗(yàn)結(jié)果來分析它們的性能。本研究的目標(biāo)是確定解決最大子數(shù)組問題的最有效方法，并全面了解用于解決該問題的不同算法。

1 問題概述

假如我們有一個數(shù)組，數(shù)組中的元素有正數(shù)和負(fù)數(shù)，如何在數(shù)組中找到一段連續(xù)的子數(shù)組，使得子數(shù)組各個元素之和最大。

定義：數(shù)組中連續(xù)的一段序列稱為子數(shù)組。

定義：數(shù)組中元素和最大的非空子數(shù)組稱為最大子數(shù)組。詳細(xì)定義為：

輸入：給定一個數(shù)組X［1，2，…，n］，對于任意數(shù)組下標(biāo)為l，r（l≤r）的非空子數(shù)組，其和記為S（l，r）

輸出：求S（l，r）的最大值，記為Smax。

比如已知序列X=（-2，2，5，-7，-1，2，-4，3），求序列的最大子數(shù)組，正確的答案為X［2，3］，子數(shù)組和為7。本文將以此序列為例全面分析各種不同算法解決此問題。

2 蠻力算法

蠻力算法也稱為窮舉法或暴力法，它是算法設(shè)計中最常見的方法之一。蠻力算法的基本思路是對問題的所有可能狀態(tài)一一測試，直到找到解或?qū)⑷靠赡軤顟B(tài)都測試為止。蠻力法是一種簡單、直接地解決問題的方法，通常直接基于問題的描述和所涉及的概念定義來解決問題。蠻力算法是基于計算機(jī)運(yùn)算速度快這一特性，在解決問題時采用的一種“懶惰”策略。蠻力算法是學(xué)習(xí)算法的基礎(chǔ)，很多算法的優(yōu)化都是在蠻力算法的基礎(chǔ)上進(jìn)行的，因此想要熟練應(yīng)用各種算法策略，培養(yǎng)算法思維，必須對蠻力算法有深刻的認(rèn)識和熟練的應(yīng)用。

蠻力算法是解決最大子數(shù)組問題的一種簡單方法。它包括生成所有可能的子數(shù)組并計算它們的和。然后，返回具有最大和的子數(shù)組。已知序列如圖1所示。

圖1 序列X

圖2 求S3的思路

遍歷子數(shù)組X［l，2，…，r］的下標(biāo)，l的取值范圍：1～n，r的取值范圍：l～n，遍歷過程中對子數(shù)組元素求和，并記錄最大值Smax。

算法偽代碼如下：

該算法的時間復(fù)雜度為O（n3），因?yàn)樗枰蒼2個子數(shù)組并計算它們的和。

3 優(yōu)化的蠻力算法

根據(jù)上述算法，當(dāng)求S（i,j）時，通過來得到，求S（i，j+1）時，通過來得到，通過觀察發(fā)現(xiàn)，S（i，j+1）的求解包含著子問題S（i,j）的求解，如果能利用S（i,j）的解來求解S（i，j+1），則能改進(jìn)算法的效率。以此為優(yōu)化的目標(biāo)，設(shè)計優(yōu)化的蠻力算法如下：

通過上述改進(jìn)，減少了一層循環(huán)的應(yīng)用，算法的復(fù)雜度由O（n3）降為O（n2），效率提高了一個數(shù)量級。

4 分治法

分治算法的基本思想是將一個規(guī)模為N的問題分解為K個規(guī)模較小的子問題，這些子問題相互獨(dú)立且與原問題性質(zhì)相同［2］，求出子問題的解，通過合并的方式就可得到原問題的解。用分治法求解的問題具有如下基本特征：①該問題的規(guī)?？s小到一定的程度就可以容易地解決；②該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；③利用該問題分解出的子問題的解可以合并為該問題的解；④該問題所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公共的子子問題。

分治法求解問題的基本步驟分為三步［3-4］：

第一步：分解原問題。將原問題分解為兩個或多個與原問題性質(zhì)相同、規(guī)模更小的子問題，不同的問題分解的策略不一樣，比如二路歸并排序的分解策略是一分為二，快速排序的分解策略為利用數(shù)組劃分算法實(shí)現(xiàn)分解。

第二步：求解子問題。對子問題的求解分別調(diào)用一次遞歸即可，因?yàn)樽訂栴}本質(zhì)上和原問題性質(zhì)相同，只是規(guī)模變小而已。

第三步：合并子問題的解。通過對子問題的解進(jìn)行合并，可以得到原問題的解。此步反映了分治法具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，即原問題的解可以通過子問題的解組合得到。不同的是，對子問題的解合并方式不一樣，比如歸并算法需要有專門的合并算法來實(shí)現(xiàn)，而快速排序卻沒有嚴(yán)格意義上的合并過程。

分治算法是解決最大子數(shù)組問題的一種有效方法。該算法遞歸地將輸入數(shù)組分為兩半，得到兩個子問題，分別解決每個子問題的最大子數(shù)組問題，再求出跨左右兩個子問題的最大子數(shù)組，然后將解組合起來，由此得到原始數(shù)組的最大子數(shù)組。按照分治法解決問題的基本步驟具體設(shè)計思想如下：

（1）分解

將數(shù)組X［1，2，…，n］分為和從中間分成兩半，得到兩個子問題，即求解數(shù)組的最大子數(shù)組問題和求解數(shù)組的最大子數(shù)組問題。

（2）求解

遞歸求解上述兩個子問題，將結(jié)果分別記為S1，S2。

（3）合并

兩個子問題的解S1，S2可能是原問題的解，也可能不是原問題的解，因?yàn)檫€存在一個跨左右兩個子數(shù)組的最大子數(shù)組，記為S3。S3有個特點(diǎn)，它一定是包含左邊子問題的最后一個元素和右邊子問題的第一個元素，即跨中間點(diǎn)的最大子數(shù)組。不難理解，原問題的解在S1，S2和S3中，為Smax=max｛S1,S2,S3｝。顯然關(guān)鍵問題是求S3。

對于S3的求解，可以用蠻力法，但效率低，達(dá)到O（n2）的規(guī)模。設(shè)左邊子問題的最后一個元素下標(biāo)為m，則右邊子問題第一個元素下標(biāo)為m+1，如果分別求解出左邊以元素X［m］結(jié)尾的最大子數(shù)組，記為left；求出右邊以元素X［m+1］開始的最大子數(shù)組，記為right，則可順利求出S3=left+right。見圖。

以此為思路，設(shè)計求S3的算法getS3（X，low，mid，high），偽代碼如下：

算法中，求left的復(fù)雜度為O（mid），求right的復(fù)雜度為O（n-mid），則求S3的算法復(fù)雜度為O（n），顯然比直接蠻力法求S3的效率要高一個數(shù)量級。

分治法求解最大子數(shù)組問題的主算法Max-SubArray（X，low，high）偽代碼如下：

5 動態(tài)規(guī)劃法

動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，然后從這些子問題的解得到原問題的解［3］。與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到的子問題往往不是相互獨(dú)立的。也就是各個子問題包含公共的子子問題［4］。為了解決子問題重復(fù)計算的問題，動態(tài)規(guī)劃算法對每個子問題只計算一次，不管該子問題是否以后被用到，都將其結(jié)果保存到一張表中，從而避免每次遇到各個子問題時重新計算答案［5］。動態(tài)規(guī)劃通常應(yīng)用于求解最優(yōu)解問題，如0-1背包問題，最大子數(shù)組問題，矩陣鏈乘法問題等。

動態(tài)規(guī)劃法所能解決的問題一般具有以下幾個特征：①大問題可分解性。該問題可以分解為若干個規(guī)模較小的問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；②子問題易解決性。該問題的規(guī)模縮小到一定的程度就可以容易地解決；③解可合并性。利用該問題分解出的子問題的解可以組合為該問題的解；④子問題重疊性。當(dāng)計算出某個子問題的解時，后續(xù)多個問題都需要計算該子問題的解，所以計算出某個子問題的解，并將其保存，就節(jié)省了分治法重復(fù)計算的時間。

動態(tài)規(guī)劃算法求解問題的基本步驟分為四步：

第一步：問題結(jié)構(gòu)分析。分析問題的特點(diǎn)，結(jié)合問題的特點(diǎn)分析問題的結(jié)構(gòu)，找到合適的辦法來表示問題，進(jìn)而通過此表示方法來表示原問題。

第二步：遞推關(guān)系的建立。動態(tài)規(guī)劃算法的核心是填表，表中每個單元格代表一個子問題的解，每個單元格的解是通過其他子問題的解組合得到的，即動態(tài)規(guī)劃算法也要滿足最優(yōu)子結(jié)構(gòu)的性質(zhì)。因此要分析子問題之間的依賴關(guān)系，也即分析最優(yōu)子結(jié)構(gòu)性質(zhì)，由此得到子問題求解過程的組合方式，即遞推關(guān)系。

第三步：確定計算順序。對于填表的辦法，不同的問題填法不一樣，有的表從左向右自上而下來填，有的表需要從后往前填，有的甚至按對角線的方式從左向右填，具體的填表方式因問題性質(zhì)而異，需要通過第二步得到的子問題間的遞推關(guān)系來確定。

第四步：最優(yōu)方案的追蹤。通過第三步得到了問題的最優(yōu)值，對應(yīng)的最優(yōu)方案可以通過記錄填表時的決策過程，通過回溯的方式來得到。

動態(tài)規(guī)劃算法是解決最大子數(shù)組問題的另一種有效方法。該算法以數(shù)組中的每一個元素作為一個子數(shù)組的最后一個元素，向前遍歷求和。通過規(guī)律觀察發(fā)現(xiàn)，如果此元素的前一個子數(shù)組和為負(fù)，則以這個元素為最后一個元素的子數(shù)組的最大和為此元素本身；如果此元素之前的子數(shù)組和為正，則以這個元素為最后一個元素的子數(shù)組最大和為此元素本身加上前一個最大子數(shù)組和。每做一次子數(shù)組求和，就與前面出現(xiàn)的最大和作比較，如果此子數(shù)組大于前面的最大子數(shù)組，就將其賦值給最大值。若定義D［i］表示以X［i］結(jié)尾的最大的子數(shù)組和，則D［i］的求解如圖3所示。

圖3 求解D［i］的思路

按照此思路，根據(jù)動態(tài)規(guī)劃算法求解問題的基本步驟，設(shè)計如下：

問題結(jié)構(gòu)分析：

定義D［i］：表示以X［i］結(jié)尾的最大的子數(shù)組和，則原問題表示為Smax=max｛D［i］｝（1≤i≤n）。

遞推關(guān)系建立：

根據(jù)遞推關(guān)系的分析，D［i］實(shí)際上是一張一維表，故將原問題轉(zhuǎn)換為填D這張表的問題，如圖4所示。

圖4 表D的結(jié)構(gòu)

計算順序：

根據(jù)遞推式，將兩個子問題D［i］和D［i-1］在表中的位置關(guān)系表示出來，如圖5所示，通過觀察發(fā)現(xiàn)要求D［i］，需要先求D［i-1］，則得到此表的計算順序?yàn)閺淖蟮接业捻樞颍瓎栴}的解在表中的某個位置。如圖6所示。

圖5 D［i］和D［i-1］在表中的位置關(guān)系

圖6 計算順序

以此為思想，設(shè)計算法MaxSubjectarrayDP（X，n）偽代碼如下：

該算法用一層循環(huán)實(shí)現(xiàn)，時間復(fù)雜度為O（n），因?yàn)樗谳斎霐?shù)組中迭代一次，在恒定時間內(nèi)解決每個子問題。

6 算法對比實(shí)驗(yàn)

按上述設(shè)計實(shí)現(xiàn)這三種算法，并進(jìn)行對比測試。首先生成一些隨機(jī)數(shù)數(shù)組，數(shù)組規(guī)模從100 到100000000 不等。然后對每個數(shù)組運(yùn)行優(yōu)化的蠻力算法、分治算法和動態(tài)規(guī)劃算法，并計算它們所需的時間。測試結(jié)果見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)結(jié)果表明，對于較大的輸入大小，動態(tài)規(guī)劃算法優(yōu)于蠻力算法和分治算法。例如，對于大小為100000 的輸入數(shù)組，蠻力算法需要1 s 以上的時間來計算最大子數(shù)組，分治法需要1 ms，動態(tài)規(guī)劃法需要3 ms，此時，動態(tài)規(guī)劃法無優(yōu)勢；但數(shù)組規(guī)模到1000000，蠻力法已經(jīng)不是秒級，程序運(yùn)行時幾分鐘之內(nèi)未出結(jié)果，分治法18 s，動態(tài)規(guī)劃只需1 ms；數(shù)組規(guī)模到10000000 時，動態(tài)規(guī)劃法的優(yōu)勢更明顯，且隨著數(shù)組規(guī)模的增大，動態(tài)規(guī)劃的優(yōu)勢不斷增大。由此可見，分治算法比蠻力算法表現(xiàn)更好，但對于較大的輸入大小，仍然比動態(tài)編程算法花費(fèi)更長的時間。

7 結(jié)語

本文比較了解決最大子數(shù)組問題的不同方法，包括蠻力算法、分治算法和動態(tài)規(guī)劃算法。實(shí)驗(yàn)結(jié)果表明，動態(tài)規(guī)劃算法是解決這個問題的最有效方法，特別是對于大輸入量的情況。分治算法也是一個很好的替代方案，但它不如動態(tài)規(guī)劃算法有效。蠻力算法是一種基本的方法，只能應(yīng)用于較小的輸入大小?？傮w而言，動態(tài)規(guī)劃算法為最大子數(shù)組問題提供了最優(yōu)解，其時間復(fù)雜度為O（n）。