回溯法
回溯法的一个流程便是 设置 递归 回溯，循环
背景介绍：回溯法是一种穷举类型的算法，与其说它是一种算法，倒不如说它是一种试法。回溯法并没有什么高深的算法思想，虽然名字起的很高规格，但其实它的算法性连二分查找都比不上。这里说的算法性其实就是指技巧性，对问题特性了解越深入，越能创造出很巧妙的算法，在时间复杂度的级别上提高算法效率。这体现了算法效率与适用性之间的矛盾，二分查找效率很高，但适用性比较低，类似的还有著名的KMP算法。而穷举法效率最低，但几乎适用于所有问题。
好像有点儿扯远了，我们还是接着说回溯法。回溯法是一种试探性算法，从这一点上看，它很像穷举法。但它终究不是穷举法，回溯法是有组织的进行穷举，在试探过程中不断通过题设要求减少搜索空间，而这种减少不是一个一个解的减少，而是对搜索空间进行大规模剪枝，从而使得实际搜索空间远远小于问题的解空间，所以回溯法的实际运行效率还是比较高的。
应用场景：回溯法的应用背景说大很大，说小很小。算法大都在“不得不”的情况 下才会使用，如果有别的算法，那它很有可能比回溯法高效，别忘了，回溯法是基于穷举的。回溯法适用于解排列组合类问题，也就是说目标解是从一个候选空间中选择出来的。从数量级上考虑，设候选空间的大小为n，如果选择是可重复的，那生成的搜索树为完全n叉树，搜索空间为n^n（如0-1背包问题，生成的解空间为高度为n完全二叉树，其中n为物体个数）。如果选择不能重复，那生成的解空间为n!(如TSP问题生成的解空间为n!,其中n为城市个数)。也就是说，当我们通过分析发现问题的解空间为n^n或者n!时，那很可能要用到我们的回溯法了。
搜索策略：要用回溯法解决问题，那首先要确定问题的状态空间树。这个并不是很难，就看每一步选择有多少个可选值就可以了，第一步有8个可选值，那树第一层就有8个节点，第二步有5个可选值，那第一层每个节点都有5个分支，则第二层有8×5=40个节点，以此类推……到第n层一共有m1×m2×……×mn个节点，其中mi为第i步的可选值的个数。
确定了状态空间树，那下一步就是搜索了。这时候就体现出回溯法的优势了，前面不是说了嘛，回溯法的特点就是有规律、有组织的进行搜索，那下面就来看一下回溯法是如何进行搜索的：（PS：这部分内容大都取自清华大学郑宗汉的《算法设计与分析》一书，当然也有自己的一些理解）在开始搜索之前，我们先来说一下我们要做的事情，我们要得到一个解向量solution，每个分量对应每一步选择的结果，显然这个解向量的长度应该为n（我们采用C语言的标准，下标范围为0到n-1）。好了，现在我们有了一个状态空间树（逻辑上的，并不用实现）和一个解向量（物理上的，要用来装数据的）。现在可以开始搜索了，先设定一个下标r，这个r就是解向量的下标，也用于标识状态树的第r行。先做第一步，令r=0，选solution[0]，也就是从树的第0行选择一个值放入solution[0]，显然刚开始我们应该选择第一个，即前面提到的8个里面的第一个。然后看这个半成品解向量是否是可行的，也就是说看看刚才选择的那个值是否满足要求，加入那个值不满足要求，那应该选择第二个，以此类推直到选择一个可行的值，放入solution[0]。然后r++进行第二步，选择solution[1]，同样的，我们应该从树的第二行中选择第一个看构成的解是否可行（此时解向量中包含两个元素），这样的步骤一直进行下去，直到出现这样的情况
（1）r=n-1了，也就是说我们得到了问题的一个可行解，这时候就要看题设要求了，如果只要求找到一个可行解，那此时算法就可以停止了。
（2）某一层的候选值选完了，我们知道，每一层的候选值都有一定个数，如上面提到的例子中第二层只有5个候选值，如果这五个候选值都试探完了还是没有可行解那该怎么办呢？这里体现的思想就是我们回溯法名字的由来，回溯。也就是令r–退回去，从新选择上面的解。比如上面的例子先选择8个中的第一个作为解的一部分，然后发现后面的5个和前面这个都不能组成可行解，那这就说明前面那个选择是不可行的，和后面是不搭配的。所以应该返回去选择8个中的第二个，然后再对5个进行选择，看哪个与这个第二个想匹配。
（3）最后一种情况，因为我们这个过程中有回溯过程，即r–的过程，那可能最后r小于0了，这说明整个树都搜索完了，也就是问题没有可行解。
代码实现：
用回溯法解题一般思想为：
- 在解空间树中，从根节点出发，采用深度优先搜索的思想来遍历解空间树。每一次遍历节点时都判断当前 节点是否为合法解，如果为合法解，那么继续遍历其自子树，如果不是合法节点，那么访问其下一个兄弟节点，如果没有下一个兄就退回到父节点（回溯），访问父节点下一个兄弟节点。
- 回溯法结束的条件是回溯到根节点而且所有子树均已遍历到。
- 回溯法归根结底是一种带有节点判断条件的深度优先搜索算法。
回溯法解题一般步骤：
（1）针对所给问题，确定问题的解空间：
首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
（2）确定结点的扩展搜索规则
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
回溯法一般有两种代码实现方案，递归方法和非递归方法。相比之下，递归设计方法比较简单，用前面提到的r作为递归变量即可，如果满足搜索条件，则递归调用r+1对应函数，如果不满足，则递归调用r-1对应的函数。基础步为当r＜0或r=n-1分别对应无解和得到可行解，这个就不多说了。非递归方法，也就是循环方法设计细节比较多，但只要掌握了其特点，对不同问题的适用性很强（即代码只通过很少的修改就可以应用到不同问题），加之其效率高于递归算法（循环的优势），所以这里我们着重讲一下回溯的非递归代码实现。
算法框架：
（1）问题框架
设问题的解是一个n维向量(a1,a2,………,an),约束条件是ai(i=1,2,3,…..,n)之间满足某种条件，记为f(ai)。
（2）非递归回溯框架
int a[n],i;
2: 初始化数组a[];
3: i = 1;
4: while (i>0(有路可走) and (未达到目标)) // 还未回溯到头
5: {
6: if(i > n) // 搜索到叶结点
7: {
8: 搜索到一个解，输出；
9: }
10: else // 处理第i个元素
11: {
12: a[i]第一个可能的值；
13: while(a[i]在不满足约束条件且在搜索空间内)
14: {
15: a[i]下一个可能的值；
16: }
17: if(a[i]在搜索空间内)
18: {
19: 标识占用的资源；
20: i = i+1; // 扩展下一个结点
21: }
22: else
23: {
24: 清理所占的状态空间； // 回溯
25: i = i –1;
26: }
27: }（3）递归的算法框架
回溯法是对解空间的深度优先搜索，在一般情况下使用递归函数来实现回溯法比较简单，其中i为搜索的深度，框架如下：
int a[n];
2: try(int i)
3: {
4: if(i>n)
5: 输出结果;
6: else
7: {
8: for(j = 下界; j <= 上界; j=j+1) // 枚举i所有可能的路径
9: {
10: if(fun(j)) // 满足限界函数和约束条件
11: {
12: a[i] = j;
13: ... // 其他操作
14: try(i+1);
15: 回溯前的清理工作（如a[i]置空值等）;
16: }
17: }
18: }
19: }回溯法有“通用解题法”之称。用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索
算法。
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一
结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的
解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解
时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
应用举例：纸上谈兵已经做完了，该来点儿实践了。这里举三个小例子以示回溯法的基本应用，更高深的留待大家自己去研究。
第一个例子是八皇后问题，是回溯法应用中很典型的一个。还有一个是图的着色问题，也是很明显的回溯问题。最后一个是全排列问题，也可以用回溯法来解。
直接上代码吧：
八皇后问题：
在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
思路是按行来规定皇后，第一行放第一个皇后，第二行放第二个，然后通过遍历所有列，来判断下一个皇后能否放在该列。直到所有皇后都放完，或者放哪都不行。第一个皇后先放第一行第一列，然后第二个皇后放在第二行第一列、然后判断是否OK，然后第二列、第三列、依次把所有列都放完，找到一个合适继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解。然后回头继续第一个皇后放第二列，后面继续循环……
public class EightQueen {
//一共有多少个皇后（此时设置为8皇后在8X8棋盘，可以修改此值来设置N皇后问题）
int max = 8;
//该数组保存结果，第一个皇后摆在array[0]列，第二个摆在array[1]列
int[] array = new int[max];
/*
* n代表是第几个皇后，皇后n在第array[n]列
*/
public void check(int n){
//终止条件是最后一行已经摆完，因为每摆一行都会判断，所以只要最后一行摆完，说明得到了一个正确解
if(n==max){
print();
return;
}else{
//从第一列开始摆，判断是否和本行本列本斜线有冲突，如果ok，就进入下一列
for(int i=0;i<max;i++){
array[n] = i;
if(judge(n)){
check(n+1);
}
}
}
}
private boolean judge(int n) {
for(int i=0;i<n;i++){
/*
* 判断是否在同一列，只需要看array这两个位置上的数字是否相同
* 判断是否在同一斜线，将棋盘看做一个二维数组，因为不用的棋子在不同行，所以纵坐标就是哪个棋子，横坐标就是列，即array的数字
* 如果两个棋子坐标为(a1,b1)(a2,b2)，当|a2-a1|=|b2-b1|时，才能证明在同一斜线
*/
if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n]-array[i])){
return false;
}
}
return true;
}
private void print() {
for(int i=0;i<array.length;i++){
System.out.print(array[i]+1+" ");
}
System.out.println();
}
public static void main(String[] args) {
new EightQueen().check(0);
}
}下面再看着色问题的代码。
1. bool placeOk(int x,int k,int c,int n)
2. {
3. //自己可实现
4. }
5. bool m_colouring(int n,int m,int x[],int c)
6. {
7. //输入：n为顶点个数，m为颜色种类，x为解向量，c为邻接矩阵
8. for(int i=0;i<n;i++) x[i]=0;//初始化解向量
9. int i = 0; bool flag = false;//初始化
10. while(i>=0){
11. while(x[i]<=m){
12. if(placeOk(x,i,c,n)){//得到可行解
13. if(i==n-1) {flag=true; break;}//得到最终可行解，退出
14. else{//得到部分可行解，搜索下一行
15. i++; x[i]=0;
16. }
17. }
18. else{//当前解不可行
19. x[i]++;
20. }
21. }
22. if (flag) break;
23. x[i]=0;i--;x[i]++;//回溯
24. }
25. if (flag) return true;
26. else return false;
27.
28. } 全排列代码：
全排列问题，输入一个字符串，输出字符串全部排列组合，可能有重复字符固定第一个字符，递归取得首位后面的各种字符串组合；再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合；
递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
假如有重复值呢？
由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。 * 由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。 * 换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数， * 所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！
public static ArrayList<String> Permutation(String str) {
ArrayList<String> list = new ArrayList<>();
if(str!=null && str.length()>0){
PermutationHelper(str.toCharArray(),0,list);
Collections.sort(list);
}
return list;
}
private static void PermutationHelper(char[] charArray, int i, ArrayList<String> list) {
if(i == charArray.length-1){
list.add(String.valueOf(charArray));
}else{
for(int j=i;j<charArray.length;++j){
if(j==i || charArray[j]!=charArray[i]){
// 先交换
swap(charArray,i,j);
// 递归下一节
PermutationHelper(charArray, i+1, list);
// 再回溯。准备下一个
swap(charArray,i,j);
}
}
}
}
private static void swap(char[] charArray, int i, int j) {
char temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
}里面的部分代码没有实现，这一部分也恰好是两个问题不同的部分，即判断当前的解是否是部分可行解。 由于篇幅问题，就不深究这两个例子了，关键希望大家能从中体会出回溯法的模式，具体实现还是要大家仔细琢磨的。
最后总结：通过比较上面三段代码可发现，这几乎就是复制粘贴出来的。这说明回溯法是一种通用性很高的算法模型，这是因为我们回溯法面向的是一棵空间搜索树，这课树已经完成了从实际问题到数学表达的建模。而每棵树的特性都是相当一致的，所以我们的算法也具有高度的一致性。从这个角度看，一旦掌握了回溯法，那以后用起来是比较简单的，所以回溯法是一个很值得学习的算法。