若干算法设计模式的研究与应用

论文摘要

自动程序设计一直是计算机科学的一个奋斗目标,而算法[1]是程序的灵魂,是解决问题的关键,是程序设计的基础和难点,要实现程序设计的自动化首先应该实现算法设计的自动化。但算法设计是一项创造性的劳动,因此要实现自动程序设计的目标目前还存在很多困难。在长期的算法和程序设计实践中,人们总结出来了一些常用而有效的算法设计方法:贪心法、分而治之法、动态规划法、回溯法和分枝定界法,很多问题均可以使用它们进行求解。因此,我们期望通过对这些算法设计方法的深入研究,抽取每种方法在求解问题时的共同规律,利用泛型程序设计的思想,构造上述五类常用算法设计方法的算法设计模式。当面临一个具体问题求解时,只需根据该问题的特点和性质,对算法设计模式进行实例化,即可生成问题的求解程序,不仅可以降低程序开发的难度,而且可以对推动算法设计自动化研究探索一条有效的途径。因此本文主要工作包括:1、对贪心法、分而治之法、动态规划法、回溯法、分枝定界法进行了深入研究,并对这五种算法设计方法分别进行抽象,形成对应的算法设计模式,这是本文研究的重点与难点。2、以本文抽象出的五种算法设计模式为基础,构造相应的算法设计模板。3、以若干典型问题为例,说明上述所得算法设计模板的使用方法。实践证明,本文开发的五种算法设计模板具有较好的可重用性,使用它们开发应用程序,能有效地降低程序开发的难度,提高程序开发效率。同时由于它们经过许多实例测试保证了其可靠性,从而提高了以它们为基础所开发的应用程序的可靠性。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 引言
• 1.2 算法概述
• 1.2.1 算法思想
• 1.2.2 算法的描述
• 1.2.3 算法的复杂性
• 1.3 设计模式研究概述
• 1.3.1 设计模式的思想
• 1.3.2 设计模式的原则
• 1.3.3 设计模式的基本成分
• 1.3.4 设计模式的研究现状
• 1.3.5 设计模式的典型示例
• 1.4 泛型程序设计思想
• 1.5 设计模式的泛化
• 1.6 C++中的模板机制
• 1.6.1 类模板
• 1.6.2 函数模板
• 1.7 本文章节组织
• 2 算法设计模式的研究及实现
• 2.1 概述
• 2.2 算法设计模式的实现环境和实现工具
• 2.2.1 实现环境简介
• 2.2.2 模板机制（template）
• 2.3 贪心法设计模式
• 2.3.1 贪心法概述
• 2.3.2 抽象贪心法设计模式的思想
• 2.3.3 贪心法设计模式定义与实现
• 2.4 分而治之法设计模式
• 2.4.1 分而治之法概述
• 2.4.2 抽象分而治之法设计模式的思想
• 2.4.3 分而治之法设计模式定义
• 2.5 动态规划法设计模式
• 2.5.1 动态规划法概述
• 2.5.2 抽象动态规划法设计模式的思想
• 2.5.3 动态规划法设计模式定义
• 2.6 回溯法设计模式
• 2.6.1 回溯法设计方法概述
• 2.6.2 回溯法设计模式的思想
• 2.6.3 回溯法设计模式定义
• 2.7 分枝定界法设计模式
• 2.7.1 分枝定界法设计方法概述
• 2.7.2 分枝定界法设计模式的思想
• 2.7.3 分枝定界法设计模式定义
• 2.8 小结
• 3 算法设计模式的使用方法
• 3.1 使用本文开发的算法设计模式进行问题求解的步骤
• 3.2 贪心法设计模式进一步说明
• 3.3 分而治之法设计模式进一步说明
• 3.4 动态规划法设计模式进一步说明
• 3.5 回溯法设计模式进一步说明
• 3.6 分枝定界法设计模式进一步说明
• 4 算法设计模式应用实例
• 4.1 贪心法设计模式实例
• 4.1.1 背包问题
• 4.1.2 找零钱
• 4.2 分而治之法设计模式实例
• 4.2.1 选择问题
• 4.2.2 归并排序
• 4.3 动态规划法设计模式实例
• 4.3.1 最优矩阵连乘次序问题
• 4.3.2 最短路径
• 4.4 回溯法设计模式实例
• 4.4.1 n 皇后问题
• 4.4.2 子集和问题
• 4.5 分枝定界法设计模式实例
• 4.5.1 n 皇后问题
• 4.5.2 旅行商问题
• 4.6 小结
• 结语
• 本文工作总结
• 进一步的工作展望
• 参考文献
• 后记
• 在学期间公开发表论文及著作情况