基于案例的比较法在《算法设计与分析》教学中的应用研究

耿霞 刘建华

1.山东农业大学信息科学与工程学院 山东 泰安 271018；2.山东农业大学经济管理学院 山东 泰安 271018

1 《算法设计与分析》课程的性质与特点

算法在计算机科学中具有不可代替的重要地位[1-2]。算法对计算机科学的所有分支都非常重要，比如，大数据、机器学习需要用到分类决策树算法、遗传算法、爬山算法、模拟退火算法等；通信网络中的路由协议需要使用经典的最短路径算法；公钥加密依赖于高效的数论算法；计算机图像学需要用到几何算法等。

《算法设计与分析》是计算机类专业、人工智能专业等的一门核心专业基础课，本课程介绍非数值算法设计的策略与技术，课程内容主要包括：递推算法、递归与分治策略、动态规划算法、贪心算法、回溯算法、分支限界算法等[3]。通过本课程的学习，使学生能够掌握经典算法的基本思想并能灵活利用这些算法思想去解决实际问题，并掌握算法设计与分析的基本技巧，能够从时间复杂度和空间复杂度两个方面去分析算法的优劣[4]。本课程既具有较强的理论性又具有较强的实践性[5]，并且在学生就业和考研过程中，本课程知识点是经常被考察的内容。但本课程中涉及的一些经典算法由于比较抽象，因此学生在学习的过程中比较难理解，并且很难使学生达到灵活应用算法解决问题的教学目标。

2 案例教学法和比较教学法的内涵

案例教学法是在教学过程中通过引入一些学生生活或学习过程中的典型案例，借助于这些生动的案例帮助学生更好地理解抽象、枯燥的知识点的一种教学方法。案例教学法已被广泛应用于各种课程的教学过程中，是一种非常有效的教学方法。通过案例教学方法，可以把难理解的知识点融入有趣的案例中，从而能够激发学生的学习兴趣，更容易地理解和掌握有关知识点。教育学家叶圣陶说过，“教材无非是个例子”。案例教学法可以达到事半功倍的教学效果。

3 基于案例的比较教学法在课程中的应用

3.1 案例设计原则

好的案例是案例教学法取得好的教学效果的基础，因此教师在备课的过程中，一定要认真谨慎选择和设计教学案例。设计的教学案例应该具有贴切性、代表性、生动性。

贴切性是指设计的案例一是应该符合教学目标和要求，不能“跑题”，要与要讲授的知识点密切相关，案例应该能启发学生积极思考，或者能帮助学生更好地理解有关知识。二是应该难度适中，如果案例太简单的话，则引不起学生的兴趣，也可能会让学生忽视有关知识点的学习，不能让学生掌握好课程的重点或难点；如果案例太难的话，学生找不到解决问题的思考点或者很难理解其中包含的内容，则不利于帮助学生掌握课程内容。

代表性是指设计的案例要能起到范例作用，让学生能够举一反三，利用解决此问题的思路可以类推到其他相似的问题中，从而有利于培养学生分析问题、解决问题的能力。

生动性是指设计的案例一是应该来源于生活，与学生的日常学习、生活密切相关，这样的案例容易引起学生的兴趣，爱因斯坦说过：“兴趣是最好的老师”，在兴趣的驱使下，学生才能更加积极思考和学习。二是适合学生展开讨论和交流，具有一定的“话题性”。通过案例，便于教师引导学生积极思考，展开讨论，通过讨论找到问题的解决方法，自然而然地让学生理解有关的算法知识。

设计的案例可以分成引导型案例和学习型案例。所谓引导型案例，是指通过该案例，可以引起学生对某个知识点的兴趣，领着学生“入门”；所谓学习型案例，是指通过该案例，学生可以比较轻松地学习掌握某个知识点，是一种“润物细无声”传授知识的案例。

比如案例：用“贪心算法”找到偷车贼。

来自圣母大学计算机系副教授史戈宇在和家人外出的过程中遭遇了劫匪劫车，被抢之后，史教授原本通过拨打911借助于警察帮忙，但无奈警察不作为，史教授只好自己亲自解决。他最终借助于GPS定位功能和“贪心算法”思想成功找到了丢失的车辆。

本案例就属于一个引导型案例，设计此案例的目的是让学生对贪心算法有一个初步印象，体会所学知识和现实生活的密切关系，从而引发学生对学习贪心算法的兴趣，让学生非常期待后续有关知识的学习，调动了学生学习的积极性。

3.2 基于案例的比较法教学在《算法设计与分析》课程中的应用

通过几个具体例子来说明基于案例的比较教学法在《算法设计与分析》教学过程中的应用。

案例1：给定一个载重量为M的背包，考虑n个物品，其中第i个物品的重量wi，价值vi（1≤i≤n），要求把物品装入背包，且使背包内的物品价值最大。有两类背包问题（根据物品是否可以分割），如果物品不可以分割，称为0-1背包问题；如果物品可以分割，则称为背包问题。假设背包容量为50，有3件物品，每件物品的重量和价值如表1所示。

表1 每件物品重量和价值

分析：如果把此问题当作0-1背包问题，用动态规划算法可以解决，得到装载方案为：物品2和物品3装入背包，此时可以得到最大价值为220。此问题也可以使用贪心算法解决，首先按照单位价值从高到低排序，依次装入物品1和物品2，此时背包剩余容量只有20，无法再继续装入物品3，因此，此时背包中物品的价值为160。

如果把此问题当作背包问题，只能使用贪心算法解决。按性价比从高到低的顺序选取物品，获得最优值240。由于物品可以分割，剩下的空间装入物品3的一部分，而获得了更好的性能。

通过此案例，可以对比动态规划算法和贪心算法的算法思想，不同的算法得到的解决方案是不同的。根据得到的结果，学生很容易得到结论：0-1背包问题适合采用动态规划算法解决，背包问题适合采用贪心算法解决。基于同一个案例，学生可以比较动态规划算法和贪心算法的差异，从而能够更好地掌握两个算法的核心思想。

案例2：一销售商从n个城市中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。本题假定该旅行商从第1个城市出发。

假设有4个城市，各个城市之间的长度如图1所示。

图1 城市之间长度示意图

分析：旅行商问题可以采用回溯法解决，也可以采用分支限界算法解决。

如果采用回溯法，旅行商问题的解空间是一棵排列树。开始时，x＝｛1，2，…，n｝，相应的排列树由x的全排列构成。回溯法实现的伪代码如下：

旅行商问题也可以采用分支限界算法解决，解空间同回溯法一样也是一棵排列树。回溯法是以深度优先方式搜索解空间树，分支限界算法是以广度优先的方式搜索问题的解空间树。在分支限界算法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。使用分支限界算法解决旅行商问题的伪代码本文不再详述。

4 结束语

案例法和比较法都是被实践证明了的有效教学方法。《算法设计与分析》本身既有很强的理论性又有很强的应用性，涉及的经典算法理解起来比较困难，学生在学习的过程中存在畏难情绪。为了增强该课程的趣味性，激发学生的学习兴趣，更好地理解该课程的内容，本文研究了基于案例的比较法在教学过程中的应用。设计具有多种求解算法的教学案例，通过对同一案例不同实现算法的比较，使学生深刻理解这些算法的内涵和应用场景，既能促成学生更好地掌握算法设计与分析的理论和方法，又能培养学生的发散思维，提高学生分析问题、解决问题的能力。