Question

回溯算法

Answer 1

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

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

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

国际象棋的棋盘为8*8的方格棋盘。现将”马”放在任意指定的方格中，按照”马”走棋的规则将”马”进行移动(如图所示，如果将空格标成点，就是象棋中的马走“日”字)。要求每个方格只能进入一次，最终使得”马 ”走遍棋盘的64个方格。如图所示，任意一个位置，“马”最多有8个方向可以跳动，所以每次都要依据这最多8个方向进行选择。

这道题在贪心算法中也提到过，这里使用回溯法，是一种便于理解和实现的算法。

注： 这里当时犯了一个错误，当时把 int a = x + moveX[i]写成了x = x + moveX[i],这样就相当于没有进行回溯