分治、贪心、动态规划、回溯算法思想回顾与总结

目录

 ps.里面提到的实验详细内容在该专栏其他文章中

分治

分治法的思想：

分而治之，关键在于将大问题分割成若干子问题（最好使子问题的规模大致相同），子问题相互独立且与原有问题相同【分】；递归求解出子问题后自底向上合并解，求出原问题的解【治】

适用条件：

• 问题规模缩小到一定程度时容易解决；
• 问题具有最优子结构性质，即原问题的最优解包含子问题的最优解；
• 分解出的子问题是相互独立的，即子问题之间不包含公共子问题；
• 分解出的子问题的解可以合并为原问题的解。

实验中具体的分治思想：

1. 归并排序：先将待排序元素分为两个大小大致相同的子集合，分别对每个集合递归调用归并排序函数，然后将排好序的子集合合并为所要求的排好序的集合；
2. 快速排序：先确定好基准点（可以通过产生一个随机数来获取），重新划分区间，将比他大的数放到右边，小于或等于的数放到左边（不稳定的排序），递归处理左右两段，直到区间只有一个数（在递归的过程中各个元素已经处于正确位置上，不需要再合并）；（挖坑填数+分治）
3. 循环赛日程表：每个选手与其他选手各赛一次（有对称性，甲与乙比即为乙与甲比），共需赛n*（n-1）场【注意：这个对称规律需要将比赛的选手本人也放进矩阵中，而不是只存他每天的对手！！即不能用第i行表示第i+1个选手，而是要将i+1存在第i行的首元素位置，这样才是一个n*n的矩阵，才有对称一说】。这里的分治即考虑到对角分布特殊——对称，将矩阵不断一分为四（递归），直到矩阵成为一个2*2的矩阵，再利用对角对称，将对角复制赋值，最后合并得到结果。

贪心

贪心法的原理：

1. 贪心选择性质：所求问题的整体最优解可通过一系列局部最优的选择，即贪心选择来实现；
2. 最优子结构性质：原问题的最优解包含子问题的最优解
    

      贪心算法常用解题方法：
      常用自顶向下的方式进行，步骤：

1. 套用问题模型：事先定义了限制条件和期望值的一组数据，在满足限制的条件下，使期望值最大；
2. 贪心算法：每次选择对限制值同等贡献量的情况下对期望值贡献最大的数据；
3. 举例验证。

      贪心算法存在以下问题：

• 不能保证给出的是最优解；
• 不能用来求最大/小解问题；
• 只能求满足某些约束条件的可行解的范围

1、单源最短路径：限制条件——单源；期望值——总权值最小。

采用Dijkstra算法，设置顶点集合S并不断地作贪心选择来扩充这个集合，直到该集合包含所有顶点。一个顶点属于集合S当且仅当从源到该顶点的最短路径已知。

2、找零：限制条件——共n分钱；期望值——找的硬币数目最少。

不断做出贪心选择——选择符合要求的面值最大的硬币，直到找了n分钱为止。

3、多机调度：限制条件——m台机器；期望值——让作业在尽可能短的时间内加工完成。

当n > m时，先对作业按要求的执行时间从大到小排序，然后按照这个排好序的顺序，去找目前用时最短的机器，并将该机器加上对应时长，最后取那个使用时间最长的机器所用时间为最优解。

实验体会

贪心算法与分治的共同点在于它们其实都是通过降低问题规模来一步一步解决问题，都要求有最优子结构性质，除此之外，贪心还有一个要求，就是要具有贪心选择性质，即问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这个要求其实是很高的，所以实际生活中并没有很多问题可以通过贪心算法来找到最优解，但是通过贪心来近似寻找最优解是一个很巧妙的想法，就如本次实验中的多机调度问题，它本来是一个NP完全问题，即一个多项式复杂程度的非确定性问题，但是通过使用贪心选择策略我们能设计出较好的近似算法。

总之，明白贪心的优缺点后，我们可以进行适当的舍取，确定自己是否要用贪心来解决遇到的问题，如果用贪心的话可能会出现什么问题。

动态规划

动态规划：

对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。

与分治的区别在于，子问题往往不是相互独立的；

与贪心的区别在于，贪心选择不可撤回，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。

    动态规划原理：

1.  最优子结构性质
2.  重叠子问题——保存子问题的解
3.  无后效性——下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结。

    动态规划关键：

        记住已经求过的解，即存储子问题的每一个解，以备它重复出现

    含重叠子问题的求解方式：

1. 自顶向下的备忘录方法；
2. 自底向上的DP：先解决小问题,再由小问题解决大问题(即由之前存在过的状态推导出后面的状态)

找出状态转移方程（一个递推表达式），动态规划中本阶段的状态往往是上一阶段状态和决策的结果；

                            降规模——找边界条件；

                            扩规模——找状态转移方程（由之前存在过的状态推导出后面的状态)

自底而上是从具体问题分析到抽象问题,也就是从小问题开始求解,一直推广到大问题的求解;自顶而下则相反,是从抽象的问题入手逐渐解决具体的问题,也就是把大问题化小,最后解决小问题

动态规划五部曲：

dp数组及下标含义；递推公式；dp数组如何初始化；遍历顺序；打印dp数组（用于查错）

1. 0-1背包问题：降规模，找边界条件——只有一个物品时直接判断能否放入包中；扩规模，找状态转移方程——如图
2. LIS（最长递增子序列）：降规模，找边界条件——只有一个数字时LIS就是它(故dp数组初始化为1)；扩规模，找状态转移方程——每一个数字的LIS长度可以通过比较排在它前面的数字的LIS+1与当前它的LIS的值，遍历完前面所有数字后即可找出它的LIS长度。

dp[i] = max{dp[j] + 1, dp[i]}，0 <=j < i && height[j] < height[i]

合唱队形安排其实就是找出一个数，它的左边的最长递增子序列与右边的最长递减子序列长度之和最大。

LDS：dp[i] = max{dp[j] + 1, dp[i]}，i < j < n && height[j] < height[i]

       3.五部曲分析：

        0-1背包中dp[i][j]的i表示第0-i个物品，j表示背包容量，数组值表示当容量为j，物品为0-i时最优解的价值总量；从递推公式中可以看出dp应该如何初始化——i最小值为0，而递推公式中有i-1，所以i只能从1开始，即要先将i为0时的dp数组初始化，j=0时值就为0；从递推公式中可以看出要想求出dp[i][j]则要先知道dp[i-1][j]和dp[i-1][j-wi]的值，即该元素上面的元素以及左上的元素，故遍历顺序随意，因为无论是先遍历背包容量还是先遍历物品，都可以在求某个元素的值前先得知其上面和左上的元素值。

回溯

回溯算法：

带优化的穷举法，具有限界函数的深度优先搜索算法。

优化是指在搜索过程中用剪枝函数避免无效搜索。

常用剪枝函数有两种（不一定两种同时存在，但有可能两种同时存在）：

1. 约束函数，剪去不满足约束条件的左子树；
2. 限界函数，剪去得不到最优解的右子树

可以解决的问题：

1. 组合问题
2. 切割问题：给一个字符串及约束条件，问有几种切割方式
3. 排列问题：与组合的区别在于排列强调顺序
4. 子集问题
5. 棋盘问题：如N皇后问题

    回溯算法的理解：

1. 递归是有终止的，回溯与递归相辅相成，可以抽象为一棵n叉树。树的宽度为处理的集合大小，常用for循环遍历；树的深度即为递归的深度。
2. 通常处理逻辑： 

 void backtrack(){      if(终止条件){          收集结果;          return;`     }      for(集合元素){          处理结点;          递归函数;          回溯操作;//撤销处理结果      }  }

通过递归控制有多少层for循环，递归的每一层相当于一个for循环。for循环横向遍历，递归纵向遍历，回溯不断调整结果集。

1. 八皇后问题：约束条件（没有限界函数）——同一列/斜线上是否已经放了一个皇后（行不用管，因为就是在找当前行能不能放皇后，一行一行地找，若在该行遍历完n之前能够找到位置放置皇后，则向下一行递归，若没有位置可放，则向上回溯）
2. 批处理作业调度问题：剪枝函数——total < bestT(当前用时比已找到的bestT小才往下遍历)
3. 排列问题：约束条件——当前数字是否已经被排列