常见算法思想6：回溯法

回溯法

回溯法也叫试探法，试探的处事方式比较委婉，它先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一进行枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。如果当前候选解除了不满足问题规模要求外能够满足所有其他要求时，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。

使用回溯法解题的基本步骤如下所示：

（1）针对所给问题，定义问题的解空间。
（2）确定易于搜索的解空间结构。
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯法为了求得问题的正确解，会先委婉地试探某一种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，马上会自觉地退回一步重新选择，然后继续向前试探，如此这般反复进行，直至得到解或证明无解时才死心。

效率分析

下面是回溯的3个要素。
（1）解空间：表示要解决问题的范围，不知道范围的搜索是不可能找到结果的。
（2）约束条件：包括隐性的和显性的，题目中的要求以及题目描述隐含的约束条件，是搜索有解的保证。
（3）状态树：是构造深搜过程的依据，整个搜索以此树展开。

回溯算法适合解决没有要求求最优解的问题。如果采用，一定要注意跳出条件及搜索完成的标志，否则会陷入泥潭不可自拔。

下面是影响算法效率的因素：

• 搜索树的结构，解的分布，约束条件的判断。
• 改进回溯算法的途径。
• 搜索顺序。
• 节点少的分支优先，解多的分支优先。
• 让回溯尽量早发生。

回溯法搜索解空间时，通常采用两种策略避免无效搜索，提高回溯的搜索效率:

• 用约束函数在扩展结点处剪除不满足约束的子树；
• 用限界函数剪去得不到问题解或最优解的子树。

例题

N皇后问题：在一个N*N大小的国际象棋棋盘上放置N个皇后棋子，使得所有的皇后都是安全的（即任意两个皇后都无法攻击到对方）。

分析：

为缩小规模，我们用显示的国际象棋8*8的八皇后来分析。按照国际象棋的规则，皇后的攻击方式是横，竖和斜向。
皇后可以攻击到同一列所有其它棋子，因此可推导出每1列只能存在1个皇后，即每个皇后分别占据一列。棋盘一共8列，刚好放置8个皇后。

为了摆放出满足条件的8个皇后的布局，可以按如下方式逐步操作：

1. 在第0行找到一个位置放置第1个皇后；
2. 在第1行找到一个位置放置第2个皇后；
3. 在第2行找到一个位置放置第3个皇后；
4. 对第3，4，5，6，7行都执行放置操作；
5. 当执行完“在第7行找到一个放置第8个皇后”这一操作完毕后，问题求解完毕。
   观察1，2，3，4 这些操作步骤，可以发现是一个重复的动作，抽象一下，即“在第 n 行放下第 n+1 个皇后”，n 从0到7。

把规模放大到N行N列也一样，下面用回溯法解决N皇后问题：

Go语言描述

const N = 8

func NQueens() {
    // 开辟一个一维数组保存可能的结果
    result := make([]int, N)
    // 从第一行开始试探放置棋子
    place(result, 0)
}

// 递归：在保证已放置行安全情况下，放置下一行棋子
func place(result []int, row int) {
    // 所有行棋子放满后输出
    if row == N {
        fmt.Println(result) // 输出答案
        return
    }

    // 逐列试探
    for column := 0; column < N; column++ {
        // 试探在 column 列 处放下棋子，并检验是否安全
        result[row] = column
        if safe(result, row) {
            // 棋子安全，放置下一行棋子
            place(result, row+1)
        }
    }
}

// 验证当前棋子是否安全
func safe(result []int, row int) bool {
    // 循环验证是否互相攻击
    for c := 0; c < row; c++ {
        if isAttack(result, c, row) {
            return false
        }
    }
    return true
}

// 攻击试探，如果被攻击则返回true
func isAttack(result []int, c int, row int) bool {
    
    switch {
    case result[c] == result[row]:
        return true
    case result[row]-result[c] == c-row:
        return true
    case result[row]-result[c] == row-c:
        return true
    }
    return false
}

执行：

func TestNQueens(t *testing.T) {
    NQueens()
}


=== RUN   TestNQueens
[0 4 7 5 2 6 1 3]
[0 5 7 2 6 3 1 4]
[0 6 3 5 7 1 4 2]
[0 6 4 7 1 3 5 2]
[1 3 5 7 2 0 6 4]
[1 4 6 0 2 7 5 3]
[1 4 6 3 0 7 5 2]
[1 5 0 6 3 7 2 4]
[1 5 7 2 0 3 6 4]
[1 6 2 5 7 4 0 3]
[1 6 4 7 0 3 5 2]
[1 7 5 0 2 4 6 3]
[2 0 6 4 7 1 3 5]
[2 4 1 7 0 6 3 5]
[2 4 1 7 5 3 6 0]
[2 4 6 0 3 1 7 5]
[2 4 7 3 0 6 1 5]
[2 5 1 4 7 0 6 3]
[2 5 1 6 0 3 7 4]
[2 5 1 6 4 0 7 3]
[2 5 3 0 7 4 6 1]
[2 5 3 1 7 4 6 0]
[2 5 7 0 3 6 4 1]
[2 5 7 0 4 6 1 3]
[2 5 7 1 3 0 6 4]
[2 6 1 7 4 0 3 5]
[2 6 1 7 5 3 0 4]
[2 7 3 6 0 5 1 4]
[3 0 4 7 1 6 2 5]
[3 0 4 7 5 2 6 1]
[3 1 4 7 5 0 2 6]
[3 1 6 2 5 7 0 4]
[3 1 6 2 5 7 4 0]
[3 1 6 4 0 7 5 2]
[3 1 7 4 6 0 2 5]
[3 1 7 5 0 2 4 6]
[3 5 0 4 1 7 2 6]
[3 5 7 1 6 0 2 4]
[3 5 7 2 0 6 4 1]
[3 6 0 7 4 1 5 2]
[3 6 2 7 1 4 0 5]
[3 6 4 1 5 0 2 7]
[3 6 4 2 0 5 7 1]
[3 7 0 2 5 1 6 4]
[3 7 0 4 6 1 5 2]
[3 7 4 2 0 6 1 5]
[4 0 3 5 7 1 6 2]
[4 0 7 3 1 6 2 5]
[4 0 7 5 2 6 1 3]
[4 1 3 5 7 2 0 6]
[4 1 3 6 2 7 5 0]
[4 1 5 0 6 3 7 2]
[4 1 7 0 3 6 2 5]
[4 2 0 5 7 1 3 6]
[4 2 0 6 1 7 5 3]
[4 2 7 3 6 0 5 1]
[4 6 0 2 7 5 3 1]
[4 6 0 3 1 7 5 2]
[4 6 1 3 7 0 2 5]
[4 6 1 5 2 0 3 7]
[4 6 1 5 2 0 7 3]
[4 6 3 0 2 7 5 1]
[4 7 3 0 2 5 1 6]
[4 7 3 0 6 1 5 2]
[5 0 4 1 7 2 6 3]
[5 1 6 0 2 4 7 3]
[5 1 6 0 3 7 4 2]
[5 2 0 6 4 7 1 3]
[5 2 0 7 3 1 6 4]
[5 2 0 7 4 1 3 6]
[5 2 4 6 0 3 1 7]
[5 2 4 7 0 3 1 6]
[5 2 6 1 3 7 0 4]
[5 2 6 1 7 4 0 3]
[5 2 6 3 0 7 1 4]
[5 3 0 4 7 1 6 2]
[5 3 1 7 4 6 0 2]
[5 3 6 0 2 4 1 7]
[5 3 6 0 7 1 4 2]
[5 7 1 3 0 6 4 2]
[6 0 2 7 5 3 1 4]
[6 1 3 0 7 4 2 5]
[6 1 5 2 0 3 7 4]
[6 2 0 5 7 4 1 3]
[6 2 7 1 4 0 5 3]
[6 3 1 4 7 0 2 5]
[6 3 1 7 5 0 2 4]
[6 4 2 0 5 7 1 3]
[7 1 3 0 6 4 2 5]
[7 1 4 2 0 6 3 5]
[7 2 0 5 1 4 6 3]
[7 3 0 2 5 1 6 4]
--- PASS: TestNQueens (0.00s)
PASS