張立臣

（1.現(xiàn)代教學(xué)技術(shù)教育部重點實驗室，西安 710062；2.陜西省教學(xué)信息技術(shù)工程實驗室，西安 710119；3.陜西師范大學(xué)計算機(jī)科學(xué)學(xué)院，西安 710119）

0 引言

培養(yǎng)高層次人才一直是我國研究生培養(yǎng)的目標(biāo)之一，而較高的科研能力是高層次人才的基本特征[1]。因此，在本科階段開展規(guī)范的科研訓(xùn)練，有助于培養(yǎng)學(xué)生的基本科研素質(zhì)和科研能力，從而為其未來從事科研工作奠定基礎(chǔ)。目前，以學(xué)生為中心的本科生教育教學(xué)改革，越來越突出學(xué)生的能力培養(yǎng)[2]。這就促使大學(xué)教師積極更新教學(xué)內(nèi)容、教學(xué)模式、教學(xué)案例和教學(xué)評價方式，以培養(yǎng)學(xué)生包括科研能力在內(nèi)的諸多能力素養(yǎng)。

算法課程作為計算機(jī)學(xué)科的一門專業(yè)核心課程，尤其注重培養(yǎng)學(xué)生算法基本理論知識和計算思維、問題建模、算法設(shè)計與分析能力[3]。算法課程在計算機(jī)學(xué)科課程中地位十分重要，其關(guān)注的算法設(shè)計與分析能力對學(xué)生未來職業(yè)發(fā)展，尤其是從事科研和算法工程師等工作，具有重要意義。因此，針對算法課程的教育教學(xué)改革受到廣泛關(guān)注，相關(guān)教材、在線課程、算法競賽層出不窮。事實上，現(xiàn)有的算法課程改革主要關(guān)注于算法的設(shè)計與實現(xiàn)，一般提供算法偽代碼或程序源代碼，但在實驗對比和分析方面較為欠缺。由此導(dǎo)致的結(jié)果是，學(xué)生雖然可以設(shè)計并實現(xiàn)教師布置的算法問題，并能夠給出正確結(jié)果，但是，所給出的結(jié)果往往是某個特定問題實例的結(jié)果，通用性較差，缺乏不同規(guī)模下的問題實例的對比結(jié)果。相反，現(xiàn)有算法相關(guān)論文的實驗部分大都基于不同規(guī)模的問題實例開展對比實驗，并在此基礎(chǔ)上，分析實驗結(jié)果，評價算法優(yōu)劣。

針對上述問題，以0-1背包問題的教學(xué)為例，本文提出了一種新的算法課程教學(xué)模式，在問題建模和算法設(shè)計的基礎(chǔ)上，通過提供完整的編程框架和測試數(shù)據(jù)，將學(xué)生工作重心集中到算法核心代碼實現(xiàn)和實驗結(jié)果分析上；在此基礎(chǔ)上，提供矢量圖繪制模板，讓學(xué)生繪制實驗結(jié)果矢量圖并分析實驗結(jié)果。通過上述訓(xùn)練，有望培養(yǎng)學(xué)生基本的科研素質(zhì)和科研習(xí)慣，為其未來從事科研工作打下堅實基礎(chǔ)。

1 0-1背包問題概述

0-1背包問題是算法課程中動態(tài)規(guī)劃策略教學(xué)的重要內(nèi)容[4]。0-1背包問題是一個NP難問題，解決該問題具有重要的理論和實際意義。0-1背包問題可描述為：存在1個有限容量的背包和一組有限個數(shù)的物品，已知背包的容量以及每個物品的重量和價值，如何選擇裝入背包的物品，使得在不超過背包容量的前提下，裝入背包的物品的總價值最大。該問題的形式化數(shù)學(xué)模型可用0-1整數(shù)規(guī)劃模型描述：

其中，w[i]和v[i]分別表示物品i的重量和價值，B表示背包的容量，x[i]表示是否將物品i放入背包，x[i]=1表示裝入物品i，x[i]=0表示不裝入物品i，其中，i∈{1,…,n}。

現(xiàn)有教材一般采用動態(tài)規(guī)劃算法策略求解該問題，動態(tài)規(guī)劃算法適合那些經(jīng)分解得到的子問題不互相獨立的情形。0-1背包問題的動態(tài)規(guī)劃算法的遞推方程為：

其中，F(xiàn)（i,W）表示在不超過背包容量W的前提下，選擇前i個物品中的某些物品（i≤n）所得到的最大價值，即F（i,W）對應(yīng)的子問題是由前i個物品及容量為W的背包構(gòu)成的。

分析上述遞推方程，學(xué)生一般能夠通過循環(huán)、分支等語句完成程序源代碼編寫并調(diào)試運行。但是，這在實驗對比方面較為欠缺，學(xué)生一般不進(jìn)行不同問題規(guī)模下的實驗對比和分析。為此，我們針對該問題設(shè)計了新的教學(xué)模式，以訓(xùn)練和培養(yǎng)學(xué)生基本的實驗對比和分析能力。

2 聚焦實驗對比和分析的0-1背包問題教學(xué)模式

在對0-1背包問題進(jìn)行數(shù)學(xué)建模和動態(tài)規(guī)劃算法設(shè)計的基礎(chǔ)上，我們提供了實現(xiàn)該問題的編程框架和測試數(shù)據(jù)，以突出訓(xùn)練和培養(yǎng)學(xué)生的核心代碼編寫和實驗結(jié)果分析能力。

2.1 協(xié)作結(jié)對編寫算法核心代碼

協(xié)作結(jié)對編程是指兩個程序員共同完成同樣的編程任務(wù)，有助于減少學(xué)生的認(rèn)知負(fù)荷，提升學(xué)生的互動性和學(xué)習(xí)興趣[5]。學(xué)生自由組合結(jié)對，在課堂上共同操作一臺電腦完成核心代碼的編寫和調(diào)試。為了將學(xué)生聚焦于核心代碼編寫層面，我們設(shè)計了程序框架，并讓學(xué)生提前下載到電腦中。所提供的程序框架采用Java語言編寫，以Eclipse項目形式提供下載，0-1背包問題編程框架如下所示：

代碼塊1：文件Test.Java:

代碼塊2：文件Knapsack.Java

以上代碼提供了2個文件，其中，文件Test.Java用于產(chǎn)生輸入數(shù)據(jù)、輸出結(jié)果，文件Knapsack.Java用于解決0-1背包問題。在文件Test.Java中，定義了物品重量數(shù)組、物品價值數(shù)組和背包容量等全局變量，這些數(shù)據(jù)通過函數(shù)generate（）隨機(jī)產(chǎn)生，共產(chǎn)生10組數(shù)據(jù)，物品價值和重量在1至10之間，背包容量限制為物品總重量的0.8倍。第一組數(shù)據(jù)包括10個物品，然后以10的倍數(shù)增加物品數(shù)量。對每組產(chǎn)生的數(shù)據(jù)，將調(diào)用Knapsack類中的靜態(tài)方法solve（），該方法需要學(xué)生結(jié)對編程實現(xiàn)。此外，為了記錄動態(tài)規(guī)劃算法的時間，用數(shù)組ctime記錄處理每組數(shù)據(jù)所用的時間并輸出。一種可行的動態(tài)規(guī)劃源代碼如下所示。

代碼塊3：

開始時，學(xué)生將實驗次數(shù)num的值先設(shè)置為1，然后通過斷點或輸出以檢查所設(shè)計的算法是否正確，在正確的前提下，將實驗次數(shù)增加，記錄所需的時間。

2.2 分析實驗數(shù)據(jù)

在保證算法正確的前提下，學(xué)生分析實驗結(jié)果。通常，由于當(dāng)前電腦速度極快且數(shù)據(jù)規(guī)模較小，每組實驗所消耗的時間差別不大，有時實驗在某些規(guī)模下所耗時間反而降低。針對此問題，一般通過兩種方式實現(xiàn)。一種是調(diào)整實驗參數(shù)，通過增加數(shù)據(jù)規(guī)模，比如將物品的數(shù)量從300開始增加，依次增加300；一種是對每次實驗重復(fù)多次，取平均時間。此外，在實驗中也可以同時結(jié)合這兩種方式。

在此基礎(chǔ)上，分析影響實驗結(jié)果的因素。由于0-1背包問題的動態(tài)規(guī)劃算法的時間復(fù)雜度為O（n*B），其中n和B分別是物品的數(shù)量和背包的容量。因此，背包容量B也會影響算法性能，可以通過設(shè)置不同的背包容量，記錄實驗的運行時間，并作出適當(dāng)分析。

2.3 繪制矢量圖并分析實驗結(jié)果

圖和表格是常見的兩種實驗結(jié)果的呈現(xiàn)方式。鑒于圖更為直觀和常用，我們提供了矢量圖的繪制命令模板。首先，學(xué)生下載并安裝矢量畫圖工具Gnuplot（http://gnuplot.sourceforge.net/）；然后，將每組實驗記錄的運行時間數(shù)據(jù)按列形式存在數(shù)據(jù)文件中，如data.txt，格式如表1所示；接著，修改如代碼塊4所示的命令文件a.txt；最后，在Gnuplot軟件命令行中，通過load“a.txt”執(zhí)行命令，矢量圖eps文件（如圖1所示）被生成于命令文件所在的文件夾中。

表1 實驗產(chǎn)生的數(shù)據(jù)文件

表1中的第1列表示數(shù)據(jù)規(guī)模，即物品數(shù)量，從物品數(shù)量為300開始，以300增加，最終到3000；從第2列起每列代表一個算法在各個規(guī)模下的數(shù)據(jù)下的運行時間，共 4個算法，分別記為 DP-0.9、DP-0.7、DP-0.5、GR-0.9，其中，DP表示動態(tài)規(guī)劃算法，GR表示貪心算法，后面的數(shù)字表示背包容量占物品總重量的比重，比如0.9表示背包容量是所有物品重量之和的0.9倍；單元格中的數(shù)據(jù)是算法的運行時間，單位是毫秒（ms）。代碼塊4給出了繪制矢量圖的命令文件的內(nèi)容，其中，符號#后面是簡要解釋。依據(jù)代碼塊4的命令和表1的數(shù)據(jù)，通過Gnuplot執(zhí)行，可生成圖1所示的矢量圖。

代碼塊4：

需要指出的是，貪心算法GR-0.9是按照單位價值比從大到小處理的。從圖1可以看出，貪心算法運行時間明顯小于各個動態(tài)規(guī)劃算法，而動態(tài)規(guī)劃算法隨著背包容量增大、物品數(shù)量增加，其運行時間逐漸增加，基本呈現(xiàn)線性增長方式，這與理論上的時間復(fù)雜度相同。此外，學(xué)生還可以修改源代碼，課下開展動態(tài)規(guī)劃算法和貪心算法的優(yōu)化目標(biāo)比較，從中發(fā)現(xiàn)貪心算法的近似最優(yōu)特性及其與動態(tài)規(guī)劃算法的差距。

圖1 0-1背包問題的各類算法的運行時間對比圖

2.4 對比多種算法

0-1背包問題是經(jīng)典的NP難問題，動態(tài)規(guī)劃算法和貪心算法只是求解該問題的常用算法。隨著算法課程的開展，其他算法，如回溯法、分支限界法、概率算法將陸續(xù)被介紹。通過保留上述實驗數(shù)據(jù)和相關(guān)Gnu?plot繪圖命令，待掌握其他算法之后，再進(jìn)行對比，從中發(fā)現(xiàn)新規(guī)律，可以加深各個算法策略的理解和應(yīng)用。此外，上述實驗流程和分析也將為學(xué)生開展實際問題的算法研究提供新思路。

3 結(jié)語

本文以培養(yǎng)學(xué)生實驗對比和分析能力為目標(biāo)，以算法課程中的0-1背包問題為例，提出了新的教學(xué)模式，引導(dǎo)學(xué)生開展協(xié)作結(jié)對編程、實驗數(shù)據(jù)產(chǎn)生、矢量圖繪制、實驗結(jié)果分析等較為規(guī)范的科研訓(xùn)練。本文所提出的科研訓(xùn)練模式可以讓學(xué)生加深對算法策略的理解和綜合應(yīng)用，有望為學(xué)生未來順利開展科研工作奠定基礎(chǔ)，同時也為以能力目標(biāo)導(dǎo)向的算法課程教學(xué)改革提供新思路。