论文部分内容阅读
摘 要：实例驱动教学是一种具有实践性和启发性的新型教学方法。《算法设计与分析》是实践性较强的一门课程。教学内容的比较抽象与复杂，学生在这门课程的学习中会感到困难。本文针对该课程教学内容，对典型实例驱动教学在《算法设计与分析》课程中做了一些探索。通过典型的实例驱动教学，一个抽象的算法更具体化与形象化，使学生能快速理解算法的原理及各个算法之间的主要区别，同时激发他们学习的兴趣和热情，从而提高教学质量和教学效果。
关键词：算法设计与分析 实例驱动教学 背包问题 教学改革
中图分类号：G642 文献标识码：A 文章编号：1673-9795（2013）06（a）-0070-01
1 问题的提出
《算法设计与分析》[1]是实践性较强的一门课程。这门课程的主要目的，通过对计算机算法系统的学习与研究，掌握算法设计算法策略和技巧，培养学生对算法的计算复杂性正确分析的能力，对不同的实际问题设计出清晰高效的算法，为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础。软件的效率和稳定性取决于软件中所采用的算法，学习《算法设计与分析》课程，可以开阔编程思路，有助于编写出高效程序。因此，提高《算法设计与分析》课程教学水平有着极其深远的意义和重要的作用。
《算法设计与分析》内容的比较抽象与复杂，从学生的普遍反映来看，这是一门比较难的课程。《算法设计与分析》课程的教学内容按算法分类组织。在教科书中[2]，每一章对应一种算法，主要内容涵盖了动态规划、贪心法、回溯法和分支限界法经典的算法。本文针对该课程，对典型实例驱动教学在《算法设计与分析》教学中的应用做了一些探索。通过典型的实例教学，一个抽象的算法使其更具体化、形象化，学生能快速理解各种算法的原理及算法之间的区别，因此，在《算法设计与分析》教学中合理利用典型实例，激发学生学习兴趣和热情，从而提高教学效果。
2 0-1背包问题实例
0-1背包问题是经典组合优化问题[3]，有着广泛的实际应用背景，0-1背包问题比较简单，把抽象的，复杂的算法应用到该问题便于同学理解和掌握。0-1背包问题描述为：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大。
3 动态规划算法
动态规划是解决多阶段决策过程最优化的一种方法，该方法是由美国数学家贝尔曼等人提出的。用于解决生产管理、工程技术等方面的许多问题，并建立了运筹学的一个新的分支，即动态规划。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。动态规划方法能够把复杂问题的算法从指数阶的计算量减少到多项式阶。
4 贪心算法
贪心算法通过一系列的选择来得到问题的最优解，它所做的每一个选择都是当前状态最好的选择，即贪心选择。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。用贪心算法不能求解0-1背包问题，但能解决背包问题，背包问题与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，即xi∈[0，1]。
5 回溯算法
回溯法在问题的解空间树中，按深度优先策略，从根结点出发系统地搜索一个问题的所有解或任一解。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子樹的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
如果采用回溯法解决0-1背包问题，如一个结点的左儿子结点是一个可行结点就搜索其左子树。而对于右子树，需要用贪心算法构造一个上界函数，上界函数是通过讲将0-1背包问题松弛为背包问题利用贪心算法求得的，这个函数表明这个结点的子树所能达到的可能的最优值，只在这个上界函数的值超过当前最优解时才进入搜索。随着搜索进程的推进，最优解不断得到加强，对搜索的限制就越来越严格。如果这个上界小于当前值Bestf，说明该子树不可能包含最优解，即可以被“剪枝”。
6 分支限界法
分支限界法类似于回溯法，也是一种在问题的解空间树上搜索问题解的算法。分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。采用分支限界法解决0-1背包问题，同样需要用到贪心算法构造的上界函数。所不同的是，这个上界函数的作用不在于判断是否进入一个结点的子树继续搜索，因为在搜索到达叶节点之前，大家也无法知道已经得到的最优解是什么。在这里，可用一个最大堆来实现活结点的优先队列，上界函数的值将作为优先级，这样一旦有一个叶结点成为扩展结点，就表明已经找到了最优解。
7 结语
通过典型0-1背包问题实例，学生可以快速理解各种算法的基本思想、特点及算法之间区别，便于理解与掌握。笔者在这门课程的教学过程中深刻地体会到，要上好这门课，教师要注意观察学生的课堂反应及接受能力，采用适当的教学方法。实践证明，《算法设计与分析》实例教学方法是一种将抽象算法理论与实际典型实例相结合，让学生带着感兴趣的问题进入课程的学习，其探究能力和创新意识得到了较好的培养，同时培养学生分析问题及解决问题的能力。
参考文献
[1] 阿霍.计算机算法设计与分析：英文版，[M].北京：机械工业出版社，2006.
[2] 王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2010，5.
[3] 王晓云，陈业纲.计算机算法设计、分析与实现[M].北京：科学出版社，2012.
关键词：算法设计与分析 实例驱动教学 背包问题 教学改革
中图分类号：G642 文献标识码：A 文章编号：1673-9795（2013）06（a）-0070-01
1 问题的提出
《算法设计与分析》[1]是实践性较强的一门课程。这门课程的主要目的，通过对计算机算法系统的学习与研究，掌握算法设计算法策略和技巧，培养学生对算法的计算复杂性正确分析的能力，对不同的实际问题设计出清晰高效的算法，为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础。软件的效率和稳定性取决于软件中所采用的算法，学习《算法设计与分析》课程，可以开阔编程思路，有助于编写出高效程序。因此，提高《算法设计与分析》课程教学水平有着极其深远的意义和重要的作用。
《算法设计与分析》内容的比较抽象与复杂，从学生的普遍反映来看，这是一门比较难的课程。《算法设计与分析》课程的教学内容按算法分类组织。在教科书中[2]，每一章对应一种算法，主要内容涵盖了动态规划、贪心法、回溯法和分支限界法经典的算法。本文针对该课程，对典型实例驱动教学在《算法设计与分析》教学中的应用做了一些探索。通过典型的实例教学，一个抽象的算法使其更具体化、形象化，学生能快速理解各种算法的原理及算法之间的区别，因此，在《算法设计与分析》教学中合理利用典型实例，激发学生学习兴趣和热情，从而提高教学效果。
2 0-1背包问题实例
0-1背包问题是经典组合优化问题[3]，有着广泛的实际应用背景，0-1背包问题比较简单，把抽象的，复杂的算法应用到该问题便于同学理解和掌握。0-1背包问题描述为：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大。
3 动态规划算法
动态规划是解决多阶段决策过程最优化的一种方法，该方法是由美国数学家贝尔曼等人提出的。用于解决生产管理、工程技术等方面的许多问题，并建立了运筹学的一个新的分支，即动态规划。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。动态规划方法能够把复杂问题的算法从指数阶的计算量减少到多项式阶。
4 贪心算法
贪心算法通过一系列的选择来得到问题的最优解，它所做的每一个选择都是当前状态最好的选择，即贪心选择。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。用贪心算法不能求解0-1背包问题，但能解决背包问题，背包问题与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，即xi∈[0，1]。
5 回溯算法
回溯法在问题的解空间树中，按深度优先策略，从根结点出发系统地搜索一个问题的所有解或任一解。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子樹的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
如果采用回溯法解决0-1背包问题，如一个结点的左儿子结点是一个可行结点就搜索其左子树。而对于右子树，需要用贪心算法构造一个上界函数，上界函数是通过讲将0-1背包问题松弛为背包问题利用贪心算法求得的，这个函数表明这个结点的子树所能达到的可能的最优值，只在这个上界函数的值超过当前最优解时才进入搜索。随着搜索进程的推进，最优解不断得到加强，对搜索的限制就越来越严格。如果这个上界小于当前值Bestf，说明该子树不可能包含最优解，即可以被“剪枝”。
6 分支限界法
分支限界法类似于回溯法，也是一种在问题的解空间树上搜索问题解的算法。分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。采用分支限界法解决0-1背包问题，同样需要用到贪心算法构造的上界函数。所不同的是，这个上界函数的作用不在于判断是否进入一个结点的子树继续搜索，因为在搜索到达叶节点之前，大家也无法知道已经得到的最优解是什么。在这里，可用一个最大堆来实现活结点的优先队列，上界函数的值将作为优先级，这样一旦有一个叶结点成为扩展结点，就表明已经找到了最优解。
7 结语
通过典型0-1背包问题实例，学生可以快速理解各种算法的基本思想、特点及算法之间区别，便于理解与掌握。笔者在这门课程的教学过程中深刻地体会到，要上好这门课，教师要注意观察学生的课堂反应及接受能力，采用适当的教学方法。实践证明，《算法设计与分析》实例教学方法是一种将抽象算法理论与实际典型实例相结合，让学生带着感兴趣的问题进入课程的学习，其探究能力和创新意识得到了较好的培养，同时培养学生分析问题及解决问题的能力。
参考文献
[1] 阿霍.计算机算法设计与分析：英文版，[M].北京：机械工业出版社，2006.
[2] 王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2010，5.
[3] 王晓云，陈业纲.计算机算法设计、分析与实现[M].北京：科学出版社，2012.