回溯算法

一、概念

回溯法有通用解法的美称，对于很多问题，如迷宫等都有很好的效果。回溯算法实际上一个深度优先搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回（也就是递归返回），尝试别的路径。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。回溯法说白了就是穷举法。回溯法一般用递归来解决，当然这也带来了一个缺点，时间复杂度一般较大

在我看来回溯算法是一个很好理解的算法，类似于dfs，当条件满足时，就一直执行下去，当条件不满足时，则回溯进行另一个分支的执行，直到所有结果都遍历完成。其实就是一个依靠递归的方法。所以，其时间复杂度也是较大的。

二、经典例题

1. dfs深度优先搜索

这个是比较简单的回溯算法，是对图的一种遍历的方式。即：从图的某个顶点出发访问遍图中所有顶点，且每个顶点仅被访问一次（连通图和非连通图）。

• 深度优先搜索

1. 访问指定的起始定点
2. 若当前访问的顶点的邻接顶点有未被访问的，则任选一个访问之；反之，退回到最近访问过的顶点；直到与起始顶点相通的全部顶点都访问完毕；
3. 若此时图中尚有顶点未被访问，则再选其中一个顶点作为起始顶点并访问之，转 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],这样就相当于没有进行回溯