贪心算法实例化教学方法探索

Instantiation Teaching Method Exploration of Greedy Algorithm

摘要: 贪心算法是经典的六大类算法设计思想之一。贪心算法思想简单，其应用的难点在于如果想要求的是全局最优解，则必须证明贪心算法的两个性质(贪心选择性质和最优子结构性质)。而在教学过程中，对于贪心选择性质的证明，一直是学生理解的难点。本文提出了一种将动画、实例、形式化描述相结合的教学方法，以最优装载问题为例来介绍贪心算法的讲解。经实践检验，教学效果较好。

Abstract: Greedy algorithm is one of the six classic algorithm design ideas. The idea of greedy algorithm is simple. The difficulty of greedy algorithm is that the two properties (greedy selection property and optimal substructure property) must be proved if the global optimal solution is desired. In the course of teaching, the proof of the greedy selection property has always been a difficult point for students to understand. This paper proposes a teaching method which combines animation, instantiate examples and formal description. Through an example of the most optimal loading problem, the teaching method of greedy algorithm is introduced. The practice shows that the teaching effect is good.