張立臣 王小明

摘? 要：?jiǎn)栴}解決能力是目前學(xué)生亟待提升的能力之一。圍繞動(dòng)態(tài)規(guī)劃算法教學(xué)，介紹了一種以問題解決能力目標(biāo)為導(dǎo)向的教學(xué)設(shè)計(jì)，通過調(diào)整教學(xué)內(nèi)容和教學(xué)過程，突出學(xué)生問題解決能力的培養(yǎng)和訓(xùn)練，為能力目標(biāo)導(dǎo)向的課程改革提供了一種新思路。

關(guān)鍵詞：?jiǎn)栴}解決能力;動(dòng)態(tài)規(guī)劃;算法設(shè)計(jì);教學(xué)設(shè)計(jì)

中圖分類號(hào)：G642? ? ? ?文獻(xiàn)標(biāo)志碼：A? ? ? ? ?文章編號(hào)：2096-000X（2021）11-0105-05

Abstract： Currently， it is urgent to promote students' problem solving ability. Focusing on the teaching mode on dynamic programming algorithm， a novel teaching design scheme is introduced oriented by the goal of problem solving ability. The proposed scheme tries to adjust the teaching contents and design process， in which the training and promotion process of the students' problem solving ability is emphasized， then providing a novel idea to the ability-oriented curriculum reform.

Keywords： problem-solving ability; Dynamic Programming; algorithm design; teaching design

目前，以學(xué)生為中心的教育改革，比如，OBE（Outcomes-Based Education， 成果導(dǎo)向教育）[1]、系統(tǒng)能力培養(yǎng)教育[2]、計(jì)算思維能力培養(yǎng)教育[3]、新工科背景下的教育改革等[4]，越來越突出學(xué)生的能力培養(yǎng)。根據(jù)學(xué)生現(xiàn)有能力水平和畢業(yè)應(yīng)具備的能力要求，教育改革要求教師反向設(shè)計(jì)教學(xué)內(nèi)容、教學(xué)模式、教學(xué)案例和教學(xué)評(píng)價(jià)方式。

算法設(shè)計(jì)與分析是計(jì)算機(jī)學(xué)科的一門專業(yè)核心課，主要培養(yǎng)學(xué)生計(jì)算思維能力以及實(shí)際計(jì)算問題解決能力[5]。這些能力對(duì)學(xué)生未來從事計(jì)算機(jī)相關(guān)的教學(xué)、科研和工程實(shí)踐活動(dòng)具有重要作用。因此，算法課程的教學(xué)研究和改革得到了廣泛關(guān)注，已出版了眾多案例豐富的算法教材，開發(fā)了大量在線算法課程。本文主要以算法課程中的“動(dòng)態(tài)規(guī)劃算法”教學(xué)為例，設(shè)計(jì)一種新的能力目標(biāo)導(dǎo)向的教學(xué)設(shè)計(jì)案例，突出培養(yǎng)和訓(xùn)練學(xué)生的問題解決能力，從而為能力目標(biāo)導(dǎo)向的課程改革提供教學(xué)案例參考和教學(xué)設(shè)計(jì)思路。

一、動(dòng)態(tài)規(guī)劃算法教學(xué)

動(dòng)態(tài)規(guī)劃算法解決的問題是最優(yōu)化問題，其基本思想是將待求解問題分解成若干子問題，通過對(duì)子問題的迭代求解，獲得待求解問題的最優(yōu)解[5]。與分治法不同，動(dòng)態(tài)規(guī)劃算法更適合那些經(jīng)分解得到的子問題不互相獨(dú)立的情形。在動(dòng)態(tài)規(guī)劃算法中，通過保存已解決子問題的解，可避免大量重復(fù)計(jì)算，進(jìn)而提高算法效率。

動(dòng)態(tài)規(guī)劃算法要求待求解問題具有2個(gè)重要性質(zhì)，即最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)是指，問題的最優(yōu)解可通過其所包含的子問題的最優(yōu)解計(jì)算得到;子問題重疊性質(zhì)是指，分解后的問題包含很多重復(fù)的子問題。通過記錄不同的子問題的解，可以大大減少求解子問題的次數(shù)。動(dòng)態(tài)規(guī)劃算法具有很多實(shí)際的應(yīng)用，因此成為算法課程中的一個(gè)難點(diǎn)和重點(diǎn)。

二、動(dòng)態(tài)規(guī)劃算法教學(xué)設(shè)計(jì)

通過動(dòng)態(tài)規(guī)劃算法教學(xué)，我們將突出訓(xùn)練和培養(yǎng)學(xué)生基于計(jì)算機(jī)解決問題的能力，主要包括：?jiǎn)栴}分析與建模能力、遞推方程的構(gòu)建能力、基于遞推方程尋找最優(yōu)解的能力、遞推方程的算法設(shè)計(jì)與編程實(shí)現(xiàn)能力、遞推方程的算法優(yōu)化與復(fù)雜度分析能力、遞推方程的算法實(shí)驗(yàn)分析能力。

（一）問題分析與建模

對(duì)實(shí)際問題進(jìn)行分析并建立形式化模型是基于計(jì)算機(jī)求解問題的首要任務(wù)，對(duì)學(xué)生的未來職業(yè)發(fā)展具有重要作用。發(fā)現(xiàn)問題比解決問題更為重要。正確建立問題的形式化模型往往意味著完成了問題求解的一半工作。問題分析與建模的關(guān)鍵在于如何選擇數(shù)學(xué)符號(hào)并運(yùn)用適當(dāng)?shù)墓矫枋鰡栴}，即定義問題的目標(biāo)和約束條件。我們以如下兩個(gè)最優(yōu)化問題作為動(dòng)態(tài)規(guī)劃算法的教學(xué)案例。

問題1（數(shù)組不相鄰元素的最大和問題） 在具有n個(gè)元素的數(shù)組中取出一個(gè)或多個(gè)不相鄰的元素，使其和最大。

問題2（0-1背包問題） 給定1個(gè)背包和一組物品，已知背包的容量以及每個(gè)物品的重量和價(jià)值，如何選擇裝入背包的物品，在不超過背包容量的前提下，使得所裝入背包的物品的總價(jià)值最大。

一般采用3個(gè)步驟對(duì)給定的問題進(jìn)行數(shù)學(xué)建模。步驟1. 確定問題中已知量和未知量的數(shù)學(xué)符號(hào);步驟2. 確定問題的優(yōu)化目標(biāo);步驟3. 確定問題的各個(gè)約束條件。

對(duì)于問題1，用符號(hào)a表示給定數(shù)組，n表示數(shù)組所含元素個(gè)數(shù)，a[i]則表示數(shù)組中第i個(gè)元素，i在1和n之間。用大小為n的數(shù)組x表示選擇了哪些元素，x[i]=1表示選擇了元素a[i]。然后，問題1的優(yōu)化目標(biāo)可表示為所選擇的元素的和最大，可用max？撞ia[i]·x[i]表示。該問題存在兩個(gè)約束，一是所選擇的元素互不相鄰，可用x[i]+x[i+1]？燮1表示， 其中，i∈{1，...，n-1}，另一個(gè)是x[i]的取值只能為0或1，以表示對(duì)應(yīng)第i個(gè)元素是否被選取，即x[i]∈{0，1}，i∈{1，...，n}。綜上，問題1的形式化模型可表示為：

同理，問題2的形式化模型可表示為：

其中，w[i]和v[i]分別表示物品i的重量和價(jià)值，B表示背包的容量，x[i]表示是否將物品i放入背包，即x[i]=1表示選擇了物品i，其中，i∈{1，...，n}。顯然，該問題的目標(biāo)是使得所選擇的物品的價(jià)值之和最大，約束1保證了裝入背包的物品的重量之和不超過背包的容量。

在此基礎(chǔ)上，繼續(xù)選擇一些代表性的問題作為課堂和課后練習(xí)，以訓(xùn)練和培養(yǎng)學(xué)生的問題分析及形式化模型構(gòu)建能力。常見的動(dòng)態(tài)規(guī)劃問題包括：

問題3（矩陣連乘問題）有n個(gè)矩陣進(jìn)行乘法運(yùn)算，如何通過給矩陣連乘時(shí)加括號(hào)，使得總的乘法次數(shù)最少。

問題4（加權(quán)區(qū)間值調(diào)度問題） 給定n個(gè)時(shí)間區(qū)間，每個(gè)時(shí)間區(qū)間包括一個(gè)開始時(shí)間和一個(gè)結(jié)束時(shí)間，還包括一個(gè)權(quán)重，如何選擇一些時(shí)間不重疊的時(shí)間區(qū)間，使得所選擇的時(shí)間區(qū)間的權(quán)重之和最大。

問題5（最大連續(xù)子序列和問題） 給定一個(gè)含n個(gè)元素的序列，請(qǐng)確定一個(gè)連續(xù)的子序列，使得這個(gè)子序列的和最大。

（二）遞推方程的算法設(shè)計(jì)與編程實(shí)現(xiàn)

考慮到遞推方程的構(gòu)建是動(dòng)態(tài)規(guī)劃算法教學(xué)的重點(diǎn)和難點(diǎn)，我們將該內(nèi)容放到最后重點(diǎn)講解。在此，我們將先給出一個(gè)遞推方程，然后，基于該遞推方程講解對(duì)應(yīng)問題的算法設(shè)計(jì)與編程實(shí)現(xiàn)，從而培養(yǎng)和提高學(xué)生能夠基于所構(gòu)建的遞推方程設(shè)計(jì)相應(yīng)的算法并能夠編程實(shí)現(xiàn)的能力。事實(shí)上，通過之前學(xué)習(xí)程序設(shè)計(jì)語言課程，學(xué)生已接觸過基于遞推方程的算法設(shè)計(jì)和編程訓(xùn)練。我們將通過兩個(gè)簡(jiǎn)單示例對(duì)學(xué)生進(jìn)行啟發(fā)式教學(xué)。

遞推方程1（數(shù)的階乘）整數(shù)n的階乘的遞推方程為：

其中，F(xiàn)（i）表示整數(shù)i的階乘，i∈{1，...，n}，因此，整數(shù)n的階乘為F（n）。

遞推方程2（最大值）n個(gè)元素中的最大值的遞推方程為：

其中，M（i）表示n個(gè)元素中的前i個(gè)元素的最大值，i∈{1，...，n}，因此，n個(gè)元素中的最大值為M（n）。

遞推方程3（斐波那契數(shù)列）遞推方程為：

其中，F(xiàn)（i）表示斐波那契數(shù)列的第i個(gè)元素的值，i∈{1，...，n}。

選擇以上簡(jiǎn)單示例的原因是學(xué)生已在程序設(shè)計(jì)語言課程學(xué)習(xí)中掌握了求解這些問題的算法設(shè)計(jì)方案，從而通過總結(jié)這些方案，可以得出通用的基于遞推方程設(shè)計(jì)相應(yīng)算法的方法和步驟。顯然，遞推方程一般存在兩個(gè)方案，一個(gè)采用遞歸策略，另一個(gè)采用迭代策略。通過分別給出并分析遞推方程的兩種算法設(shè)計(jì)方案，可以使學(xué)生加深這兩種策略的理解。遞推方程1、2和3的遞歸和迭代算法分別用表1、表2和表3描述。

（三）遞推方程的算法優(yōu)化與復(fù)雜度分析

算法時(shí)間復(fù)雜度分析與算法優(yōu)化能力是需要學(xué)生掌握的重要能力。我們將分別對(duì)上述遞推方程的兩種算法進(jìn)行時(shí)間復(fù)雜度分析，得出：這三個(gè)算法的迭代算法的時(shí)間復(fù)雜度均為O（n），前兩個(gè)問題的遞歸算法的時(shí)間復(fù)雜度也為O（n），而第3個(gè)問題的遞歸算法的時(shí)間復(fù)雜度為O（2n），其中n是元素個(gè)數(shù)。

需要指出的是，（1）基于遞推方程設(shè)計(jì)遞歸算法較

為直接和簡(jiǎn)單，但由于遞歸算法的調(diào)用需要消耗大量的系統(tǒng)資源而導(dǎo)致其效率較迭代算法低很多。特別地，對(duì)于斐波那契數(shù)列問題，雖然不同的子問題的個(gè)數(shù)只有n個(gè)，但遞歸算法卻需要計(jì)算很多重復(fù)的子問題（2n個(gè)）。比如，在計(jì)算F（n）時(shí)需要計(jì)算F（n-1）和F（n-2），而在計(jì)算F（n-1）的過程中，又需要再次計(jì)算F（n-2），導(dǎo)致算法時(shí)間復(fù)雜度極高。通過公式推導(dǎo)，可得出其算法時(shí)間復(fù)雜度為指數(shù)級(jí)的。（2） 遞歸算法是一種很自然的算法，對(duì)于包含很多重復(fù)子問題的計(jì)算問題，可引導(dǎo)學(xué)生通過“備忘錄方法”解決，即將計(jì)算的子問題的結(jié)果暫時(shí)保存在某個(gè)數(shù)據(jù)結(jié)構(gòu)（一般是數(shù)組）中。每當(dāng)需要計(jì)算時(shí)，首先檢索該子問題是否已保存，若是，則直接返回結(jié)果，否則，將進(jìn)行計(jì)算并保存結(jié)果。經(jīng)“備忘錄方法”改進(jìn)的斐波那契數(shù)列的遞歸算法如表4所示（注：定義全局?jǐn)?shù)組a，初始值將a[1]，a[2]設(shè)為1，其他元素設(shè)為0）。

經(jīng)過深入分析，進(jìn)一步得出如下結(jié)論。雖然表4中的“備忘錄方法”可以使得遞歸算法中的子問題計(jì)算次數(shù)減少至n，但其遞歸調(diào)用次數(shù)沒有得到改變。因此，我們還可以對(duì)上述算法進(jìn)一步改進(jìn)，以減少遞歸調(diào)用次數(shù)，其基本思路是在調(diào)用遞歸函數(shù)時(shí)，首先檢查是否以保存小問題的解。由此，得到如表5所示的較完美的遞歸算法，雖然該算法的被調(diào)用次數(shù)仍大于n（經(jīng)分析，被調(diào)用次數(shù)約為n的2倍）。

通過上述3個(gè)遞推方程的算法設(shè)計(jì)、分析與優(yōu)化，我們可得出對(duì)于遞推方程的兩種動(dòng)態(tài)規(guī)劃算法解決方案：一種稱為“備忘錄方法”的基于遞歸算法解決方案，其存在設(shè)計(jì)簡(jiǎn)單但效率較低的特點(diǎn);一種為基于迭代算法的解決方案，其通過存儲(chǔ)小問題的解逐步構(gòu)造和計(jì)算大問題的解，具有高效的優(yōu)點(diǎn)。

（四）遞推方程的構(gòu)建與算法設(shè)計(jì)

采用啟發(fā)式策略與學(xué)生一起尋找上述問題1和問題2的遞推方程，并依據(jù)上述知識(shí)進(jìn)行算法設(shè)計(jì)、分析和優(yōu)化。構(gòu)造最優(yōu)化問題的遞推方程的關(guān)鍵是確定大問題的最優(yōu)解與其包含的某個(gè)或某些小問題的最優(yōu)解之間的關(guān)系。因此，如何用符號(hào)描述某個(gè)子問題的最優(yōu)解是構(gòu)建遞推方程的前提。我們將引導(dǎo)學(xué)生采用試探方法描述子問題的最優(yōu)解及其之間的遞推方程。例如，針對(duì)問題1，我們用F（i）表示n個(gè)元素中前i個(gè)元素所構(gòu)成的子問題的最優(yōu)解所對(duì)應(yīng)的目標(biāo)值，即，如何選擇前i個(gè)元素中的某些不相鄰的數(shù)，使得這些數(shù)的和最大，該和就是F（i）的值。顯然，原問題的優(yōu)化目標(biāo)可表示為F（n），而F（1）顯然就是a[1]的值。對(duì)于選擇問題的常見的遞推方程的構(gòu)建方法是考慮是否選擇了某個(gè)數(shù)，在此問題中，可考慮F（i）的最優(yōu)解中是否包括第i個(gè)元素。分析可知：（1）如果最優(yōu)解中包括第i個(gè)元素，那么將導(dǎo)致其相鄰的左側(cè)（即第i-1個(gè)）元素不能被選取，此時(shí)，F(xiàn)（i）=a[i]+F（i-2），即前i-2個(gè)元素構(gòu)成的子問題的最優(yōu)解加上第i個(gè)元素就是前i個(gè)元素構(gòu)成的子問題的最優(yōu)解;（2）反之，如果不包括第i個(gè)元素，那么其相鄰的左側(cè)的第i-1元素可以被選取，因此，前i個(gè)元素構(gòu)成的子問題的最優(yōu)解就等于前i-1個(gè)元素構(gòu)成的子問題的最優(yōu)解。由于第i個(gè)元素是否在F（i）中只存在兩種情況，因此，可得出F（i）的如下遞推方程：

在此基礎(chǔ)上，可設(shè)計(jì)上述遞推方程的遞歸算法和迭代算法，如表6所示。

經(jīng)過分析，可知基于迭代算法的時(shí)間和空間復(fù)雜度均為O（n），而基于遞歸的算法可采用備忘錄方法進(jìn)一步改進(jìn)，改進(jìn)后的時(shí)間復(fù)雜度仍為O（n），但效率較低。

在此基礎(chǔ)上，啟發(fā)學(xué)生根據(jù)優(yōu)化目標(biāo)的計(jì)算過程尋找對(duì)應(yīng)的最優(yōu)解。需要強(qiáng)調(diào)的是，動(dòng)態(tài)規(guī)劃的迭代算法的設(shè)計(jì)采用“自下而上計(jì)算最優(yōu)解的目標(biāo)值、自上而下尋找最優(yōu)目標(biāo)對(duì)應(yīng)的最優(yōu)解”思想。所謂“自下而上”是指通過小問題的最優(yōu)解計(jì)算大問題的最優(yōu)解，而“自上而下”是指通過大問題的最優(yōu)解尋找小問題的最優(yōu)解。對(duì)于問題1，最終的最優(yōu)解存儲(chǔ)在v[n]中，而根據(jù)表6的迭代算法可知，v[n]的計(jì)算是通過比較a[j]+v[j-2]和v[j-1]的大小得到的，因此，通過構(gòu)建一個(gè)循環(huán)可得出最優(yōu)解所包含的元素，其對(duì)應(yīng)的偽代碼如表7所示，數(shù)組x中等于1的元素的下標(biāo)所對(duì)應(yīng)的元素就是被選擇的元素。

問題2的遞推方程的構(gòu)建過程較上述問題復(fù)雜一些。我們將首先嘗試簡(jiǎn)單的解決方案，在發(fā)現(xiàn)問題的基礎(chǔ)上，尋找正確的遞推方程。具體過程包括：首先，以F（i）表示在不超過背包容量B的前提下，選擇前i個(gè)物品中的某些物品（i？燮n）所得到的最大價(jià)值，即F（i）對(duì)應(yīng)的子問題是由前i個(gè)物品及容量為B的背包構(gòu)成的。然后，分析F（i）所對(duì)應(yīng)的最優(yōu)解中是否包括第i個(gè)物品，根據(jù)前文敘述，初步構(gòu)造的F（i）遞推方程為：

但是，上述遞推方程的第3個(gè)公式是錯(cuò)誤的。因?yàn)镕（i-1）顯然小于F（i-1）+v[i]，這意味著在第i個(gè)物品的重量不超過背包容量時(shí)，一定會(huì)裝入背包。導(dǎo)致出現(xiàn)該錯(cuò)誤的原因在于，在第i個(gè)物品的重量不超過背包容量時(shí)，如果選擇將該物品裝入背包，實(shí)際上將導(dǎo)致背包的可用容量變小，即第i個(gè)物品的重量將消耗背包的部分容量。但是，上述遞推方程并沒有考慮背包容量的變化。因此，為解決該問題，應(yīng)該將背包的容量考慮進(jìn)去?；谏鲜隹紤]，我們以符號(hào)F（i，W）表示在不超過背包容量W的前提下，選擇前i個(gè)物品中的某些物品（i？燮n）所得到的最大價(jià)值，即F（i，W）對(duì)應(yīng)的子問題是由前i個(gè)物品及容量為W的背包構(gòu)成的。在此基礎(chǔ)上，可構(gòu)造F（i，W）的正確的遞推方程為：

在此基礎(chǔ)上，采用二維數(shù)組a存儲(chǔ)中間結(jié)果，可設(shè)計(jì)上述遞推方程的遞歸算法和迭代算法，如表8所示。

顯然，函數(shù)F（n，B）將返回原背包問題的最優(yōu)解對(duì)應(yīng)的價(jià)值。在此基礎(chǔ)上，可引導(dǎo)學(xué)生構(gòu)造如表9的算法偽代碼，以獲得背包問題的最優(yōu)解，其中，數(shù)組x中等于1的元素的下標(biāo)所對(duì)應(yīng)的元素就是被選擇的元素。

經(jīng)過分析，可知基于迭代算法的時(shí)間和空間復(fù)雜度均為O（n*B）。在此基礎(chǔ)上，可繼續(xù)分析0-1背包問題的動(dòng)態(tài)規(guī)劃算法的優(yōu)缺點(diǎn)，并可對(duì)算法進(jìn)行改進(jìn)，以進(jìn)一步降低算法的空間復(fù)雜度。

三、結(jié)束語

本文以培養(yǎng)學(xué)生問題解決能力為目標(biāo)，以算法課程中的動(dòng)態(tài)規(guī)劃算法教學(xué)為例，提出了一種新的教學(xué)案例設(shè)計(jì)思路，以啟發(fā)式、探究式教學(xué)方法，從易到難，逐步解決實(shí)際問題，突出訓(xùn)練和培養(yǎng)學(xué)生的問題分析與建模能力、遞推方程的構(gòu)建能力、基于遞推方程尋找最優(yōu)解的能力、遞推方程的算法設(shè)計(jì)與編程實(shí)現(xiàn)能力、遞推方程的算法優(yōu)化與復(fù)雜度分析能力、遞推方程的算法實(shí)驗(yàn)分析能力。這將為以能力目標(biāo)導(dǎo)向的算法課程教學(xué)改革提供新思路，為培養(yǎng)學(xué)生未來職業(yè)發(fā)展所需問題解決能力提供教學(xué)設(shè)計(jì)案例。

參考文獻(xiàn)：

[1]吳勁，周帆，王瑞錦，等.OBE模式下的程序設(shè)計(jì)與算法基礎(chǔ)課程改革探索[J].計(jì)算機(jī)教育，2019（11）：86-90.

[2]張文宇，劉鵬，陳衛(wèi)衛(wèi)，等.面向系統(tǒng)能力培養(yǎng)的計(jì)算機(jī)專業(yè)課程教學(xué)評(píng)價(jià)研究[J].計(jì)算機(jī)教育，2019（2）：107-111.

[3]李玲.以培養(yǎng)計(jì)算思維為導(dǎo)向的高中《算法與程序設(shè)計(jì)》教學(xué)案例設(shè)計(jì)[D].沈陽師范大學(xué)，2016.

[4]王玉柱，張玉清，季曉慧，等.新工科理念下高性能計(jì)算導(dǎo)論課程內(nèi)容與實(shí)踐教學(xué)的探索[J].教育教學(xué)論壇，2019（25）：97-98.

[5]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析（第4版）[M].電子工業(yè)出版社，2012.