分治算法和回溯算法

一、分治算法

核心思想就是分而治之，将原问题划分为n个规模较小的，并且结构与原问题相似的子问题，而后递归地解决这些子问题，最后将其结果进行合并，得到原问题地解。但是要求，分解问题和合并结果不能太复杂。

分治算法是一种处理问题的思想，递归是一种编程技巧。一般情况下，分治算法都比较适合使用递归来实现。

比如在讲解八大排序算法中的归并排序时，就是将大的排序问题分解为小的排序问题，再将小的有序数列合并起来形成最开始问题的解。

分治算法应用比较广泛，并不仅限于指导算法思想上，在海量数据处理场景中也可以大显身手。比如海量数据无法直接加载到一台机器的内存中进行处理，那么可以将海量数据分解到n台机器的内存中分别处理，最后将每台机器的处理结果合并再进行最后的处理。当然，并不仅限于内存敏感的问题，CPU敏感的问题也都是同一思路。

二、回溯算法

回溯算法常用于求解路径搜索类的问题。比如，每个路口都有很多岔路，如何选择最优的路径。

其实回溯算法算是作用在枚举之上的，我们需要枚举出来所有的解，然后根据这些解之间的比较得到最有的那个解。而回溯算法在这其中起到的作用就是帮助我们毫不遗漏地枚举每一个解并找到最优解。

比如在图的应用那篇文章里面，我们提到的深度优先搜索算法，先随意选择一条路走到头，然后退回一个继续寻找其它的路，当所有路都找完了，再退回一个继续寻找，如此回溯。

还有八皇后问题，我们需要在8*8的棋盘上，放置8个皇后，使得每个皇后所在的行、列、对角线上都不能有另外一个皇后，总共有多少种放法。这个问题我们把其分为八个步骤，每一个步骤都是先随便放置，看看当前的方案是否符合要求，如果不符合要求，就回溯寻找其它位置，如果符合要求就进行下一个步骤。

还有0-1背包问题，正则表达式匹配问题等，都可以使用回溯的算法思想。