前言：
而今小伙伴们对“谷歌分支界限法算法面试题”可能比较着重，你们都需要剖析一些“谷歌分支界限法算法面试题”的相关资讯。那么小编同时在网络上汇集了一些对于“谷歌分支界限法算法面试题””的相关内容，希望大家能喜欢，姐妹们一起来了解一下吧！目录
一. 分治算法
二．动态规则算法
三．贪心算法
四．回溯算法
五．分支限界法
一.分治算法1.什么是分治算法
分治法
分治法，字面意思是“分而治之”，就是把一个复杂的1问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并，这个思想是很多高效算法的基础，例如排序算法(快速排序，归并排序)，傅里叶变换(快速傅里叶变换)等。
分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
这个定义看起来有点类似递归的定义。关于分治和递归的区别，我们在排序（下）的时候讲过，分治算法是一种处理问题的思想，递归是一种编程技巧。实际上，分治算法一般都比较适合用递归来实现。分治算法的递归实现中，每一层递归都会涉及这样三个操作：
分解：将原问题分解成一系列子问题；
解决：递归地求解各个子问题，若子问题足够小，则直接求解；
合并：将子问题的结果合并成原问题。
分治算法能解决的问题，一般需要满足下面这几个条件：
原问题与分解成的小问题具有相同的模式；
原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别，等我们讲到动态规划的时候，会详细对比这两种算法；
具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。
基本思想
分治法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
2.分治算法的例子:归并排序
归并排序
归并排序（ MERGE － SORT ）是利用归并的思想实现的排序方法，该算法采用经典的分治（ divide - and - conquer )策略（分治法将问题分（ divide ）成一些小的问题然后递归求解，而治（ conquer ）的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之）。
基本思想
流程图（以对数组[8,4,5,7,1,3,6,2]排序为例）
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将
[4,5,7,8］和［1,2,3,6］两个已经有序的子序列，合并为最终序列［1,2,3,4,5,6,7,8]，来看下实现步骤。
3.代码实现package Sort;
import java.util.Arrays;/** * 归并排序： * * 利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解， * * 而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。 * @author lenovo * */public class MergeSort { public static void main(String[] args) { int[] a= {5,8,6,3,9,8,7,1,4,21,-8,46}; int[] temp=new int[a.length]; mergeSort(a, 0, a.length-1, temp); System.out.println(Arrays.toString(a)); } public static void mergeSort(int[] arr,int left,int right,int[] temp) { if(left<right) { int mid=(left+right)/2; mergeSort(arr, left, mid, temp); mergeSort(arr, mid+1,right, temp); merge(arr, left, mid, right, temp); } } public static void merge(int[] arr,int left,int mid,int right,int[] temp) { int l=left;//左边序列的起始位置 int r=mid+1;//右边序列的起始位置 int t=0;//中间数组的当前元素下标 while(l<=mid &&r<=right ) {//左边或右边没结束 //那边小就将那边的元素放入到临时数组中 if(arr[l]<=arr[r]) { temp[t++]=arr[l++]; }else { temp[t++]=arr[r++]; } } //while循环结束，说明有一边已经遍历完毕，将另一边剩余的元素放入到临时数组中 while(l<=mid) { temp[t++]=arr[l++]; } while(r<=right) { temp[t++]=arr[r++]; } //将临时数组中的有序序列copy到原数组中 t=0; int templeft=left; while(templeft<=right) { arr[templeft++]=temp[t++]; } }}4.大规模计算框架MapReduce中的分治思想MapReduce是Google大数据处理的三驾马车之一，另外两个是GFS和Bigtable。它在倒排索引、PageRank计算、网页分析等搜索引擎相关的技术中都有大量的应用。
分治思想在海量数据处理中的应用
分治算法思想的应用是非常广泛的，并不仅限于指导编程和算法设计。它还经常用在海量数据处理的场景中。我们前面讲的数据结构和算法，大部分都是基于内存存储和单机处理。但是，如果要处理的数据量非常大，没法一次性放到内存中，这个时候，这些数据结构和算法就无法工作了。
比如，给10GB的订单文件按照金额排序这样一个需求，看似是一个简单的排序问题，但是因为数据量大，有10GB，而我们的机器的内存可能只有2、3GB这样子，无法一次性加载到内存，也就无法通过单纯地使用快排、归并等基础算法来解决了。
要解决这种数据量大到内存装不下的问题，我们就可以利用分治的思想。我们可以将海量的数据集合根据某种方法，划分为几个小的数据集合，每个小的数据集合单独加载到内存来解决，然后再将小数据集合合并成大数据集合。实际上，利用这种分治的处理思路，不仅仅能克服内存的限制，还能利用多线程或者多机处理，加快处理的速度。
比如刚刚举的那个例子，给10GB的订单排序，我们就可以先扫描一遍订单，根据订单的金额，将10GB的文件划分为几个金额区间。比如订单金额为1到100元的放到一个小文件，101到200之间的放到另一个文件，以此类推。这样每个小文件都可以单独加载到内存排序，最后将这些有序的小文件合并，就是最终有序的10GB订单数据了。
如果订单数据存储在类似GFS这样的分布式系统上，当10GB的订单被划分成多个小文件的时候，每个文件可以并行加载到多台机器上处理，最后再将结果合并在一起，这样并行处理的速度也加快了很多。不过，这里有一个点要注意，就是数据的存储与计算所在的机器是同一个或者在网络中靠的很近（比如一个局域网内，数据存取速度很快），否则就会因为数据访问的速度，导致整个处理过程不但不会变快，反而有可能变慢。
MapReduce中的分治思想
我们刚刚举的订单的例子，数据有10GB大小，可能给你的感受还不强烈。那如果我们要处理的数据是1T、10T、100T这样子的，那一台机器处理的效率肯定是非常低的。而对于谷歌搜索引擎来说，网页爬取、清洗、分析、分词、计算权重、倒排索引等等各个环节中，都会面对如此海量的数据（比如网页）。所以，利用集群并行处理显然是大势所趋。
一台机器过于低效，那我们就把任务拆分到多台机器上来处理。如果拆分之后的小任务之间互不干扰，独立计算，最后再将结果合并。这不就是分治思想吗？
实际上，MapReduce框架只是一个任务调度器，底层依赖GFS来存储数据，依赖Borg管理机器。它从GFS中拿数据，交给Borg中的机器执行，并且时刻监控机器执行的进度，一旦出现机器宕机、进度卡壳等，就重新从Borg中调度一台机器执行。
尽管MapReduce的模型非常简单，但是在Google内部应用非常广泛。它除了可以用来处理这种数据与数据之间存在关系的任务，比如MapReduce的经典例子，统计文件中单词出现的频率。除此之外，它还可以用来处理数据与数据之间没有关系的任务，比如对网页分析、分词等，每个网页可以独立的分析、分词，而这两个网页之间并没有关系。网页几十亿、上百亿，如果单机处理，效率低下，我们就可以利用MapReduce提供的高可靠、高性能、高容错的并行计算框架，并行地处理这几十亿、上百亿的网页。
二. 动态规则算法动态规划算法的思想
动态规划算法处理的对象是多阶段复杂决策问题，动态规划算法和分治算法类似，其基本思想也是将待求解问题分解成若干个子问题(阶段)，然后分别求解各个子问题(阶段)，最后将子问题的解组合起来得到原问题的解，但是与分治算法不同的是，子问题往往不是相互独立的，而是相互联系又相互区别的
动态规划算法问题求解的目标是获取导致问题最优解的最优决策序列(最优策略)。对于一个决策序列，可以用一个数值函数(目标函数)衡量这个决策的优劣。
最优性原理
动态规划算法的最优性原理：一个最优决策序列具有这样的性质，不论初始状态和第一步决策如何，对前面的决策所形成的状态而言，其余的决策必须按照前一次决策所产生的新状态构成一个最优决策序列。
最优性原理体现为问题的最优子结构特性，对于一个问题，如果能从较小规模的子问题的最优解求得较大规模同类子问题的最优解，最终得到给定问题的最优解，也就是问题的最优解中所包含的子问题的最优解，这种性质被称为最优子结构性质。最优子结构特性使得在从较小问题的解构造较大问题的解时，只需考虑子问题的最优解，然后以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解，它保证了原问题的最优解可以通过求解子问题的最优解来获得，最优子结构的特性是动态规划算法求解问题的必要条件。
动态规划算法的三大特点如果求解的问题满足最优性原理，则说明用动态规划算法有可能解决该问题，在分析问题的最优子结构时，所使用的方法具有普遍性。要注意一个问题可以有多种方式刻画它的最优子结构，有些表示方法的求解速度更快(空间占用少，问题的维度低)。递归定义最优解决方案。动态规划的每一步决策都依赖于子问题的解，动态规划算法求解最优化问题的步骤为:找出最优解的结构，具体来说就是看这个问题是否满足最优子结构特性；其次递归定义一个最优解的值，即构造原问题和子问题之间的递归方程，原问题的最优解可以通过子问题的最优解获得。以自底向上的方式计算出最优解的值(最优解的目标函数的值)。对子问题的分解是基于原问题的分解的基础之上进行的，而且这些子问题的分解过程是相互独立的。在对原问题分解的过程中，会出现大量的共享重叠子问题，为了避免对大量重叠子问题的重复计算，一般动态规划算法从自底向上开始计算，对每一个问题只解一次，并且保存求解子问题的最优值，当再需要求解这个子问题的时候，可以用常数时间查看一下结果，而不是再递归的去求解每一个问题的解，因此提高了动态规划算法的效率。动态规划算法中的0/1背包问题
0/1背包问题的规则是不允许该物品进行拆分，即只有把物品放入和不放入两个基本状态，要使用动态规划算法求解决如何放物品才可以是背包中的物品的总价值达到最高。
示例
有一个载重为10的背包，现有4类物品，每类物品的重量分别为(w0,w1,w2,w3)=(2,3,4,7),它们的价值分别为(p0,p1,p2,p3)=(1,3,5,9)。试问如何装载能够使背包容纳物品的价值最大。
package 算法设计与分析;import java.util.Arrays;import java.util.Scanner;//m表示的是背包的容量，a表示有多少种类的物品，数组w用与存放每类物品的重量，数组val用于存放每类物品的价值public class my { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print("请输入背包的容量:"); int m = scanner.nextInt(); Scanner inScanner = new Scanner(System.in); System.out.print("请输入物品的个数:"); int a = inScanner.nextInt(); int[] w = new int[a + 1]; System.out.print("请输入物品的重量:" + " "); for (int i = 1; i <= a; i++) { w[i] = inScanner.nextInt(); } int[] val = new int[a+ 1]; System.out.print("请输入物品的价值:" + " "); for (int i = 1; i <= a; i++) { val[i] = inScanner.nextInt(); } int n = val.length; int[][] path = new int[n +1][m+1 ]; //创建二维数组 //v[i][j]：表示在前i个物品中能够装入容量为j的背包中的最大价值 int[][] v = new int[n +1][m + 1]; //初始化第一行和第一列 for (int i = 0; i < v.length; i++) {//v.length:获取二维数组的行数 v[i][0] = 0;//将第一列设置为0 } for (int i = 0; i < v[0].length; i++) {//v[0].length：获取二维数组的列数 v[0][i] = 0;//将第一行设置为0 } for (int i = 1; i < v.length; i++) {//int i = 1 不处理第一行 for (int j = 1; j < v[0].length; j++) {//int j = 1 不处理第一列 if (w[i - 1] > j) { v[i][j] = v[i - 1][j]; } else { if (v[i - 1][j] < (val[i - 1] + v[i - 1][j - w[i - 1]])) { v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]]; //把当前情况记录到path path[i][j] = 1; } else { v[i][j] = v[i - 1][j]; } } } } //输出二维数组： for (int[] ints : v) { System.out.println(Arrays.toString(ints)); } //输出最后我们是放入的那些商品 int i = path.length - 1;//行的最大下标 int j = path[0].length - 1;//列的最大下标 while (i > 0 && j > 0) {//从path的最后开始找 if (path[i][j] == 1) { System.out.printf("第%d个商品放入背包\n", i-1); j -= w[i - 1]; } i--; } }}输入一个背包容量为10，里面有4类物品，物品的重量分别为2，3，4，7，物品的价值分别为1，3，5，9
结果
动态规划算法的优点
若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
三.贪心算法基本概念
在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以，对所采用的贪心策略一定要仔细分析其是否满足无后效性。
基本思路
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
贪心算法适用的问题
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。
贪心算法的实现框架从问题的某一初始解出发；while（能朝给定总目标前进一步）{利用可行的决策，求出可行解的一个解元素；}由所有解元素组合成问题的一个可行解；贪心策略的选择
因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。
例题分析——[背包问题]
有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
分析：
目标函数： ∑pi最大 约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？（2）每次挑选所占重量最小的物品装入是否能得到最优解？（3）每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
（1）贪心策略：选取价值最大者。反例：
W=30 物品：A B C 重量：28 12 12 价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
（3）贪心策略：选取单位重量价值最大的物品。反例：
W=30 物品：A B C 重量：28 20 10 价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
纸币找零问题
假设1元、2元、5元、10元、20元、50元、100元的纸币，张数不限制，现在要用来支付K元，至少要多少张纸币？
很显然，我们很容易就想到使用贪心算法来解决，并且我们所根据的贪心策略是，每一步尽可能用面值大的纸币即可。当然这是正确的，代码如下：
1.public static void greedyGiveMoney(int money) {2. System.out.println("需要找零: " + money);3. int[] moneyLevel = {1, 5, 10, 20, 50, 100};4. for (int i = moneyLevel.length - 1; i >= 0; i--) {5. //取商6. int num = money/ moneyLevel[i];7. //取余数8. int mod = money % moneyLevel[i];9. money = mod;10. if (num > 0) {11. System.out.println("需要" + num + "张" + moneyLevel[i] + "块的");12. }13. if(mod==0) { 14. break; 15. }16.17. }18. }（1）如果不限制纸币的金额，那这种情况还适合用贪心算法么。比如1元，2元，3元，4元，8元，15元的纸币，用来支付K元，至少多少张纸币？
经我们分析，这种情况是不适合用贪心算法的，因为我们上面提供的贪心策略不是最优解。比如，纸币1元，5元，6元，要支付10元的话，按照上面的算法，至少需要1张6元的，4张1元的，而实际上最优的应该是2张5元的。
（2）如果限制纸币的张数，那这种情况还适合用贪心算法么。比如1元10张，2元20张，5元1张，用来支付K元，至少多少张纸币？
同样，仔细想一下，就知道这种情况也是不适合用贪心算法的。比如1元10张，20元5张，50元1张，那用来支付60元，按照上面的算法，至少需要1张50元，10张1元，而实际上使用3张20元的即可；
（3）所以贪心算法是一种在某种范围内，局部最优的算法。
活动选择问题
假定一个有n个活动(activity)的集合S={a1,a2,….,an}，这些活动使用同一个资源（例如同一个阶梯教室），而这个资源在某个时刻只能供一个活动使用。每个活动ai都有一个开始时间si和一个结束时间fi，其中0<=si<fi<正无穷。一旦被选择后，ai发生在半开时间区间[si,fi)期间。如果两个活动ai和aj满足[si,fi)和[sj,fj)不重叠，则称它们是兼容的。也就说，若si style="margin: 0px; padding: 0px; box-sizing: border-box;">=fj或sj>=fi，则ai和aj是兼容的。在活动选择问题中，我们希望选出一个最大兼容活动集。假定活动已按结束时间fi的单调递增顺序排序（排序的时间复杂度为O(nlogn)）：
f1<=f2<=f3<=f4<=...<=fn-1<=fn
考虑如下活动集合
活动i
1
2
3
4
5
6
7
8
9
10
11
si
1
3
0
5
3
5
6
8
8
2
12
fi
4
5
6
7
8
9
10
11
12
13
14
可以看到，{a3,a9,a11}是由相互兼容的活动组成。但它不是一个最大集，{a1,a4,a8,a11}更大，是一个最大集，最大集可以有多个不同的,比如{a2,a4,a9,a11}。
假设：Sij表示在ai结束之后，在aj开始之前的活动的集合。Aij表示Sij的一个最大相互兼容的活动子集。那么只要Sij非空，则Aij至少会包含一个活动，假设为ak。那么可以将Aij分解为：Aij = Aik+ak+Akj。假设Cij为Aij的大小，那么有Cij=cik+ckj+1。但是我们并不知道具体是k等于多少的时候，可以让ak一定位于Aij中，所以我们采用动态规划的方式，遍历所有可能的k值，来取得。于是有：
接下来，如果按照动态规划的方式，就可以采用自底向上的递归来求解最优的解。
但是贪心算法却要简单许多，贪心算法直接在每一步选择当前看来最好的选择。比如在一开始的时候，我们要选择在Aij中的第一个活动，我们选择活动结束时间最早的那个活动，这样能够给其他活动尽可能的腾出多余的时间。而后每一步都在剩下的活动中选取，也遵循类似的原则。由于获取已经按照fi排序好，所以这里第一个选择的活动就是a1。但是问题来了，我们能否确定a1一定在Aij中呢，在这个问题中，答案是肯定的，可以给出简单的证明：
假设Aij是Sij的某个最大兼容活动集，假设Aij中，最早结束的活动是an，分两种情况：
①如果an=a1，则得证
②如果an不等于a1，则an的结束时间一定会晚于a1的结束时间，我们用a1去替换Aij中的an，于是得到A，由于a1比an结束的早，而Aij中的其他活动都比an的结束时间开始 的要晚，所以A中的其他活动 都与a1不想交，所以A中的所有活动是兼容的，所以A也是Sij的一个最大兼容活动集。
于是证明了命题。
根据上面的结论，我们可以给出贪心算法在解决这个问题的两种方式：递归和迭代方式，两种算法都是按照自顶向下来求解问题的。
Java实现两种贪心算法策略:
1.public class Activity {2. /**3. * 递归找寻最大兼容的活动4. * @param activiy 可以同时进行的活动5. * @param si 活动i的开始使劲6. * @param fi 活动i的结束时间7. * @param index 活动开始下标因为已经按结束时间排序，所以开始是08. * @param i 兼容活动的下标9. */10. private static void recursiveActivitySelector(int[] activiy,int[] si,int[] fi,int index,int i) {11. //获取第二个活动12. int m = index+1;13. int n =si.length;14. //寻找活动的活动开始时间晚于上一个活动的活动结束时间，那么第二个活动就是可以进行的15. while(m<n&&si[m]<=fi[index]) {16. //继续寻找17. m++;18. }19. //到这里若是m还没有大于n就表明找到了20. if(m<n) {21. //活动下标记录的是活动的序号，从1开始22. activiy[i]=m+1;23. recursiveActivitySelector(activiy,si,fi,m,i+1);24. }25. }26.27. /**28. * 迭代方式29. * @param activiy 可以同时进行的活动30. * @param si 活动i的开始使劲31. * @param fi 活动i的结束时间32. */33. private static void GreedyActiivtySelector(int[] activiy,int[] si,int[] fi) {34. //选择活动135. int start=0;36. int index = 0;37. int n = si.length;38. activiy[start++]=index+1;39. //从第二个开始40. for(int m=1;m<n;m++) {41. if(si[m]>=fi[index]) {42. //活动m的开始时间晚于上一个活动的结束时间，活动有效43. activiy[start++]=m+1;44. //然后再以该活动开始寻找45. index=m;46. }47. }48. }49.50.51. public static void main(String[] args) {52. //活动i已经按fi的时间排序，排序的时间复杂度为O(nlogn)53. int[] si=new int[]{1,3,0,5,3,5,6,8,8,2,12};54. int[] fi=new int[]{4,5,6,7,8,9,10,11,12,13,14};55. int[] activity = new int[si.length];56. int[] activity2 = new int[si.length];57. //默认第一个活动58. activity[0]=1;59. System.out.println("递归贪心算法求出的最大相互兼容活动子集：");60. recursiveActivitySelector(activity,si,fi,0,1);61. for (int i = 0; i < activity.length; i++) {62. if(activity[i]!=0) {63. System.out.print(activity[i]+";");64. }65. }66. System.out.println();67. System.out.println("迭代贪心算法求出的最大相互兼容活动子集：");68. GreedyActiivtySelector(activity2,si,fi) ;69. for (int i = 0; i < activity2.length; i++) {70. if(activity2[i]!=0) {71. System.out.print(activity2[i]+";");72. }73. }74. }75.76.}运行结果如下
递归贪心算法求出的最大相互兼容活动子集：1;4;8;11;迭代贪心算法求出的最大相互兼容活动子集：1;4;8;11;
这里迭代的代码更加简洁！
假设实现活动已经按照fi的升序排列好了的话，会发现实际上贪心算法在处理这个问题的时候只做了一次遍历，所以算法复杂度为O(n)。
四. 回溯算法什么叫回溯算法
对于回溯算法的定义，百度百科上是这样描述的：回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
看明白没，回溯算法其实就是一个不断探索尝试的过程，探索成功了也就成功了，探索失败了就在退一步，继续尝试……，
组合总和
组合总和算是一道比较经典的回溯算法题，其中有一道题是这样的。
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
这题说的很明白，就是从1-9中选出k个数字，他们的和等于n，并且这k个数字不能有重复的。所以第一次选择的时候可以从这9个数字中任选一个，沿着这个分支走下去，第二次选择的时候还可以从这9个数字中任选一个，但因为不能有重复的，所以要排除第一次选择的，第二次选择的时候只能从剩下的8个数字中选一个……。这个选择的过程就比较明朗了，我们可以把它看做一棵9叉树，除叶子结点外每个节点都有9个子节点，也就是下面这样
从9个数字中任选一个，就是沿着他的任一个分支一直走下去，其实就是DFS（如果不懂DFS的可以看下373，数据结构-6,树），二叉树的DFS代码是下面这样的
public static void treeDFS(TreeNode root) { if (root == null) return; System.out.println(root.val); treeDFS(root.left); treeDFS(root.right);}这里可以仿照二叉树的DFS来写一下9叉树，9叉树的DFS就是通过递归遍历他的9个子节点，代码如下
public static void treeDFS(TreeNode root) { //递归必须要有终止条件 if (root == null) return; System.out.println(root.val); //通过循环，分别遍历9个子树 for (int i = 1; i <= 9; i++) { //2，一些操作，可有可无，视情况而定 treeDFS("第i个子节点"); //3，一些操作，可有可无，视情况而定 }}DFS其实就相当于遍历他的所有分支，就是列出他所有的可能结果，只要判断结果等于n就是我们要找的，那么这棵9叉树最多有多少层呢，因为有k个数字，所以最多只能有k层。来看下代码
public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> res = new ArrayList<>(); dfs(res, new ArrayList<>(), k, 1, n); return res;}private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n) { //终止条件，如果满足这个条件，再往下找也没什么意义了 if (list.size() == k || n <= 0) { //如果找到一组合适的就把他加入到集合list中 if (list.size() == k && n == 0) res.add(new ArrayList<>(list)); return; } //通过循环，分别遍历9个子树 for (int i = start; i <= 9; i++) { //选择当前值 list.add(i); //递归 dfs(res, list, k, i + 1, n - i); //撤销选择 list.remove(list.size() - 1); }}代码相对来说还是比较简单的，我们来分析下（如果看懂了可以直接跳过）。
1，代码dfs中最开始的地方是终止条件的判断，之前在426，什么是递归，通过这篇文章，让你彻底搞懂递归中讲过，递归必须要有终止条件。
2，下面的for循环分别遍历他的9个子节点，注意这里的i是从start开始的，所以有可能还没有9个子树，前面说过，如果从9个数字中选择一个之后，第2次就只能从剩下的8个选择了，第3次就只能从剩下的7个中选择了……
3，在第20行dsf中的start是i+1，这里要说一下为什么是i+1。比如我选择了3，下次就应该从4开始选择，如果不加1，下次还从3开始就出现了数字重复，明显与题中的要求不符
4，for循环的i为什么不能每次都从1开始，如果每次都从1开始就会出现结果重复，比如选择了[1，2]，下次可能就会选择[2，1]。
5，如果对回溯算法不懂的，可能最不容易理解的就是最后一行，为什么要撤销选择。如果经常看我公众号的同学可能知道，也就是我经常提到的分支污染问题，因为list是引用传递，当从一个分支跳到另一个分支的时候，如果不把前一个分支的数据给移除掉，那么list就会把前一个分支的数据带到下一个分支去，造成结果错误（下面会讲）。那么除了把前一个分支的数据给移除以外还有一种方式就是每个分支都创建一个list，这样每个分支都是一个新的list，都不互相干扰，也就是下面图中这样
代码如下
public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> res = new ArrayList<>(); dfs(res, new ArrayList<>(), k, 1, n); return res;}private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n) { //终止条件，如果满足这个条件，再往下找也没什么意义了 if (list.size() == k || n <= 0) { //如果找到一组合适的就把他加入到集合list中 if (list.size() == k && n == 0) res.add(new ArrayList<>(list)); return; } //通过循环，分别遍历9个子树 for (int i = start; i <= 9; i++) { //创建一个新的list，和原来的list撇清关系，对当前list的修改并不会影响到之前的list List<Integer> subList = new LinkedList<>(list); subList.add(i); //递归 dfs(res, subList, k, i + 1, n - i); //注意这里没有撤销的操作，因为是在一个新的list中的修改，原来的list并没有修改， //所以不需要撤销操作 }}我们看到最后并没有撤销的操作，这是因为每个分支都是一个新的list，你对当前分支的修改并不会影响到其他分支，所以并不需要撤销操作。
注意：大家尽量不要写这样的代码，这种方式虽然也能解决，但每个分支都会重新创建list，效率很差。
要搞懂最后一行代码首先要明白什么是递归，递归分为递和归两部分，递就是往下传递，归就是往回走。递归你从什么地方调用最终还会回到什么地方去，我们来画个简单的图看一下
这是一棵非常简单的3叉树，假如要对他进行DFS遍历，当沿着1→2这条路径走下去的时候，list中应该是[1，2]。因为是递归调用最终还会回到节点1，如果不把2给移除掉，当沿着1→4这个分支走下去的时候就变成[1，2，4]，但实际上1→4这个分支的结果应该是[1，4]，这是因为我们把前一个分支的值给带过来了。当1，2这两个节点遍历完之后最终还是返回节点1，在回到节点1的时候就应该把结点2的值给移除掉，让list变为[1]，然后再沿着1→4这个分支走下去，结果就是[1，4]。
我们来总结一下回溯算法的代码模板吧
private void backtrack("原始参数") { //终止条件(递归必须要有终止条件) if ("终止条件") { //一些逻辑操作（可有可无，视情况而定） return; } for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) { //一些逻辑操作（可有可无，视情况而定） //做出选择 //递归 backtrack("新的参数"); //一些逻辑操作（可有可无，视情况而定） //撤销选择 }}有了模板，回溯算法的代码就非常容易写了，下面就根据模板来写几个经典回溯案例的答案。
八皇后问题
八皇后问题也是一道非常经典的回溯算法题，前面也有对八皇后问题的专门介绍，有不明白的可以先看下394，经典的八皇后问题和N皇后问题。他就是不断的尝试，如果当前位置能放皇后就放，一直到最后一行如果也能放就表示成功了，如果某一个位置不能放，就回到上一步重新尝试。比如我们先在第1行第1列放一个皇后，如下图所示
然后第2行从第1列开始在不冲突的位置再放一个皇后，然后第3行……一直这样放下去，如果能放到第8行还不冲突说明成功了，如果没到第8行的时候出现了冲突就回到上一步继续查找合适的位置……来看下代码
//row表示的是第几行public void solve(char[][] chess, int row) { //终止条件，row是从0开始的，最后一行都可以放，说明成功了 if (row == chess.length) { //自己写的一个公共方法，打印二维数组的， //主要用于测试数据用的 Util.printTwoCharArrays(chess); System.out.println(); return; } for (int col = 0; col < chess.length; col++) { //验证当前位置是否可以放皇后 if (valid(chess, row, col)) { //如果在当前位置放一个皇后不冲突， //就在当前位置放一个皇后 chess[row][col] = 'Q'; //递归，在下一行继续…… solve(chess, row + 1); //撤销当前位置的皇后 chess[row][col] = '.'; } }}全排列问题给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
这道题我们可以把它当做一棵3叉树，所以每一步都会有3种选择，具体过程就不在分析了，直接根据上面的模板来写下代码
public List<List<Integer>> permute(int[] nums) { List<List<Integer>> list = new ArrayList<>(); backtrack(list, new ArrayList<>(), nums); return list;}private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) { //终止条件 if (tempList.size() == nums.length) { //说明找到一一组组合 list.add(new ArrayList<>(tempList)); return; } for (int i = 0; i < nums.length; i++) { //因为不能有重复的，所以有重复的就不能选 if (tempList.contains(nums[i])) continue; //选择当前值 tempList.add(nums[i]); //递归 backtrack(list, tempList, nums); //撤销选择 tempList.remove(tempList.size() - 1); }}是不是感觉很简单。
子集问题
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
我们还是根据模板来修改吧
public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> list = new ArrayList<>(); //先排序 Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, 0); return list;}private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) { //注意这里没有写终止条件，不是说递归一定要有终止条件的吗，这里怎么没写，其实这里的终止条件 //隐含在for循环中了，当然我们也可以写if(start>nums.length) rerurn;只不过这里省略了。 list.add(new ArrayList<>(tempList)); for (int i = start; i < nums.length; i++) { //做出选择 tempList.add(nums[i]); //递归 backtrack(list, tempList, nums, i + 1); //撤销选择 tempList.remove(tempList.size() - 1); }}所以类似这种题基本上也就是这个套路，就是先做出选择，然后递归，最后再撤销选择。在讲第一道示例的时候提到过撤销的原因是防止把前一个分支的结果带到下一个分支造成结果错误。不过他们不同的是，一个是终止条件的判断，还一个就是for循环的起始值，这些都要具体问题具体分析。下面再来看最后一到题解数独。
解数独
数独大家都玩过吧，他的规则是这样的
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
过程就不在分析了，直接看代码，代码中也有详细的注释，这篇讲的是回溯算法，这里主要看一下backTrace方法即可，其他的可以先不用看
//回溯算法public static boolean solveSudoku(char[][] board) { return backTrace(board, 0, 0);}//注意这里的参数，row表示第几行，col表示第几列。private static boolean backTrace(char[][] board, int row, int col) { //注意row是从0开始的，当row等于board.length的时候表示数独的 //最后一行全部读遍历完了，说明数独中的值是有效的，直接返回true if (row == board.length) return true; //如果当前行的最后一列也遍历完了，就从下一行的第一列开始。这里的遍历 //顺序是从第1行的第1列一直到最后一列，然后第二行的第一列一直到最后 //一列，然后第三行的…… if (col == board.length) return backTrace(board, row + 1, 0); //如果当前位置已经有数字了，就不能再填了，直接到这一行的下一列 if (board[row][col] != '.') return backTrace(board, row, col + 1); //如果上面条件都不满足，我们就从1到9中选择一个合适的数字填入到数独中 for (char i = '1'; i <= '9'; i++) { //判断当前位置[row，col]是否可以放数字i，如果不能放再判断下 //一个能不能放，直到找到能放的为止，如果从1-9都不能放，就会下面 //直接return false if (!isValid(board, row, col, i)) continue; //如果能放数字i，就把数字i放进去 board[row][col] = i; //如果成功就直接返回，不需要再尝试了 if (backTrace(board, row, col)) return true; //否则就撤销重新选择 board[row][col] = '.'; } //如果当前位置[row，col]不能放任何数字，直接返回false return false;}//验证当前位置[row，col]是否可以存放字符cprivate static boolean isValid(char[][] board, int row, int col, char c) { for (int i = 0; i < 9; i++) { if (board[i][col] != '.' && board[i][col] == c) return false; if (board[row][i] != '.' && board[row][i] == c) return false; if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' && board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; } return true;}回溯算法总结
回溯算法要和递归结合起来就很好理解了，递归分为两部分，第一部分是先往下传递，第二部分到达终止条件的时候然后再反弹往回走，我们来看一下阶乘的递归
其实回溯算法就是在往下传递的时候把某个值给改变，然后往回反弹的时候再把原来的值复原即可。比如八皇后的时候我们先假设一个位置可以放皇后，如果走不通就把当前位置给撤销，放其他的位置。如果是组合之类的问题，往下传递的时候我们把当前值加入到list中，然后往回反弹的时候在把它从list中给移除掉即可。
五. 分支限界法基本概念
类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
一般过程
由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。
分支限界法的搜索策略：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。
回溯法和分支限界法的区别
回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解。
分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解。
注：深度优先搜索一般用栈，广度优先搜索一般用队列实现！
分支限界法分为如下两种类型队列式（FIFI,先进先出）分支限界法。队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选择下一个结点作为扩展节点。优先队列式分支限界法。优先队列式分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的节点优先级选取下一个结点作为扩展节点。电路布线问题—分支限界法求解
1、问题描述：
布线问题：印刷电路板将布线区域划分成n×m个方格阵列，要求确定连接方格阵列中的方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。
2、算法应用：
用分支限界法解此布线问题。分支限界法类似回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但分支限界法只找出满足约束条件的一个最优解，并且以广度优先或最小耗费优先的方式搜索解空间树T。树T是一棵子集树或排列树。在搜索时，每个结点只有一次机会成为扩展结点，并且一次性产生其所有儿子结点。从活结点表中选择下一扩展结点有两种方式：（1）队列式（FIFO） （2）优先队列式。分支限界法广泛应用于单源最短路径问题，最大团问题，布线问题，电路板排列问题等。
3、求解思路：
用队列式分支限界法来考虑布线问题。布线问题的解空间是一个图，则从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。接着，从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。
4、算法思路：
在实现上述算法时，
（1）定义一个表示电路板上方格位置的类Position。
它的2个成员row和col分别表示方格所在的行和列。在方格处，布线可沿右、下、左、上4个方向进行。沿这4个方向的移动分别记为0，1，2，3。下表中，offset[i].row和offset[i].col(i= 0,1,2,3)分别给出沿这4个方向前进1步相对于当前方格的相对位移。
（2）用二维数组grid表示所给的方格阵列。
初始时，grid[i][j]= 0, 表示该方格允许布线，而grid[i][j]= 1表示该方格被封锁，不允许布线。
5、举例说明：
一个7×7方格阵列布线如下：
起始位置是a =(3,2),目标位置是b =(4,6),阴影方格表示被封锁的方格。当算法搜索到目标方格b时，将目标方格b标记为从起始位置a到b的最短距离。此例中， a到b的最短距离是9。
6、Java代码实现
1.public class WireRouter {2. public int[][] grid;//方格阵列;=0表示该方格运行布线；=1表示被封锁，不允许布线3. public int size;//方格阵列大小4. public int pathLen;//最短线路长度5. public LinkedList<Position> q;//扩展结点队列，用list存储6. public Position start;//起始位置7. public Position finish;//终点8. public Position[] path;//最短路径9. public WireRouter(int[][] grid,int size,Position start,Position finish){10. this.grid=grid;11. this.size=size;12. this.start=start;13. this.finish=finish;14. }15. /**16. * 方格所在位置17. * @author Lican18. *19. */20. public static class Position{21. public int row;//行22. public int col;//列23.24. public Position(int r ,int c){25. row=r;26. col=c;27. }28. }29. /**30. *计算从起始位置start到目标位置finish的最短布线路径31. * @return 找到最短布线路径则返回true，否则返回false32. */33. public boolean findPath(){34. if(start.row==finish.row&&start.col==finish.col){//start==finish,最短路径为035. pathLen=0;36. return true;37. }38.39. //初始化相对位移40. Position[] offset=new Position[4];41. offset[0]=new Position(0,1);//右42. offset[1]=new Position(1,0);//下43. offset[2]=new Position(0,-1);//左44. offset[3]=new Position(-1,0);//上45.46. //设置方格阵列“围墙”，方便处理方格边界的情况47. for(int i=0;i<=size+1;i++){48. grid[0][i]=grid[size+1][i]=1;//顶部和底部49. grid[i][0]=grid[i][size+1]=1;//左边和右边50. }51.52. Position here=new Position(start.row,start.col);53. grid[start.row][start.col]=2;//数字0,1表示方格的开放或封锁所以，表示距离时，让所有距离都加2；起始位置的距离为0+2=254. int numOfNbrs=4;//相邻方格数55.56. //以下为标记可达的方格位置57. q=new LinkedList<Position>();58. Position nbr=new Position(0,0);59. do{60. //标记可达的相邻方格(每个方格有四个相邻方格)61. for(int i=0;i<numOfNbrs;i++){62. nbr.row=here.row+offset[i].row;63. nbr.col=here.col+offset[i].col;64. if(grid[nbr.row][nbr.col]==0){//该方格未被标记，且该方格允许布线65. grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;66. if(nbr.row==finish.row&&nbr.col==finish.col)67. break;68. q.add(new Position(nbr.row,nbr.col));69. }70. }71.72. //检测是否到达目标位置finish73. if(nbr.row==finish.row&&nbr.col==finish.col)74. break;75. if(q.isEmpty())76. return false;77.78. here=q.poll();79. }while(true);80.81. //构造最短布线路径82. pathLen=grid[finish.row][finish.col]-2;83. path=new Position[pathLen];84.85. //从目标位置finish开始向起始位置回溯86. here=finish;87. for(int j=pathLen-1;j>=0;j--){88. path[j]=here;89. //找前驱位置90. for(int i=0;i<numOfNbrs;i++){91. nbr.row=here.row+offset[i].row;92. nbr.col=here.col+offset[i].col;93. if(grid[nbr.row][nbr.col]==j+2)94. break;95. }96. here=new Position(nbr.row,nbr.col);97. }98. System.out.println("最短路线为：");99. for(int j=0;j<pathLen-1;j++){100. System.out.println("点"+(j+1)+"位置: 行-"+path[j].row+" 列-"+path[j].col);101. }102. System.out.println("布线长度为："+pathLen);103. return true;104. }105.106.107. public static void main(String[] args) {108. Scanner sc=new Scanner(System.in);109. System.out.println("请输入方格阵列大小：");110. String s1=sc.nextLine();111. Integer size=Integer.parseInt(s1);112.113. System.out.println("请输入起始点的行和列，用空格隔开：");114. String s2=sc.nextLine();115. String[] s3=s2.split(" ");116. int startRow=Integer.parseInt(s3[0]);117. int startCol=Integer.parseInt(s3[1]);118. Position start=new Position(startRow,startCol);119.120. System.out.println("请输入结束点的行和列，用空格隔开：");121. String s4=sc.nextLine();122. String[] s5=s4.split(" ");123. int finishRow=Integer.parseInt(s5[0]);124. int finishCol=Integer.parseInt(s5[1]);125. Position finish=new Position(finishRow,finishCol);126.127. int[][] grid=new int[size+2][size+2];128. System.out.println("请输入方格阵列：");129. for(int i=1;i<=size;i++){130. String str=sc.nextLine();131. String[] strs=str.split(" ");132. for(int j=0;j<strs.length;j++){133. grid[i][j+1]=Integer.parseInt(strs[j]);134. }135. }136.137. WireRouter w=new WireRouter(grid,size,start,finish);138. w.findPath(); 139. }140.}运行输出如下：
请输入方格阵列大小：7请输入起始点的行和列，用空格隔开：2 3请输入结束点的行和列，用空格隔开：4 6请输入方格阵列：0 0 1 0 0 0 00 0 1 1 0 0 00 0 0 0 1 0 00 0 0 1 1 0 01 0 0 0 1 0 01 1 1 0 0 0 01 1 1 0 0 0 0最短路线为：点1位置: 行-3 列-3点2位置: 行-4 列-3点3位置: 行-5 列-3点4位置: 行-5 列-4点5位置: 行-6 列-4点6位置: 行-6 列-5点7位置: 行-6 列-6点8位置: 行-5 列-6布线长度为：9
标签： #谷歌分支界限法算法面试题
