動態(tài)規(guī)劃算法的三式融合教學(xué)法案例研究

吳清壽，郭磊

（武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，武夷山 354300）

1 問題概述

《算法設(shè)計(jì)與分析》課程是計(jì)算機(jī)相關(guān)專業(yè)的核心課程，教學(xué)過程涉及算法基本思想的理解、算法的設(shè)計(jì)模式、算法的特性和算法的效率等環(huán)節(jié)，關(guān)聯(lián)的前導(dǎo)課程較多，要求學(xué)生具備較好的基礎(chǔ)知識和較強(qiáng)的分析能力。而與課程地位相悖的卻是課時的大量壓縮，現(xiàn)在各高校對本課程的課時安排一般都少于40節(jié)[1]，筆者所在學(xué)校對本課程的課時安排是32+8，即32節(jié)理論講解加上8課時的上機(jī)實(shí)踐。課時量不足與課程內(nèi)容較高的復(fù)雜度兩者之間的不均衡給教學(xué)造成了困難：知識點(diǎn)抽象層次較高，囿于課時無法深入分析；需要大量的實(shí)踐鞏固對算法思想的理解，但實(shí)踐課時通常很少甚至沒有；學(xué)生普遍缺乏將理論內(nèi)化為編程思想的能力。

動態(tài)規(guī)劃法是《算法設(shè)計(jì)與分析》課程的重要章節(jié)，也是歷屆學(xué)生普遍反映較難理解的內(nèi)容。本章節(jié)內(nèi)容除了具有課程本身的教學(xué)難處之外，其教學(xué)難點(diǎn)還體現(xiàn)在以下幾個方面：一是對算法的最優(yōu)子結(jié)構(gòu)性質(zhì)理解存在困難。不同問題，其最優(yōu)子結(jié)構(gòu)性質(zhì)的證明方法都不同，這是學(xué)習(xí)算法過程中的主要障礙。二是對算法的運(yùn)行過程難以理解。動態(tài)規(guī)劃算法通常以遞歸的方式定義其子問題的最優(yōu)解，而遞歸方法在思想上易于理解，但其執(zhí)行過程的分析存在較大的難度。三是無法做到學(xué)以致用[2]。學(xué)生可以通過課堂學(xué)習(xí)掌握相關(guān)例子的求解方法，但針對新的問題難以提出有效的算法過程。究其原因，主要是對算法的思想理解不透徹，對算法解決具體問題的過程掌握不清楚造成的。

文獻(xiàn)[3]從培養(yǎng)學(xué)生算法思維和提高應(yīng)用能力的角度提出了教學(xué)改革措施。文獻(xiàn)[4]從多個實(shí)例中抽象出動態(tài)規(guī)劃算法的特征。文獻(xiàn)[5]用改進(jìn)的動態(tài)規(guī)劃算法解決了背包問題。上述文獻(xiàn)從不同的角度對動態(tài)規(guī)劃算法進(jìn)行了研究，但未對學(xué)生如何更好掌握算法提出解決方法。

結(jié)合學(xué)生的實(shí)際情況，提出一種合理有效的教學(xué)方法，對學(xué)生掌握動態(tài)規(guī)劃算法的基本思想、基本性質(zhì)及其在具體問題上的分析方法是一件有必要有意義的工作。為此，筆者在多年教學(xué)《算法設(shè)計(jì)與分析》課程的過程中，提出了一種“三式融合”的教學(xué)模式，旨在促進(jìn)學(xué)生把握問題本質(zhì)，理解算法思想，提升實(shí)踐能力，做到學(xué)以致用。

2 三式融合教學(xué)法

要掌握動態(tài)規(guī)劃算法，首先要掌握其基本思想[6]。將原問題分解為相應(yīng)的子問題是分治法和動態(tài)規(guī)劃法的共同思路，而子問題是重復(fù)的還是相互獨(dú)立的決定了算法的選擇問題。為了便于后續(xù)更大規(guī)模問題的求解，動態(tài)規(guī)劃法通過引入填表法（或者稱備忘錄）記錄每個子問題的最優(yōu)解。先從極小的（即可直接求解的）子問題開始，將其解填充到備忘錄。逐步擴(kuò)大問題規(guī)模，當(dāng)前問題與子問題性質(zhì)相同，可通過查子問題的解構(gòu)造當(dāng)前問題的解，提高了算法效率，避免了子問題的重復(fù)求解過程。

從上述基本思想中可以看出，適用于動態(tài)規(guī)劃法求解的問題通常具有重復(fù)子問題性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。利用重復(fù)子問題性質(zhì)，解決了冗余計(jì)算問題，而最優(yōu)子結(jié)構(gòu)性質(zhì)確保問題求解的每一步驟都包含了子問題的最優(yōu)解。

基于以上基本思想，以0-1背包問題的求解過程為例，采用三式融合方法，給出問題求解步驟，推導(dǎo)出問題的遞歸關(guān)系式，將求解過程圖表化，從而自然得到算法的實(shí)現(xiàn)代碼。

三式融合教學(xué)法包含公式歸納，表格填充和代碼編寫三個部分。下面對三種方法予以介紹，并在下一章中結(jié)合具體的案例進(jìn)行分析。

（1）公式是本質(zhì)。動態(tài)規(guī)劃法中，利用重復(fù)子問題性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)可以定義解的遞歸公式，但解決一個新問題的遞歸公式的提出并不是顯而易見的，需要通過對問題進(jìn)行具體的分析之后再予以總結(jié)歸納而得出。

（2）圖表是手段。公式刻畫了問題的本質(zhì)，但求解過程仍然是抽象的。通過圖表的形式將求解過程具象化，能夠加深學(xué)生對問題的理解，獲得對問題的形象認(rèn)知，進(jìn)而對新問題能夠舉一反三，達(dá)到掌握算法的求解方法及本質(zhì)特征的效果。

（3）代碼是目的。算法的理解是前提條件，但最終還需將其轉(zhuǎn)化為程序代碼，獲得從分析問題到解決問題的能力，這是提出三式融合教學(xué)法的主要目的。利用公式抽象問題的本質(zhì)，利用圖表表征公式的求解步驟，依據(jù)表格的填充過程及方法，模擬出程序代碼，大大降低了程序設(shè)計(jì)的難度，且程序執(zhí)行結(jié)果易于驗(yàn)證，讓學(xué)生從中獲得編程的樂趣，并系統(tǒng)掌握程序設(shè)計(jì)的方法。

在實(shí)際教學(xué)過程中，三者不是獨(dú)立的，而是根據(jù)問題的特征，將三種方法交替使用，有機(jī)融合，讓學(xué)生在逐步分析問題的過程中掌握算法。

3 實(shí)例分析

本文以動態(tài)規(guī)劃解0-1背包問題為例。

案例數(shù)據(jù)：n=5，C=10，w={4，5，6，2，2}，v={6，4，5，3，6}，表示有5個物品，w表示第i個物品的重量，vi表示第i個物品的價值，1<=i<=5，C表示背包的容量。這是一個0-1背包問題，物品不能分割后裝入背包，只能選擇整個放入或不放入。目標(biāo)：要求裝入背包中的物品的總價值最大。

為了填充表格，先設(shè)一個二維數(shù)組m[i][j]，i（1<=i<=5）表示第i個物品，j（0<=j<=10）表示背包的當(dāng)前容量，m[i][j]表示當(dāng)背包容量為j時裝入前i個物品產(chǎn)生的最大價值。

步驟一：首先考慮當(dāng)背包的容量為0時，此時無法裝入任何物品，則產(chǎn)生的價值為0，可以得到公式（1）：

填充結(jié)果見表1中的第0列。

可用代碼描述如下：

步驟二：考慮第一個物品的裝入問題，設(shè)背包的容量為c，當(dāng)c小于w1，此時物品不能放入背包，產(chǎn)生的價值為0，從而得到公式（2）：

表格填充情況見表1中的m[1][1]～m[1][3]。

可用代碼描述如下：

當(dāng)背包容量等于或大于w1時，物品可以放入背包，則產(chǎn)生的價值為v1。因?yàn)楫?dāng)前只有一個物品，背包中物品的最大價值為v1。得到公式（3）：

表格填充情況見表1中的m[1][4]～m[1][10]。

對應(yīng)代碼如下：

步驟三：現(xiàn)在考慮有兩個物品的情況，當(dāng)背包剩余容量c

表格填充情況見表1中的m[2][1]～m[2][4]。

對應(yīng)代碼如下：

當(dāng)背包容量c>=w2時，第二個物品可以放入背包，也可以不放入，這需要根據(jù)是否能產(chǎn)生當(dāng)前最優(yōu)價值來決定。若物品2放入，產(chǎn)生價值v2，其對應(yīng)的背包總價值應(yīng)當(dāng)為前一步驟中未放入w2前對應(yīng)的背包（其容量為c-w2）中物品的總價值與v2之和，即m[i-1][cw2]+v2。若物品2不放入，則當(dāng)前的總價值為步驟二中對應(yīng)的背包（其容量為c）中物品價值的最優(yōu)值m[1][c]，取兩者最大值作為當(dāng)前容量下背包中的最大價值。由此，得到公式（5）：

表格填充情況見表1中的m[2][5]～m[2][10]。

對應(yīng)代碼如下：

以m[2][8]的填充為例。當(dāng)背包容量為8時，背包容量小于前兩個物品的重量之和，則只能選擇一個，第一個物品的價值大于第二個物品價值，所以選擇將第一個物品裝入背包，背包中的物品價值為6。其實(shí)際計(jì)算過程是m[1][c-w2]+v2=m[1][8-5]+v2=m[1][3]+4=0+4=4，可以看出，m[1][3]處未產(chǎn)生價值，即未裝入物品1，所以此處只裝入物品2。m[1][c]=m[1][8]=6，表示裝入物品1，產(chǎn)生價值為6，所以應(yīng)選擇6作為當(dāng)前背包的物品總價值。

步驟四：當(dāng)n>i>2時，其計(jì)算過程與步驟2相同，可得到通用公式：

表格填充情況見表1中的第3第4行。

代碼與步驟三相似，此處略。

步驟五：當(dāng)i=n時，因?yàn)閙[i][c]的值只與m[i-1][c]的值相關(guān)，所以此時無需完整計(jì)算整個過程，只需根據(jù)公式（7）計(jì)算c=C時的m[n][C]即可。

則 m[n][C]=max（15，11）=15

由上述步驟得到的完整表格如表1所示。

表1 0-1背包問題各步驟最優(yōu)值

由最優(yōu)值構(gòu)建最優(yōu)解的過程較為簡單，從m[n][C]開始搜索，如果m[i][c]>m[i-1][c]，說明在容量為c時，對于第i個物品，將其放入背包中將得到當(dāng)前的最優(yōu)解，則令xi=1，并縮小背包容量為c-wi，繼續(xù)對i-1個物品的放入情況即m[i-1][c-wi]進(jìn)行檢查，構(gòu)造最優(yōu)解。如果m[i][c]==m[i-1][c]，說明放入第i個物品無法產(chǎn)生新的更優(yōu)的解，則第i個物品不構(gòu)成最優(yōu)解，令xi=0，并由m[i-1][c]繼續(xù)構(gòu)造最優(yōu)解。重復(fù)以上過程。當(dāng)i等于1時，考慮構(gòu)建最優(yōu)值的步驟二中m[1][c]只有兩種取值：0 和 v1，所以，只要判斷 m[1][c]>0，則 x1=1，否則x1=0。表 1 中的 m[5][10]，m[4][8]，m[3][6]，m[2][6]，m[1][6]為最優(yōu)解的求解順序，其單元格右上角括號中的值即為 xi的值，可以看出 x={1，0，0，1，1}，即選擇物品 1，4，5，背包中的物品價值最大。

4 結(jié)語

從近幾年的教學(xué)情況可以看到，通過三式融合的教學(xué)方法，可以有效地幫助學(xué)生理解算法的基本思想，全面掌握算法的執(zhí)行情況，并能較容易的將分析過程轉(zhuǎn)化為程序代碼，提升了學(xué)生的實(shí)踐動手能力。另外，學(xué)生可以通過這種方法對比用不同算法解決同一問題的優(yōu)缺點(diǎn)，進(jìn)而提出算法的改進(jìn)措施，并能將其應(yīng)用到新的問題上。