1 概念

回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法

满足回溯条件的某个状态的点称为“回溯点”。

许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

2 基本思想

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。

当探索到某一结点时，要先判断该结点是否包含问题的解

如果包含，就从该结点出发继续探索下去
如果该结点不包含问题的解，则逐层向其祖先结点回溯

（其实回溯法就是对隐式图的深度优先搜索算法）。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

3 用回溯法解题的一般步骤：

（1）针对所给问题，确定问题的解空间：

首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。

（2）确定结点的扩展搜索规则

（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

4 算法框架

（1）问题框架

设问题的解是一个n维向量(a1,a2,………,an),约束条件是ai(i=1,2,3,…..,n)之间满足某种条件，记为f(ai)。

（2）非递归回溯框架

   1: 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为搜索的深度，框架如下：

   1: 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: }

例题

机器人的运动范围，剑指offer

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

public class Solution {

    public int movingCount(int threshold, int rows, int cols) {
        if (threshold < 1 || rows < 1 || cols < 1) {
            return 0;
        }
        boolean[][] visited = new boolean[rows][cols];
        return movingCountCore(0, 0, rows, cols, visited, threshold);
    }
 
    private int movingCountCore(int i, int j, int rows, int cols, boolean[][] visited, int threshold) {
 
        if (i < 0 || i >= rows || j < 0 || j >= cols)
            return 0;
        if (getDigitNum(i) + getDigitNum(j) > threshold || visited[i][j])
            return 0;
            
        visited[i][j] = true;
        // 标记访问过，这个标志visited不需要回溯，因为只要被访问过即可。
        // 因为如果能访问，访问过会加1.不能访问，也会标记下被访问过。
        return movingCountCore(i - 1, j, rows, cols, visited, threshold)
                + movingCountCore(i + 1, j, rows, cols, visited, threshold)
                + movingCountCore(i, j - 1, rows, cols, visited, threshold)
                + movingCountCore(i, j + 1, rows, cols, visited, threshold)
                + 1;
    }
 
    private int getDigitNum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

判断在一个矩阵中是否存在一条包含某字符串所有字符的路径

路径可以从矩阵中的任意一个格子开始
每一步可以在矩阵中向左，向右，向上，向下移动一个格子
如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子

例如[ab c e s f c s a d e e]是3*4矩阵，其包含字符串"bcced"的路径，但是矩阵中不包含“abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

回溯算法这是一个可以用回朔法解决的典型题。

首先，在矩阵中任选一个格子作为路径的起点。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的第i个位置。
如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。除在矩阵边界上的格子之外，其他格子都有4个相邻的格子。重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。

由于回朔法的递归特性，路径可以被开成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。
由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。
当矩阵中坐标为（row,col）的格子和路径字符串中相应的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下一个字符如果4个相邻的格子都没有匹配字符串中下一个的字符，表明当前路径字符串中字符在矩阵中的定位不正确，

我们需要回到前一个，然后重新定位。一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置。

public class Solution {
    // 选取一个节点（i，j）为起始点，递归遍历这个节点上下左右的元素是否和待匹配的字符数组中元素相同，
    // 相同则继续遍历这个相同节点的上下左右元素，不同则后退回来。
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        boolean[] visited = new boolean[matrix.length];
 
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (hasPathCore(matrix, rows, cols, i, j, str, visited, 0))
                    return true;
        return false;
    }
 
    /**
     * @param matrix
     *            矩阵
     * @param rows
     *            矩阵行数
     * @param cols
     *            矩阵列数
     * @param i
     *            矩阵行数索引
     * @param j
     *            矩阵列数索引
     * @param str
     *            要查找的目标字符串
     * @param visited
     *            对应的boolean矩阵是否访问过
     * @param index
     *            str字符串的下标，从0开始
     * @return
     */
    private boolean hasPathCore(char[] matrix, int rows, 
            int cols, int i, int j, char[] str, boolean[] visited,
            int index) {
        int idx = i * cols + j;
        if (i < 0 || j < 0 || i >= rows || j >= cols)
            return false;
        if (visited[i * cols + j] || matrix[idx] != str[index])
            return false;
        if (index == str.length - 1)
            return true;

        // 剪枝 状态位
        visited[idx] = true;
        index++;
        if (hasPathCore(matrix, rows, cols, i + 1, j, str, visited, index)
                || hasPathCore(matrix, rows, cols, i, j + 1, str, visited, index)
                || hasPathCore(matrix, rows, cols, i - 1, j, str, visited, index)
                || hasPathCore(matrix, rows, cols, i, j - 1, str, visited, index))
            return true;
        visited[idx] = false;
        // 此题不index--也通过，why？？？？
        index--;
        return false;
 
    }
}

回溯算法