计算机算法设计与分析主要通过介绍常见的算法设计策略及复杂性分析方法，培养学生分析问题和解决问题的能力，为开发高效的软件系统及参加相关领域的研究工作奠定坚实的基础。该课程理论与实践并重，内容具有综合性、广泛性和系统性，是一门集应用性、创造性及实践性为一体的综合性极强的课程，通过对本课程的学习，对如下算法有了深刻的理解。

一、递归与分治策略：大整数的乘法、矩阵乘法、棋盘覆盖、合并排序、快速排序

程序直接或间接调用自身的编程技巧称为递归算法。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治法在每一层递归上都有三个步骤：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；合并：将各个子问题的解合并为原问题的解。

递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归优秀在代码简洁，但首先需要有清晰的思路理清递归的循环条件及出口。递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

有时递归需要多次重复某一计算，可以用数组记录下需要的数据进行调用大大降低空间复杂度。在用分治法设计算法时，最好使子问题的规模大致相同。如分成大小相等的k个子问题，许多问题可以取k＝2。

分治法所能解决的问题一般具有以下几个特征：

（1）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质；

（2）利用该问题分解出的子问题的解可以合并为该问题的解；

（3）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

二、动态规划：最长公共子序列、凸多边形最优三角剖分、图像压缩、0-1背包问题、最优二叉搜索树

动态规划是解决多阶段决策问题的一种方法。据空间顺序或时间顺序对问题的求解划分阶段。根据题意要求，对每个阶段所做出的某种选择性操作。用数学公式描述与阶段相关的状态间的演变规律。

如果一类问题的求解过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策，并影响到下一个阶段的决策。在做每一步决策时，列出各种可能的局部解.依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。以每一步都是最优的来保证全局是最优的。

动态规划与分治法所能解决问题的特征类似，主要区别在于动态规划所分解出的各个子问题不是相互独立的，即子问题之间包含公共的子子问题。

三、贪心算法：活动安排问题、装载问题、哈夫曼编码、单源最短路径、最小生成树

在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。

利用贪心法求解的问题应具备如下2个特征：

1、贪心选择性质，指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到；

2、最优子结构性质。

四、回溯法：装载问题、n后问题、0-1背包问题、最大团问题、旅行售货员问题

以深度优先的方式系统地搜索问题的解的方法称为回溯法，分为递归回溯和迭代回溯两种。当所给的问题是从n个元素的集合S中找出满足某种性质的子集时,相应的解空间树称为子集树。当所给的问题是确定n个元素满足某种性质的排列时,相应的解空间树称为排列树。回溯算法可以很方便地遍历一个集合的所有子集或者所有排列。

在生成解空间树时，定义以下几个相关概念：活结点：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。扩展结点：当前正在生成其儿子结点的活结点叫扩展结点（正扩展的结点）。死结点：不再进一步扩展或者其儿子结点已全部生成的结点就是死结点。

在确定了解空间的组织结构后，回溯从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点成为一个活结点，同时成为当前的扩展结点。在当前的扩展结点，搜索向深度方向进入一个新的结点。这个新结点成为一个新的活结点，并成为当前的扩展结点。若在当前扩展结点处不能再向深度方向移动，则当前的扩展结点成为死结点，即该活结点成为死结点。此时回溯到最近的一个活结点处，并使得这个活结点成为当前的扩展结点。回溯法以这样的方式递归搜索整个解空间（树），直至满足中止条件。

在回溯法搜索解空间树时，通常采用两种策略（剪枝函数）避免无效搜索以提高回溯法的搜索效率：用约束函数在扩展结点处减去不满足约束条件的子树；用限界函数减去不能得到最优解的子树。

回溯法是一种组织搜索的一般技术，有“通用的解题法”之称，用它可以系统的搜索一个问题的所有解或任一解。有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。应用回溯法求解时，需要明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。

五、分支界限法：单元最短路径问题、装载问题、0-1背包问题、最大团问题、旅行售货员问题

分支限界法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为限界）。

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，凡是界限超出已知可行解值的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

六、结语

在动态规划算法中，每步所做的选择往往依赖于相关子问题的解，因而只有在解出相关子问题后，才能做出选择（子问题->选择->原问题）。在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择，然后再去解出这个选择后产生的相应的子问题（原问题->选择->子问题）。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题。

大多数问题动态规划都可以解决，但是太慢。因此有些问题贪心确实比动态快的多。不过相对的贪心解决问题并不如动态规划精细，得出来的不一定是最优解，只能说是相对最优，根据情况选择不同的算法解决问题才是王道。

在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满足某种要求的可能或最优的情况，从而得到整个问题的解。回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。

通过对课程的理论学习与实践，我掌握了许多经典的算法思想，思维创新能力和实践能力得到了有效的提高，并且一题多解的情况让我对不同的算法有了更加深刻的认识。这些知识在我今后的学习中将会得到更深层次的理解与应用。