《算法设计与分析》课程典型实例教学的应用

张晓霞，张宝鑫，陈倩

（辽宁科技大学软件学院，鞍山 114051）

1 问题的提出

《算法设计与分析》是计算机学科一门重要的专业基础课[1]，是理论与实践相结合较强的一门课程。其主要教学目标是通过对常用的算法理论进行系统而深入的学习，使学生掌握常规算法设计的基本原理，培养学生对一些算法的复杂性能进行正确分析，同时针对具体实际问题设计出高效的算法。计算机算法设计的是否高效直接决定于软件系统运行的效率和稳定性，学生掌握好《算法设计与分析》这门课程，为将来设计及编写出高效算法程序打下坚实的理论基础。所以，探讨与研究提高《算法设计与分析》课程教学效率具有理论意义和现实意义。

《算法设计与分析》内容的有些理论知识偏重与数学，学生感觉这是一门比较抽象与复杂比较难的课程。同时课程培养目标也要求学生既要掌握算法设计的基本理论，同时又要有实际调试程序的实际动手能力。在教科书中[2]，主要内容包括动态规划算法、贪心算法、回溯法和分支限界算法。本文针对《算法设计与分析》课程实际情况，对实例教学在回溯算法做了深入研究与探讨。采用典型的实例教学，把复杂而抽象的算法变为简单化、形象化，使学生能快速掌握回溯算法的基本原理及主要步骤，因此，选择合适的典型教学实例非常关键，在《算法设计与分析》教学中合理充分利用好典型实例，把复杂问题及算法简单化、具体化，活跃课堂学习气氛，从而激发学生对算法学习兴趣，同时提高理论课堂教学效果。

2 0-1背包问题实例

0-1背包问题是典型组合优化问题[3]，在很多领域，有着比较广泛的应用工程背景[4]。0-1背包问题描述为已知n个物品和一个带容量限制的背包。每个物品有重量及相应的利润，物品i的重量是wi，其利润为vi，背包的容量限制为C。求解目标为如何选择装入背包的物品，且需要满足容量约束条件，使得装入该背包中物品获得总利润最大。

约束（2）为背包的容量约束，也就是指装入背包物品不能超过背包的容量限制。约束（3）表示xi为0-1决策变量，当第i个物品放入背包时，xi=1，否则xi=0。0-1背包问题的解实际就是从物品集合中选出一个合适子集，并且满足背包的容量约束条件，使装入背包的物品获得利函数值最大。

本文采用实例为简单的0-1背包问题，这个问题贴近同学的日常生活，便于学生接受和理解。贪心算法就解背包问题上界函数是通过把0-1背包问题的xiÎ{0,1}整数松弛为小数 xiÎ[0,1]。例如：物品数目 n=3，背包容量C=35，各个物品的重量为W=（11,21,23），各个物品的价值为V=（21,31,33），如果是0-1背包问题，最优解为（1,0,1），最优值为54。如是背包问题，最优解（1,1,0.13），最优值为56。也就是说贪心算法求解背包问题为0-1背包问题提供一个上界函数。

3 回溯算法

采用回溯算法求解0-1背包问题，如果一个结点的左子树满足约束条件，就继续搜索。对于右子树，首先采用贪心算法生成一个上界函数，上界函数表明继续搜索这个结点的子树能获得最优值，也就是说只有满足上界函数的值大于当前最优解条件时才能进入下一级子树继续开始搜索。在搜索进程中，最优解逐渐得到改善。如果某个结点的上界函数小于当前最优值Bestf，那么搜索该子树不可能获得比较好的最优解，即该子树可以被“剪枝”。图1给出了0-1背包问题的解空间树，下面给出用回溯法求解决实例1中0-1背包问题步骤：

步骤1：开始时，1为唯一扩展结点，扩展1结点，先到达2结点。

步骤2：此时1、2为活结点，2成为当前扩展结点。因2结点满足能力约束，扩展2结点，先到达4结点，因4结点满足能力约束，扩展4到达8结点，因结点8不满足能力约束，结点8不可行，结点8剪去。

步骤3：回溯到4，再次扩展4到达9结点，由于9是叶结点，即得到一个可行解x=（1,1,0），当前最好值Bestf=52。

步骤4：回溯到4，再回溯到2结点，因为右子树结点 5 界函数 bound（5）=54＞Bestf，5 成为当前扩展结点，扩展结点5到10，结点10叶结点，得到一个可行解x=（1,0,1），Bestf=54。

步骤5：回溯到5，结点10剪去。回溯到2，最后回溯到1，扩展1结点，到达3结点，结点3界函数bound（3）=51，因为 bound（3）＜满足 Bestf，结点 3 剪去。

图1 0-1背包问题的解空间树

4 结语

本文针对回溯法算法特点，采用典型实例教学，有助于学生快速理解和掌握回溯法的基本原理及算法步骤。《算法设计与分析》是计算机学科的重要课程，也是一门比较难的课程。作为教师要讲好这门课，对教师也提出更高的要求，教师要多学习，扩展知识，根据算法的特点，选好典型的实例，同时在课堂教学过程中，要随时观察学生的课堂接受能力，适当动态调整教学内容与进度。经过多年教学实际验证，采用典型实例教学方法，将复杂抽象算法理论与简单的典型实例有机结合，这样使学生由被动学习变为主动学习，培养学生对算法学习的兴趣，提高学生独立分析问题及解决问题的实际动手能力。