Backtracking (Depth First Search)

Table of Contents

1 回溯法

回溯法(Backtracking)是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

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

回溯算法本质上是一种“穷举法”,很容易想到,没有什么先进思想在里面(《算法导论》一书中没有对其的介绍)。不过, 由于回溯法在搜索过程中不断略过某些显然不合适的情况(称为剪枝),所以搜索的空间大大小于一般的穷举法。 回溯法的缺点:一般来说回溯法的复杂度比较高,当问题规模非常大时,不宜采用回溯法。

当回溯法用于树型结构的问题时,又可称为深度优先搜索(Depth first search)。

回溯法一般采用的是递归实现。回溯法也可以采用迭代实现,可参考《计算机算法设计与分析(第3版, 王晓东编)》,第5章

2 回溯法实例:N皇后问题

问题描述:在一个 \(N \times N\) 的国际象棋棋盘上放置 \(N\) 个皇后,且任何2个皇后不能放在同一行或同一列或同一斜行上。问有多少种放法?并输出所有的正确放法。

2.1 问题分析

分析:这个问题可通过一个一个尝试来解决。
如何测试皇后会受到攻击?设两个皇后位置为(i,j)、(m,n),则有:
“i != m”,可表示不在同一行;
“j != n”,可表示不在同一列;
“|i + j| != |m + n|”,可表示不在斜率为1的斜线上;
“|i - j| != |m - n|”,可表示不在斜率为-1的斜线上。

如何表示皇后?用二维数组显然可以,使用一维数组更好,把皇后位置存储为一个n维数组a[n], 数组中第i个元素的值代表第i行的皇后的列的位置 ,这样便可以把问题的空间规模进行压缩。

2.2 编程实现

下面是N皇后问题的一个解法。

// 该程序是一个解N皇后问题的算法(采用递归解决)
#include <stdio.h>

#define N 8          //这里是解决8皇后问题

int solution[N];     //其中solution[i]表示第i行的皇后所在的列值,仅保存最近一次尝试的方案
int solution_count;  //记录正确放置方案的总数

/* 测试第row行皇后的放置是否成功,前面的行(0到row-1行)已经放置好了皇后 */
bool is_valid(int row) {
    for (int i = 0; i < row; i++) {   // i代表行,测试第row行的皇后和前面已经放好的row-1行是否会攻击
        if (solution[row] == solution[i]) {          // 在同一列上
            return false;
        }
        if (row-solution[row] == i-solution[i]) {    // 在\方向斜线上
            return false;
        }
        if (row+solution[row] == i+solution[i]) {    // 在/方向斜线上
            return false;
        }
    }
    return true;
}

/* 前面的 row-1 行都已放置好了,开始放第 row 行 */
void backtrack(int row) {
    int k;
    if (row > N-1) {         //终止条件,意味着找到了一个可行解。测试条件也可为row==N
        solution_count++;
        /* 找到解后,循环打印八皇后棋局(下标转换成从1开始) */
        for(k=0 ; k<N ; k++) printf("(%d,%d) ",k+1, solution[k]+1);
        printf("\n");
    } else {
        for(int i=0 ; i<N ; i++ ) {  //对第row行的皇后进行每一列进行放置尝试。
            solution[row] = i;       //放置第row行的皇后,即把其列其设为i。
            if(is_valid(row)) {      //测试放置的第row行皇后会不会有攻击。
                backtrack(row + 1);  //继续放置下一行的皇后。
            }                        //省略的else分支,是“剪枝”步骤。
        }
    }
}

void queens() {
    backtrack(0);  //从第一行(数组下标为0)开始尝试放置皇后
}

int main(void) {
    queens();
    printf("Total Solutions: %d\n", solution_count);
    return 0;
}

用上面程序解决4皇后问题(把N设置为4),可得到下面的输出:

(1,2) (2,4) (3,1) (4,3)
(1,3) (2,1) (3,4) (4,2)
Total Solutions: 2

Author: cig01

Created: <2011-11-02 Wed 00:00>

Last updated: <2017-04-28 Fri 22:58>

Creator: Emacs 25.1.1 (Org mode 9.0.7)