对算法的一些理解

主要的算法思路有这几个：

1、穷举

2、动态规划

3、分治

4、贪心

5、回溯

6、分支限界

这些算法思路之间是有区别和联系的。但是，很多文章没有把他们的区别和联系讲出来，这里尝试梳理一下。

穷举是最朴素、最原始的思路。穷举就是把所有的可能一个一个列举出来，逐个分析后，再合并分析后的结果。

但是，如果一个问题包含的可能太多，穷举就会需要大量时间来做计算和大量空间来保存运算数据。而计算机的算力和存储是有限的，所以需要改进穷举思路。

怎么改进呢？对问题进行研究，找到他的特性，根据这些特性，1）直接排除掉一些计算 2）需要多次计算的，把计算结果保存下来 3）todo

根据问题特性和改进思路的不同，把改进思路归为这几类：分治、分支限界、回溯、动态规划、贪心。

分治法：

• 该问题的规模缩小到一定的程度就可以容易地解决。
• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，利用该问题分解出的子问题的解可以合并为该问题的解。
• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（如果各子问题是不独立的，则分治法要重复地解公共的子问题，也就做了许多不必要的工作。此时虽然也可用分治法，但一般用 动态规划 较好。）

回溯法是比动态规划法更加一般的算法，如n皇后，子集和数问题。。回溯算法相当于穷举搜索，穷举所有情况，然后得到最优解。时间复杂度非常高，指数级的，只能解决小规模数据问题。对于大规模数据，执行效率就相当低。

动态规划法是一种方法，注意和算法的区别。如多段图问题，备忘录方法，弗洛伊德算法，最长公共子序列问题

贪心法是动态规划法的特例，如0-1背包，最小代价生成树（prim算法和cruskal算法），huffman算法，以及地杰斯特拉算法。

首先，这些方法所要解决的问题，一般都是决策问题。而贪心法一般是来求解最优问题的，而且他们其实都是在对问题的状态空间树进行搜索，在这个状态空间树中搜索最佳的路径以便求出最优策略。而贪心法是从上到下只进行深度搜索的，也就是说它是一口气走到黑的，一口气吃成胖子的，它的代价取决于子问题的数目，也就是树的高度，每次在当前问题的状态上作出的选择都是1，也就是说，它其实是不进行广度搜索的，这也造成了它的一个缺点：它得出的解不一定是最优解，很有可能是近似最优解。而动态规划法在最优子结构的前提下，从状态空间树的叶子节点开始向上进行搜索，并且在每一步都根据叶子节点的当前问题的状况作出选择，从而作出最优决策，所以她的代价就是子问题的个数和可选择的数目，所以它求出的解一定是最优解。回溯法是从上到下进行深度搜索，如果深度搜索没有进行到底而不满足决策函数了，那么不好意思，请回去，然后再从最近的可以岔开的地方选择另一条路，继续之前的深度搜索，如果搜索到底，那么再通过for循环进行广度搜索。所以它也是深度搜索和广度搜索并行的。求出的解也一定是最优解，通常目标是找到问题的所有可行解；分支限界法主要利用广度优先搜索策略，通常目标是尽快找到一个满足问题约束条件的解

《算法之道》对三种算法进行了归纳总结，如下表所示：