回溯算法原理及其应用场景
回溯算法核心思想
回溯算法中的回溯意思是回到原来的地方，回：即回去，溯：逆流而上。
在这里，回溯算法是指回到上一步重新决策。
假设把一个人的一生量化，当他遇到人生的岔路口的时候，如果能选择最优的抉择，那么结果将达到人生的最优，用之前我们提到的贪心算法来决策的话，并不一定能得到人生的最优，因为贪心只是选择局部最优，而人生的每一个抉择都会影响未来。如果用回溯算法，将每一个岔路口的选择都做一遍，看看哪个组合是最好的，就可以找到这个人生的最优解了。
回溯算法的应用
回溯算法其实是一种穷举算法，将所有可能发生的情况都列举一遍，选择可行解或最优解。
要理解回溯算法的核心思想，就必须要以具体的例子来讲解，它的应用范围也非常广泛，不仅仅用于搜索算法中，类似数独、八皇后问题、全排列、0-1背包、正则表达式匹配和编译原理中语法分析等
八皇后问题
首先我们来看一下如何用回溯算法来解决著名的八皇后问题，事实上回溯算法虽然能解决八皇后问题，但是效率却是最低的，八皇后问题之所以著名，是因为八皇后问题解法有多种，例如用位运算来解决八皇后问题，效率比回溯高很多。
八皇后问题，说的是在一个8x8的棋牌中，要摆放8个皇后，但是每个皇后的前后左右以及对角线上都不能有其他皇后，因为这几个方向是皇后的攻击方向。
其实很容易能够想到穷举所有的摆放方案就可以了，从第一行开始放，每次只能放在不会被攻击到的地方，遇到无解时，回到上层重新放。
最终代码如下，采用了递归来进行回溯。
int[] result = new int[8];// 下标表示行, 值表示Q存储在哪一列
public void cal8queens(int row) {
if (row == 8) { // 8 个棋子都放置好了，打印结果
printQueens(result);
return;//已经找到解，返回继续寻找下一个解
}
for (int i=0; i<8; i++) { // 每一行都有 8 中放法
if (isOk(row, i)) { // 判断皇后放在i列成不成
result[row] = i; // 成的话记录第row行的棋子放到了i列
cal8queens(row+1); // 继续放下一个皇后
}
}
}
private boolean isOk(int row, int column) {//判断皇后放在这个位置成不成
int leftup = column - 1, rightup = column + 1;
for (int i = row-1; i >= 0; --i) { // 左上角，右上角和正上方方向检查是否存在皇后
if (result[i] == column) return false; //向上考察
if (leftup >= 0) { // 向左上考察
if (result[i] == leftup)
return false;
}
if (rightup < 8) { // 向右上考察
if (result[i] == rightup)
return false;
}
--leftup;
++rightup;
}
return true;
}
private void printQueens(int[] result) { // 打印解
for (int row = 0; row < 8; ++row) {
for (int column = 0; column < 8; ++column) {
if (result[row] == column) {
System.out.print("Q ");
} else {
System.out.print("* ");
}
}
System.out.println();
}
System.out.println();
}
0-1背包问题
0-1背包是一个经典的动态规划问题，但是这里我们采用回溯算法来解决。
现在有一个背包，最高负重W，有n个物品，每个物品重量不等，并且物品不可分割，即要么放要么不放。求能放进背包的物品的最大重量。
在讲贪心算法的时候这个背包问题中的物品的可分割的，因此只需要计算每个物品的单价，来决定放多少，而现在这个问题物品是不可分割的，因此无法使用贪心算法来解决了。
现在采用回溯算法解决，同样的也是将n个物品的放法穷举一遍，选择可以装进背包的最大重量，即n个物品有2n种放法，除去总重超过W的。
public int maxW = Integer.MIN_VALUE; // 记录背包中存放物品的最大重量
// cw 表示当前已经装进去的物品的重量和
// i 表示考察到哪个物品了；
// weight 表示每个物品的重量；
// n 表示物品个数
// w 背包重量；
public void solution(int i, int cw, int[] weight, int n, int w) {
if (cw == w || i == n) { // 装满了或者已经考察到最后一个物品了
if (cw > maxW)
maxW = cw;
return;
}
solution(i+1, cw, items, n, w);//不放当前这个物品
if (cw + items[i] <= w) {// 若这个物品放的进背包
solution(i+1, cw + items[i], items, n, w);
}
}