一、概念
回溯法有通用解法的美称，对于很多问题，如迷宫等都有很好的效果。回溯算法实际上一个深度优先搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回（也就是递归返回），尝试别的路径。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。回溯法说白了就是穷举法。回溯法一般用递归来解决，当然这也带来了一个缺点，时间复杂度一般较大
在我看来回溯算法是一个很好理解的算法，类似于dfs，当条件满足时，就一直执行下去，当条件不满足时，则回溯进行另一个分支的执行，直到所有结果都遍历完成。其实就是一个依靠递归的方法。所以，其时间复杂度也是较大的。
二、经典例题
1. dfs深度优先搜索
这个是比较简单的回溯算法，是对图的一种遍历的方式。即：从图的某个顶点出发访问遍图中所有顶点，且每个顶点仅被访问一次（连通图和非连通图）。
- 深度优先搜索
- 访问指定的起始定点
- 若当前访问的顶点的邻接顶点有未被访问的，则任选一个访问之；反之，退回到最近访问过的顶点；直到与起始顶点相通的全部顶点都访问完毕；
- 若此时图中尚有顶点未被访问，则再选其中一个顶点作为起始顶点并访问之，转 2； 反之，遍历结束。
2. 马踏棋盘问题
国际象棋的棋盘为8*8的方格棋盘。现将”马”放在任意指定的方格中，按照”马”走棋的规则将”马”进行移动(如图所示，如果将空格标成点，就是象棋中的马走“日”字)。要求每个方格只能进入一次，最终使得”马 ”走遍棋盘的64个方格。如图所示，任意一个位置，“马”最多有8个方向可以跳动，所以每次都要依据这最多8个方向进行选择。
这道题在贪心算法中也提到过，这里使用回溯法，是一种便于理解和实现的算法。
/**
* @author zmrwego
* @descreption 马踏棋盘问题
* @create 2018-12-21
**/
public class Chess {
//声明棋盘大小
static int n = 8;
//直接声明一个棋盘，初始化为0
static int[][] chess = new int[n][n];
static int times = 0;
//使用回溯法进行踏马
public static void runHorse(int[][] chess, int x, int y) {
chess[x][y] = 1;
//数组代表马跳的8个方向
int[] moveX = {1, 2, 1, 2, -1, -2, -1, -2};
int[] moveY = {2, 1, -2, -1, 2, 1, -2, -1};
times++;
System.out.println(":第" + times + "步,马(" + x + "," + y + ")->");
for (int i = 0; i < moveX.length; i++) {
int a = x + moveX[i];
int b = y + moveY[i];
if ((a>=0 && a<=7 && b>=0 && b<=7)) {
if (chess[a][b] == 0) {
runHorse(chess, a, b);
}
}
}
}
public static void show(int[][] chess){
for (int i = 0; i < n ; i++) {
for (int j = 0; j < n ; j++) {
System.out.print(chess[i][j]+"");
}
System.out.println();
}
}
public static void main(String[] args) {
runHorse(chess, 0, 0);
show(chess);
}
}
注：这里当时犯了一个错误，当时把 int a = x + moveX[i]写成了x = x + moveX[i],这样就相当于没有进行回溯
