对回溯的理解
回溯法的大致意思是这样的:
问题的解往往是树状伸展, 能够使用一个树形结构来表示解空间, 我称之为解空间树吧, 那么解出问题的解的过程就是走完一条根到叶子的路径的过程. 这个树的每一层都代表一个状态, 该层的节点可以看作是此状态下的一个选择, 可以触发下一层的状态. 回溯法从解空间树的根节点开始, 对树进行深度优先的搜索
若当前搜索到的内部节点是满足条件的, 那么就继续沿着这个节点往下一层搜索; 若当前搜索到的是满足条件的叶子节点, 那么就求出一个解了!
若当前搜索到的节点是不满足条件的, 那么就回溯回上一层的节点 R, 从 R 开始往另一个方向深入搜索.
要注意的点是, 我们在回溯上一层节点的时候, 要还原状态.
DFS
DFS 就是深度优先搜索 (Depth First Search), 本质上就是状态的转移, 所以我们要弄清楚我们的状态到底是什么.
八皇后问题
回溯法的经典例题
八个皇后, 8X8 的棋盘, 皇后可以攻击其八个方向上任意距离的另一个皇后, 求如何在棋盘上放置皇后, 使得皇后之间都不能够相互攻击?
问题分析
根据题目的约束条件, 可知每个皇后必然独占一行 / 一列, 为了简化问题增加确定性, 我们可以考虑使用一行一行地放置皇后. 第一个放置的皇后 A 位置确定之后, 第二个皇后 B 必须根据 A 的位置选择, C 又必须根据 AB 的位置继续进行选择...... 这么下去环环相扣, 就构成了一棵解空间树. 我们要搜索的就是这棵树.
状态是什么? 当前放了几个皇后, 放在了哪里. 如何表示这个状态? 8X8 的棋盘, 二维数组再好不过, 至于放了几个皇后, 一个变量就可以解决.
- public static void main(String[] args) {
- Arrays.fill(pos, -1);
- queenSolve(g, 0);
- }
- private static int[][] g = new int[8][8];
- private static int[] pos = new int[8]; // 用来记录每一行 i, 皇后的位置
- /**
- * dfs 的参数列表其实就是我们的状态 递归调用时参数的变化就是状态的转移 param g 棋盘数据, true 有皇后 param cnt
- * 放置了几个皇后, 或者说时放置到第几行了, 我们时一行一行地放
- */
- private static void queenSolve(int[][] g, int cnt) {
- if (cnt == 8) {
- printAns(g);
- return;
- }
- for (int col = 0; col < 8; ++col) {
- if (isValid(cnt, col)) {
- g[cnt][col] = 1;
- pos[cnt] = col;
- queenSolve(g, cnt + 1);
- // 回溯状态
- g[cnt][col] = 0;
- pos[cnt] = -1;
- }
- }
- }
- private static boolean isValid(int x, int y) {
- // 我们是逐行放置的, 之前行必然有皇后
- for (int i = 0; i < x; ++i) {
- if (pos[i] == y || (x - i) == Math.abs(y - pos[i]))
- return false;
- }
- return true;
- }
- private static void printAns(int[][] g) {
- System.out.println("-- new ans --");
- for (int i = 0; i < 8; ++i) {
- for (int j = 0; j < 8; ++j) {
- System.out.print(g[i][j] + " ");
- }
- System.out.println("");
- }
- System.out.println("");
- }
来源: http://www.bubuko.com/infodetail-3460231.html