面向科研训练的算法课程教学模式

张立臣

（1.现代教学技术教育部重点实验室，西安 710062；2.陕西省教学信息技术工程实验室，西安 710119；3.陕西师范大学计算机科学学院，西安 710119）

0 引言

培养高层次人才一直是我国研究生培养的目标之一，而较高的科研能力是高层次人才的基本特征[1]。因此，在本科阶段开展规范的科研训练，有助于培养学生的基本科研素质和科研能力，从而为其未来从事科研工作奠定基础。目前，以学生为中心的本科生教育教学改革，越来越突出学生的能力培养[2]。这就促使大学教师积极更新教学内容、教学模式、教学案例和教学评价方式，以培养学生包括科研能力在内的诸多能力素养。

算法课程作为计算机学科的一门专业核心课程，尤其注重培养学生算法基本理论知识和计算思维、问题建模、算法设计与分析能力[3]。算法课程在计算机学科课程中地位十分重要，其关注的算法设计与分析能力对学生未来职业发展，尤其是从事科研和算法工程师等工作，具有重要意义。因此，针对算法课程的教育教学改革受到广泛关注，相关教材、在线课程、算法竞赛层出不穷。事实上，现有的算法课程改革主要关注于算法的设计与实现，一般提供算法伪代码或程序源代码，但在实验对比和分析方面较为欠缺。由此导致的结果是，学生虽然可以设计并实现教师布置的算法问题，并能够给出正确结果，但是，所给出的结果往往是某个特定问题实例的结果，通用性较差，缺乏不同规模下的问题实例的对比结果。相反，现有算法相关论文的实验部分大都基于不同规模的问题实例开展对比实验，并在此基础上，分析实验结果，评价算法优劣。

针对上述问题，以0-1背包问题的教学为例，本文提出了一种新的算法课程教学模式，在问题建模和算法设计的基础上，通过提供完整的编程框架和测试数据，将学生工作重心集中到算法核心代码实现和实验结果分析上；在此基础上，提供矢量图绘制模板，让学生绘制实验结果矢量图并分析实验结果。通过上述训练，有望培养学生基本的科研素质和科研习惯，为其未来从事科研工作打下坚实基础。

1 0-1背包问题概述

0-1背包问题是算法课程中动态规划策略教学的重要内容[4]。0-1背包问题是一个NP难问题，解决该问题具有重要的理论和实际意义。0-1背包问题可描述为：存在1个有限容量的背包和一组有限个数的物品，已知背包的容量以及每个物品的重量和价值，如何选择装入背包的物品，使得在不超过背包容量的前提下，装入背包的物品的总价值最大。该问题的形式化数学模型可用0-1整数规划模型描述：

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

现有教材一般采用动态规划算法策略求解该问题，动态规划算法适合那些经分解得到的子问题不互相独立的情形。0-1背包问题的动态规划算法的递推方程为：

其中，F（i,W）表示在不超过背包容量W的前提下，选择前i个物品中的某些物品（i≤n）所得到的最大价值，即F（i,W）对应的子问题是由前i个物品及容量为W的背包构成的。

分析上述递推方程，学生一般能够通过循环、分支等语句完成程序源代码编写并调试运行。但是，这在实验对比方面较为欠缺，学生一般不进行不同问题规模下的实验对比和分析。为此，我们针对该问题设计了新的教学模式，以训练和培养学生基本的实验对比和分析能力。

2 聚焦实验对比和分析的0-1背包问题教学模式

在对0-1背包问题进行数学建模和动态规划算法设计的基础上，我们提供了实现该问题的编程框架和测试数据，以突出训练和培养学生的核心代码编写和实验结果分析能力。

2.1 协作结对编写算法核心代码

协作结对编程是指两个程序员共同完成同样的编程任务，有助于减少学生的认知负荷，提升学生的互动性和学习兴趣[5]。学生自由组合结对，在课堂上共同操作一台电脑完成核心代码的编写和调试。为了将学生聚焦于核心代码编写层面，我们设计了程序框架，并让学生提前下载到电脑中。所提供的程序框架采用Java语言编写，以Eclipse项目形式提供下载，0-1背包问题编程框架如下所示：

代码块1：文件Test.Java:

代码块2：文件Knapsack.Java

以上代码提供了2个文件，其中，文件Test.Java用于产生输入数据、输出结果，文件Knapsack.Java用于解决0-1背包问题。在文件Test.Java中，定义了物品重量数组、物品价值数组和背包容量等全局变量，这些数据通过函数generate（）随机产生，共产生10组数据，物品价值和重量在1至10之间，背包容量限制为物品总重量的0.8倍。第一组数据包括10个物品，然后以10的倍数增加物品数量。对每组产生的数据，将调用Knapsack类中的静态方法solve（），该方法需要学生结对编程实现。此外，为了记录动态规划算法的时间，用数组ctime记录处理每组数据所用的时间并输出。一种可行的动态规划源代码如下所示。

代码块3：

开始时，学生将实验次数num的值先设置为1，然后通过断点或输出以检查所设计的算法是否正确，在正确的前提下，将实验次数增加，记录所需的时间。

2.2 分析实验数据

在保证算法正确的前提下，学生分析实验结果。通常，由于当前电脑速度极快且数据规模较小，每组实验所消耗的时间差别不大，有时实验在某些规模下所耗时间反而降低。针对此问题，一般通过两种方式实现。一种是调整实验参数，通过增加数据规模，比如将物品的数量从300开始增加，依次增加300；一种是对每次实验重复多次，取平均时间。此外，在实验中也可以同时结合这两种方式。

在此基础上，分析影响实验结果的因素。由于0-1背包问题的动态规划算法的时间复杂度为O（n*B），其中n和B分别是物品的数量和背包的容量。因此，背包容量B也会影响算法性能，可以通过设置不同的背包容量，记录实验的运行时间，并作出适当分析。

2.3 绘制矢量图并分析实验结果

图和表格是常见的两种实验结果的呈现方式。鉴于图更为直观和常用，我们提供了矢量图的绘制命令模板。首先，学生下载并安装矢量画图工具Gnuplot（http://gnuplot.sourceforge.net/）；然后，将每组实验记录的运行时间数据按列形式存在数据文件中，如data.txt，格式如表1所示；接着，修改如代码块4所示的命令文件a.txt；最后，在Gnuplot软件命令行中，通过load“a.txt”执行命令，矢量图eps文件（如图1所示）被生成于命令文件所在的文件夹中。

表1 实验产生的数据文件

表1中的第1列表示数据规模，即物品数量，从物品数量为300开始，以300增加，最终到3000；从第2列起每列代表一个算法在各个规模下的数据下的运行时间，共 4个算法，分别记为 DP-0.9、DP-0.7、DP-0.5、GR-0.9，其中，DP表示动态规划算法，GR表示贪心算法，后面的数字表示背包容量占物品总重量的比重，比如0.9表示背包容量是所有物品重量之和的0.9倍；单元格中的数据是算法的运行时间，单位是毫秒（ms）。代码块4给出了绘制矢量图的命令文件的内容，其中，符号#后面是简要解释。依据代码块4的命令和表1的数据，通过Gnuplot执行，可生成图1所示的矢量图。

代码块4：

需要指出的是，贪心算法GR-0.9是按照单位价值比从大到小处理的。从图1可以看出，贪心算法运行时间明显小于各个动态规划算法，而动态规划算法随着背包容量增大、物品数量增加，其运行时间逐渐增加，基本呈现线性增长方式，这与理论上的时间复杂度相同。此外，学生还可以修改源代码，课下开展动态规划算法和贪心算法的优化目标比较，从中发现贪心算法的近似最优特性及其与动态规划算法的差距。

图1 0-1背包问题的各类算法的运行时间对比图

2.4 对比多种算法

0-1背包问题是经典的NP难问题，动态规划算法和贪心算法只是求解该问题的常用算法。随着算法课程的开展，其他算法，如回溯法、分支限界法、概率算法将陆续被介绍。通过保留上述实验数据和相关Gnu⁃plot绘图命令，待掌握其他算法之后，再进行对比，从中发现新规律，可以加深各个算法策略的理解和应用。此外，上述实验流程和分析也将为学生开展实际问题的算法研究提供新思路。

3 结语

本文以培养学生实验对比和分析能力为目标，以算法课程中的0-1背包问题为例，提出了新的教学模式，引导学生开展协作结对编程、实验数据产生、矢量图绘制、实验结果分析等较为规范的科研训练。本文所提出的科研训练模式可以让学生加深对算法策略的理解和综合应用，有望为学生未来顺利开展科研工作奠定基础，同时也为以能力目标导向的算法课程教学改革提供新思路。