算法設(shè)計(jì)和研究課程中最大子段與問(wèn)題教學(xué)探析

1、算法設(shè)計(jì)和研究課程中最大子段與問(wèn)題教學(xué)探析摘要介紹算法設(shè)計(jì)與分析課程中最大子段和問(wèn)題的動(dòng)態(tài)規(guī)劃解法，其求解思想是先求給定序列中以每一個(gè)元素為尾元素的最大子段和，然后其中的最大者便是整個(gè)序列的最大子段和。從兩個(gè)不同的角度分析最大子段和問(wèn)題最優(yōu)解的構(gòu)造方法，給出最大子段和問(wèn)題的動(dòng)態(tài)規(guī)劃算法，并分析算法的時(shí)間復(fù)雜度。通過(guò)這一問(wèn)題的講解，有助于學(xué)生明確動(dòng)態(tài)規(guī)劃方法的解題步驟,掌握動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)步驟。關(guān)鍵詞最大子段和；動(dòng)態(tài)規(guī)劃；時(shí)間復(fù)雜度中圖分類號(hào)：g642. 4文獻(xiàn)標(biāo)識(shí)碼：b文章編號(hào):1671-489x (2013) 27-0050-03最大子段和問(wèn)題出自于2005年浙江大學(xué)計(jì)算機(jī)專業(yè)研 究生入學(xué)

2、考試計(jì)算機(jī)專業(yè)基礎(chǔ)綜合試題，它是一個(gè)典型的最 優(yōu)化問(wèn)題。該問(wèn)題描述為：給定由n個(gè)整數(shù)(可能為負(fù)整數(shù)) 組成的序列al, a2, . . . , an,其中， ai, ai+1,.,aj-1, aj (lwiwjwn)稱為序列 al，a2, . . . , an 的一個(gè)子段， 顯然子段中的元素是連續(xù)的，該子段中所有整數(shù)的和稱為該 子段的和。對(duì)于序列al, a2, . . . , an來(lái)說(shuō)，它有很多不同的子段，每個(gè)子段都有一個(gè)和，要求出該序列的各個(gè)子段的 和的最大值，當(dāng)序列中所有整數(shù)均為負(fù)整數(shù)時(shí)定義其最大子 段和為ol-2。該問(wèn)題的解法有多種，筆者在算法設(shè)計(jì)與分析課程的授 課過(guò)程中，針對(duì)該問(wèn)題給出

3、了三種求解方法，分別是枚舉法、 分治法和動(dòng)態(tài)規(guī)劃方法。用枚舉法求最大子段和問(wèn)題，時(shí)間 復(fù)雜度為0 (n2)；用分治法求最大子段和問(wèn)題，其算法的時(shí) 間復(fù)雜度可以降到0 (nlog2n)；而如果用動(dòng)態(tài)規(guī)劃方法求解 最大子段和問(wèn)題，其時(shí)間復(fù)雜度僅為0 (n),效率要比枚舉 法和分治法高很多。這里主要探討該問(wèn)題的動(dòng)態(tài)規(guī)劃解法， 包括求解該問(wèn)題的最優(yōu)值和構(gòu)造該問(wèn)題的最優(yōu)解，最優(yōu)值是 指給定序列的最大子段和是多少，最優(yōu)解是指和最大的子段 是哪一個(gè)子段。1求解最大子段和問(wèn)題的一種新思路設(shè)al： n是一個(gè)含有n個(gè)元素的整型數(shù)組，用al an這n個(gè)單元來(lái)存儲(chǔ)n個(gè)整數(shù)，a0空閑不用。對(duì)于數(shù)組a來(lái)說(shuō)，它有許多不同的

4、子段，每個(gè)子段都有 唯一的一個(gè)首元素，也有唯一的一個(gè)尾元素。那么對(duì)于數(shù)組 a來(lái)說(shuō)，它的所有子段的尾元素的下標(biāo)位置的范圍是從1到 n的，即子段的尾元素的下標(biāo)位置可以是1,這時(shí)這個(gè)子段 就是由al本身構(gòu)成的，子段的尾元素的下標(biāo)位置也可以是 2,依此類推，子段的尾元素的最后一個(gè)下標(biāo)位置是n。因此 可將數(shù)組a的所有子段分成n種，第一種是以數(shù)組元素al 為尾元素的子段，第二種是以數(shù)組元素a2為尾元素的子 段，依此類推，第n種是以數(shù)組元素an為尾元素的子段。 顯然每種子段都有一個(gè)最大子段和，那么數(shù)組a的最大子段 和就是這n個(gè)最大子段和中的最大者。因此可先求以數(shù)組元素al為尾元素的最大子段和，再 求以數(shù)組元

5、素a2為尾元素的最大子段和，依此類推，一直 求到以數(shù)組元素an為尾元素的最大子段和，則整個(gè)數(shù)組的 最大子段和就是這n個(gè)最大子段和中的最大者。若用數(shù)組元 素bj來(lái)表示以數(shù)組元素aj為尾元素的最大子段和，則 整個(gè)數(shù)組的最大子段和就是，于是求整個(gè)數(shù)組的最大子段和 就轉(zhuǎn)化為求各個(gè)bjo下面來(lái)討論如何用動(dòng)態(tài)規(guī)劃方法求 bj o2用動(dòng)態(tài)規(guī)劃方法求bj動(dòng)態(tài)規(guī)劃方法求解問(wèn)題的第一步就是分析最優(yōu)解的性 質(zhì)，并刻畫(huà)它的結(jié)構(gòu)特征，也就是證明這個(gè)問(wèn)題具有最優(yōu)子 結(jié)構(gòu)性質(zhì)，即證明問(wèn)題的最優(yōu)解中是否包含了子問(wèn)題的最優(yōu) 解。2. 1最優(yōu)子結(jié)構(gòu)性質(zhì)假設(shè)子段as, as+l,，aej-1, aj是以 aj 為尾元素的最大子段，

6、也就是說(shuō)bj = o那么必有子段as,as+l,，aj-l定是以aj-l為尾元素的最大 子段，也就是說(shuō)必有bj-l = o假設(shè)子段as, as+l,，aj-l不是以 ajt 為尾元素的最大子段，以aj-l為尾元素的最大子段是 ar, ar+1,，aj-l, r或大于s或小于s,則必有。只要在子段ar, ar+l,，ajt的后面加上一個(gè) 元素aj,就能得到另外一個(gè)以aj為尾元素的子段ar, ar+l,，aj-l, aj,這個(gè)子段的和可表示為+aj,顯然有 +aj>+aj=bj。這里假設(shè)aj不為0,這顯然與bj 是以aj為尾元素的最大子段和相矛盾，也就是與假設(shè)的 as, as+l,，aj是以

7、 aj為尾元素的最 大子段相矛盾。因此，如果as, as+l,，aj-1, aj是以aj為尾元素的最大子段，那么就必有 as,as+l,，aj-l定是以aj-l為尾元素的最大 子段，即問(wèn)題的最優(yōu)解中包含了子問(wèn)題的最優(yōu)解，最優(yōu)子結(jié) 構(gòu)性質(zhì)成立。2.2建立bj的遞推關(guān)系對(duì)于本問(wèn)題來(lái)說(shuō)，建立最優(yōu)值的遞推關(guān)系就是建立bj 與bj-l之間的關(guān)系。在證明最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，其實(shí)已經(jīng) 給出了 bj與bj-l之間的關(guān)系，bj其實(shí)就比bj-l多 了一個(gè)aj,但這里還需要根據(jù)bj-1的數(shù)值特性將此關(guān) 系式細(xì)化，因?yàn)樽佣蔚暮蚥j-l可以為正，可以為負(fù)，也可 以為零3：如果 bj-l>0,則 bj二bj-l+aj；如果bj-l 2.3以自底向上的方式計(jì)算各個(gè)bj所謂自底向上方式是指由最小子問(wèn)題的解構(gòu)造較小子 問(wèn)題的解，由較小子問(wèn)題的解構(gòu)造較大子問(wèn)題的解，由較大 子問(wèn)題的解構(gòu)造最大問(wèn)題的解。對(duì)于這個(gè)問(wèn)題來(lái)說(shuō)，最小的 子問(wèn)題就是bl,而由bj滿足的遞推關(guān)系式可知，求bl 時(shí)需要判斷b0的數(shù)值特性，由于bl表示的是以al