Java学习笔记：回溯法

回溯法

回溯法有“通用解题法”之称，用它可以系统的搜索问题的所有解。通俗的说，用回溯法可以找到问题的所有解。

它在问题的解空间树中，按照深度优先搜索策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一节点时，先判断该节点是否包含问题的解，如果肯定不包含，则跳过对以此改节点为根的子树的搜索，逐层向其祖先进行回溯；否则，进入该子树，继续按照深度优先搜索策略。

回溯发的算法框架和基本思想

1，明确定义问题的解空间（就是问题的所有可能的解）

2，得到问题的解空间后，将解空间很好的组织起来，使得能方便用回溯法搜索整个解空间。（一般将解空间组织成树或者图的）形式

3，确定了解空间的组织结构后，回溯法从开始节点（根节点）出发，以深度优先搜索整个解空间。这个开始节点称为活节点，同时也成为当前的扩展节点。在当前扩展节点处，搜索向纵深方向移至一个新节点。这个新节点成为新的活节点并且成为当前扩展节点。如果在当前扩展节点处不能再向纵深方向移动（即叶节点），则当前扩展节点就成为死节点。此时，应往回移动至最近的活节点处，并使这个活节点为当前的扩展节点。直至找到所有的解或者解空间中已经无活节点为止。

回溯法基本思想以及此处标红部分一定要充分理解。

N后问题

问题描述：

在nxn的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n x n的棋盘上放着n个皇后，任何两个皇后不放在同一列同一行，或同一斜线。

算法设计：

用x[i]表示第i个皇后放在棋盘的第i行的第x[i]列。由问题得，两个皇后的位置分别是（i,j）和（k,l）不能放在同一列，即x[i] 不等于x[j], 不在同一斜线即 k=| l-j/k-i | 不等于1.

所有可能的解为 n的n次方，

组织：为一个完全n叉树

image

回溯法

package edu.xatu;

public class NQueen1 {

**static** **int** *n*; // 皇后个数

**static** **int**[] *x*; // 当前解

**static** **long** *sum*; // 当前找到的可行方案数

**public** **static** **long** nQueen(**int** nn) {

    *n* = nn;

    *sum* = 0;

    *x* = **new** **int**[*n* + 1];

    **for** (**int** i = 0; i <= *n*; i++)

        *x*[i] = 0;

    *backtrack*(1);

    **return** *sum*;

}

**private** **static** **boolean** place(**int** k) {// 判断皇后是否能放入k列

    **for** (**int** j = 1; j < k; j++) { // 与前k-1个皇后的位置比较

        **if** ((Math.*abs*(k - j) == Math.*abs*(*x*[j] - *x*[k])) || (*x*[j] == *x*[k])) // 同对角线或同列

            **return** **false**;

    }

    **return** **true**;

}

**private** **static** **void** backtrack(**int** t) {

    **if** (t > *n*) {

        *sum*++;

        **for** (**int** i = 1; i <= *n*; i++)

            // 输出当前方案

            System.***out***.printf("%5d", *x*[i]);

        System.***out***.println();

    } **else**

        **for** (**int** i = 1; i <= *n*; i++) {

            *x*[t] = i; // 把第t个皇后依次放入n个格子，看是否可行

            **if** (*place*(t)) // 可行就继续放第t+1个皇后

                *backtrack*(t + 1);

        }

}

// 测试

**public** **static** **void** main(String[] args) {

    System.***out***.println("n皇后问题方案可行数为:" + *nQueen*(4));

}

}

运行结果：

image