四大算法思想：贪心，分治，回溯，动态规划_动态规划,贪心,分治

1 贪心算法

1.1 介绍

1. 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解；
2. 贪心算法的特点是一步一步地进行，以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间；
3. 贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题；
4. 通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都保证能获得局部最优解，但由此产生的全局解不一定是最优的；
5. 如果把所有的子问题看成一棵树的话，贪心自顶向下，每次向下遍历最优子树即可（通常这个“最优”都是基于当前情况下显而易见的“最优”），这样的话，就不需要知道一个节点的所有子树情况，于是构不成一棵完整的树；
6. 适合用贪心算法解决问题的前提是：局部最优策略能导致产生全局最优解；（比如图的最小生成树）
7. 实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断；

1.2 案例（最短路径）

贪心算法给出的问题的解并不一定是最优解。

比如在下面的一个加权图中，我们从顶点 S 开始，找一条到顶点 T 的最短路径（路径中边的权值和最小）。

如果用贪心算法来解决这个问题，那么解决思路是：每次都选择一条跟当前顶点相连的权重最小的边，直到找到顶点 T。按照这种思路，我们求出的最短路径是 S->A->E->T，路径长度是 1+4+4=9。

但是实际上，用贪心算法选择的路径并不是最短的，因为 S->B->D->T 才是最短路径，因为这条路径的长度是 2+2+2=6。

为什么此时贪心算法不一定给出最优解呢？因为前面的选择会影响后面的选择，即便第一步选择最优的走法（边最短），但有可能因为这一步选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解了。

2 分治算法

2.1 介绍

1. 分治算法是将一个规模为N的问题分解为K个规模较小的子问题;
2. 这些子问题相互独立且与原问题性质相同;
3. 求出子问题的解，就可得到原问题的解;

2.2 基本思想

1. 当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解在时间上耗费相当长，或者根本无法直接求出；
2. 对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解后，再找到合适的方法，把它们组合成整个问题的解；
3. 如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止；

2.3 解题步骤

分治法解题的一般步骤：

1. 分解：将要解决的问题划分成若干规模较小的同类问题；
2. 求解：当子问题划分得足够小时，用较简单的方法解决；
3. 合并：按原问题的要求，将子问题的解逐层合并构成原问题的解。

2.4 应用场景

运用分治策略解决的问题一般来说具有以下特点：

1. 原问题可以分解为多个子问题，这些子问题与原问题相比，只是问题的规模有所降低，其结构和求解方法与原问题相同或相似。
2. 原问题在分解过程中，递归地求解子问题。由于递归都必须有一个终止条件，因此，当分解后的子问题规模足够小时，能够直接求解。
3. 在求解并得到各个子问题的解后应能够采用某种方式、方法合并或构造出原问题的解。

在分治策略中，由于子问题与原问题在结构和解法上的相似性，用分治方法解决的问题，大都采用了递归的形式。在各种排序方法中，如归并排序、快速排序等，都存在有分治的思想。

2.5 分治与递归的联系

1. 分治是一种处理问题的思想，递归是一种编程技巧；
2. 在实际情况中，分治算法大都采用递归来实现；

2.6 案例（海量数据处理）

2.6.1 题目要求

给 10GB 的订单文件按照金额排序这样一个需求，看似是一个简单的排序问题，但是因为数据量大，有 10GB，而我们的机器的内存可能只有 2、3GB ，总之就是小于订单文件的大小因而无法一次性加载到内存，所以基础的排序算法在这样的场景下无法使用；

2.6.2 解题思路

1. 要解决这种数据量大到内存装不下的问题，我们就可以利用分治的思想。我们可以将海量的数据集合根据某种方法，划分为几个小的数据集合，每个小的数据集合单独加载到内存来解决，然后再将小数据集合合并成大数据集合。实际上，利用这种分治的处理思路，不仅能克服内存的限制，还能利用多线程或者多机处理，加快处理速度；
2. 假设现在要给 10GB 的订单排序，我们就可以先扫描一遍订单，根据订单的金额，将 10GB 的文件划分为几个金额区间。比如订单金额为 1 到 100 元的放到一个小文件，101 到 200 之间的放到另一个文件，以此类推。这样每个小文件都可以单独加载到内存排序，最后将这些有序的小文件合并，就是最终有序的 10GB 订单数据了；
3. 如果订单数据存储在类似 GFS 这样的分布式系统上，当 10GB 的订单被划分成多个小文件的时候，每个文件可以并行加载到多台机器上处理，最后再将结果合并在一起，这样并行处理的速度也加快了很多；

3 回溯算法

3.1 介绍

1. 回溯算法是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径；
2. 图的深度优先搜索 DFS 的实现就是借助了回溯算法的思想，除此之外很多经典的数学问题都可以运用回溯算法来解决，比如数独，八皇后，0-1背包等等；

3.2 解题步骤

基本思路：

（1）针对所给问题，定义问题的解空间，它至少包含问题的一个解；
（2）确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间；
（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；

解题步骤：

1. 确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间；
2. 这个开始结点就成为一个活结点，同时也成为当前的扩展结点，在当前的扩展结点处，搜索向纵深方向移至一个新结点，这个新结点就成为一个新的活结点，并成为当前扩展结点；
3. 如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点；
4. 回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止；

3.3 案例（八皇后问题）

3.3.1 问题描述

在 8×8 的国际象棋棋盘上放置八个皇后，使得任意两个皇后都不能处于同一条横行、纵行或斜线上，如下图所示，请问有多少种摆法？

3.3.2 解题思路

1. 八皇后的问题可以延申至 n 皇后的问题，比如一个 n x n 的棋盘上摆放n 个皇后，要求任意两个皇后都不能处于同一条横行、纵行或斜线上。当然了这个问题当 n=1 或者 n>=4 时才有解；

2. 我们可以定义一个一维数组 a[n]，用以保存所有的解，其中 a[i]就表示了把第 i 个皇后放在第 i 行的列数(i 从 0 开始计算)；

3. 由于任意两个皇后不能在同一列，因此任意两个 a[i]和 a[j]的值不能相同（i != j）；

4. 由于任意两个皇后不能在同一对角线上，因此对任意i和j，Math.abs(j - i) != Math.abs(a[j] - a[i])（i != j）；

3.3.3 代码示例（Java）

/**
 * 回溯思想-八皇后问题
 */
public class Queens8 {

    /**
     * 皇后数组：下标标识行数，值标识列数
     */
    private int[] queen;

    /**
     * 计算并输出n皇后的位置
     */
    public void backtrack(int n){
        // 数组初始化
        queen = new int[n];
        // 初始化起点
        for (int i=0;i<queen.length;i++){
            queen[i] = -1;
        }
        //  从第一个皇后开始
        int k=0;
        while (true){
            // 第k个皇后移动一格
            queen[k] += 1;
            //判断是否应该回溯到上一行开始搜索
            if (queen[k]>=n) {
                //第k个皇后移动后溢出，即移出边界，则确定这一行的皇后没有任何位置可选
                if(k>0) {// 如果不是第一个皇后，则第k个皇后起点回归到原始，并回溯到第k-1个皇后
                    queen[k] =-1;
                    k--;
                    continue;  // 跳出下面的判断
                } else {
                    break;// 如果是第一个皇后，则已经遍历所有位置，跳出循环
                }
            }
            // 判断皇后在该位置是否不冲突，如果不冲突，更改目标为下一行进行搜索
            if (!isMatch(k)) {
                k++;
                if (k>=n) {// 如果下标k溢出，即超过了皇后数量，则已经确定一个组合，输出
                    for (int i=0; i<n; i++){
                        System.out.print(queen[i] + " ");
                    }
                    System.out.println();
                    k--;// 将k回溯到最后一行继续探索其他可能性
                }
            }
        }
    }

    /**
     *   判断第k个皇后是否与之前的皇后冲突
     */
    public boolean isMatch(int k){
        for (int i=k-1; i>-1; i--){
            if (queen[k]==queen[i] || Math.abs(queen[k]-queen[i])==Math.abs(k-i)){
                return true;
            }
        }
        return false;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        new Queens8().backtrack(8);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

4 动态规划

4.1 介绍

1. 动态规划（Dynamic Programming，DP）是求解决策过程最优化的过程，能获得全局最优解；
2. 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解；
3. 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的，若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次（比如斐波拉契数列）；
4. 分治自顶向下，动态规划自底向上；
5. 如果把所有的子问题看成一棵树的话，动态规划自底向上，从叶子向根；构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，推得根的值，最后得到一棵完整的树，根的值即为最优值；
6. 需要在给定约束条件下优化某种指标时，动态规划很有用；
7. 每种动态规划解决方案都涉及网格，单元格中的值通常就是要优化的值；
8. 每个单元格都是一个子问题，因此需要考虑如何将问题分解为子问题；
9. 没有放之四海皆准的计算动态规划解决方案的公式；

4.2 应用场景

1. 具有最优子结构性质：指的是问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解；
2. 无后效性：在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，而不关心这个状态是怎么一步一步推导出来的；
3. 具有重叠子问题的问题：即子问题之间是不独立的，一个子问题在以后的决策中可能被多次用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）；通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解时直接查表，这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。