1、算法简介

　　算法是问题求解过程的精确描述，一个算法由有穷个可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。

　　通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。

　　算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、递归法、回溯法、动态规划法、分治法、贪心法、分支限界法等。

2、迭代法

　　从某个点出发，通过某种方式求出下一个点，使得其离要求的点（方程的解）更进一步；当两者之差接近到可以接受的精度范围内，就认为找到了问题的解。

　　迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：

　　　　● 选一个方程的近似根，赋给变量x0；

　　　　● 将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；

　　　　● 当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。

　　注意事项：

　　　　如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制；

　　　　方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。

2、穷举搜索法

　　穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解，即遍历的方法。

3、递推

　　递推，即是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。其中初始条件或问题本身已经给定，或是通过对问题的分析与化简而确定。递推的本质也是一种归纳，递推关系式通常是归纳的结果。

　　能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列解，构造出问题规模为 I的解。这样，程序可从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。

4、递归

　　能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。

　　在解决一些复杂问题时，为了降低问题的复杂程序，通常是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，并没有对问题进行求解，而只是当解决了最后的问题那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的方法。

　　一言以蔽之，递归算法的执行过程分递推和回归两个阶段。在递推阶段，把复杂的问题的分解为简单问题，而且必须要有终止递归的情况。在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。

　　在编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列 “简单问题”层，它们各有自己的参数和局部变量。

　　递归分类：分为直接递归和间接递归。如果一个算法直接调用自己，称为直接递归调用；如果一个算法A调用另一个算法B，而算法B又调用算法A，则此种递归称为间接递归调用。

　　减半递推：减半递推即将问题的规模减半，然后，重复相同的递推操作。

　　递归基本要素：

　　　　边界条件：确定递归到何时终止；

　　　　递归模式：大问题是如何分解为小问题的。

　　递归解决汉诺塔问题在下篇文章介绍：《》（点我）。

5、回溯法

　　回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。因为有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤，也不能使用无限的列举。

　　对于这类问题，只能采用试探的方法，通过对问题的分析，找出解决问题的线索，当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。

　　在回溯法中，放弃当前候选解，然后回退去使用下一个候选解的过程称为回溯；扩大当前候选解的规模，以继续试探的过程称为向前试探。

　　虽然分析回溯算法的复杂度可能很高，但实际上的性能却很好，明显优于穷举法。有时还会借助裁剪的方法进一步降低复杂度。与分支限界法不同，回溯算法通常是深度优先递归的搜索所有解，而分支限界通常是广度优先，找出满足条件的一个解。

6、分治法

　　将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。

　　如果原问题可分割成k个子问题，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

　　将原问题划分成n个规模较小而结构与原问题相似的且相互独立的子问题；递归地解决这些子问题，然后再合并其结果，这是分治法的特点。分治使用的是自顶向下的方法。但是由原问题划分而成的子问题可以相互独立也可以不独立，一般要求独立；如果不独立（即子问题相互重叠），虽然可以用分治法，但为了效率（避免重叠子问题多次求解），应该使用动态规划法，而不是分治法。

　　分治法规则：

　　　　平衡子问题：最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k＝2），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。

　　　　独立子问题：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。

　　分治在每层递归上都有三个步骤：

　　　　分解（Divide）：将原问题分解成一系列子问题；

　　　　解决（Conquer）：递归地解决各个子问题；若子问题足够小，则直接求解；

　　　　合并（Combine）：将子问题的结果合并成原问题的解。

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

　　　　● 该问题的规模缩小到一定的程度就可以容易地解决；

　　　　● 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；

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

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

　　能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

7、动态规划法

　　动态规划的基本思想与分治法的基本思想基本上类似。将待求解的问题分解成若干个全部或部分重叠的子问题，先求解子问题，但在求解这些子问题时只求解一次，然后从这些子问题的解得到原问题的解。

　　动态规划与分治法区别：动态规划法要求由原问题分成的子问题部分或全部重叠、重复；在求解时，这些重叠的子问题仅仅被求解一次，而不是多次。换句话说，分治法适合于求解子问题相互独立的问题，而动态规划适合于求解子问题重叠的问题。当然，对于子问题重叠的问题，使用分治法也是可以的，但是效率不是很好，因为重叠的子问题多次被重复求解。

　　动态规划的两个要素：最优子结构和重叠子问题，即问题必须具有最优子结构性质以及其子问题必须全部或部分重叠，一般意义上讲，问题所具有的这两个重要性质是该问题可用动态规划算法求解的基本要素。

　　最优子结构性质：

　　　　● 如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构（问题具有最优子结构）。

　　　　● 在动态规划算法中，利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。也就是说，首先找到子问题的最优解，解决子问题，然后找到问题的一个最优解。寻找问题的一个最优解需要在子问题中做出选择，即选择将用哪一个来求解问题。问题解的代价通常是子问题的代价加上选择本身带来的开销。

　　重叠子问题：

　　　　● 适用于动态规划求解的第二个要素是子问题的空间要“很小”，也就是用来求解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。当一个递归算法不断地求解同一问题时，我们说该最优问题包含重叠子问题。也就是说，不同的子问题中又包含了相同的子子问题。

　　　　● 动态规划算法总是充分利用重叠子问题，即通过每个子问题只解一次，把解保持在一个在需要时就可以查看的表中，而每次查表的时间为常数。通常，不同的子问题个数随问题的大小呈多项式增长。因此，用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。

　　动态规划法用于求解最优解，其设计步骤为：

　　　　● 描述最优解的结构或性质；

　　　　● 递归地定义最优解的值，即建立递归关系以便指导下一步的最优解的值的计算；

　　　　● 根据上一步的递归关系，按自底向上的方式计算最优解的值（该值是下一步构造最优解的依据）；

　　　　● 由上一步计算出的结果构造一个最优解。

　　前三步是构成问题的动态规划解的基础；在只需要求出最优解的值时，第4步可以略去；若需要求出问题的最优解，则必须执行第4步。如果的确做了第4步，则有时要在第3步的计算中记录一些附加信息，使构造一个最优解变得容易。

　　动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。

　　由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的（即不包含公共的子子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。

　　动态规划允许这些子问题不独立，也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。

8、贪心法

　　贪心法中采用逐步构造最优解的方法。在每一个阶段，都做出一个看上去最优的决策（在一定的贪心标准下），决策一旦作出，就不再更改。做出贪心决策依据称为贪心准则。

　　也就是说，贪心算法通过一系列的选择来得到问题的（最优）解。它所做的每一个选择都是在当前状态下局部最好的选择（即贪心选择）；贪心法是一种局部最优算法设计思路，思想是保证每一步选择在当前达到最优。

　　贪心算法与动态规划法的不同：

　　　　在动态规划算法中，每步所做的选择往往依赖于相关子问题的解，因而只有在解出相关子问题后，才能做出选择；而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择。贪心算法所做的贪心选择可以依赖于已经所做过所有的选择，但决不依赖于将来所做的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行。

　　贪心实例：例如平时购物找钱时，使找回的零钱的硬币数最少，贪心法不考虑找零钱所有的方案，而是从最大面值开始，按递减的顺序考虑各币种，当不足大面值币种时才去考虑下一种较小面值。假设只有面值为1、5和11单位的硬币，希望找回总额为15单位的硬币。按贪婪算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解应是3个5单位面值的硬币。