zhengrenzhe's blog   About

回溯法

回溯法是暴力搜索法的一种,它采用暴力搜索的思想,将解决办法分步,一步一步尝试,如果有错,则返回上一步或上几步,直到求出正确答案。回溯法的典型应用,就是计算 n 皇后问题,本文就是通过n 皇后的计算来理解回溯法的思想。

那么何谓 n 皇后问题呢?它是一道以国际象棋为背景的题目:

如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n (来源于维基百科)

也就是说如何在 nxn 棋盘上方式 n 个棋子,使它们不在同一横线、竖线、对角线。使用回溯法计算该问题,可按行来分步计算。简单起见,假设有如下4x4棋盘:

首先在(0, 0)处放一颗棋子,目前只有一颗棋子,满足条件,第一行完成。

然后进入第二行,在(0, 1)处放一颗棋子:

此时布局不满足条件,则撤回这一步,将这一行棋子放到(1, 1)处:

仍不满足条件,再撤回这一步,将棋子放到(2, 1)处:

此时布局满足条件,进入到下一行。但是下一行并无满足条件的布局,故当前布局已经无法再继续下去。则需要回退步骤到

将第二行的棋子放到(3, 1)处:

此时布局满足条件,进入到下一层。并在下一层中不断尝试,一层满足则进入下一层,不满足则退出这一层,直到进入到最后一层,找到最后一层满足条件的布局后,即为一个解。

如此这样不断循环,会尝试遍历每一层的每个位置,整个遍历的过程就像构建一颗树,只不过在构建的过程中将不满足条件的枝叶减去了,这样的方法就称为回溯法。

下面用Python来描述一下这个过程:

class NQueen(object):
    """N 皇后"""

    def __init__(self, num=4):
        self.__num = num
        self.__chessboard = [[0] * num for _ in range(num)]
        self.__count = 1

    @classmethod
    def is_vaild(cls, cur_chessboard: list):
        """判断棋盘是否合法"""
        indexs = [line.index(1) for line in cur_chessboard if 1 in line]

        # 由于计算过程保证两个棋子不可能在同一行,故无需检查棋子是否在同一行的情况

        # 检查是否在同一列
        if len(indexs) != len(set(indexs)):
            return False

        # 检查是否在对角线
        for iindex, i in enumerate(indexs):
            for jindex, j in enumerate(indexs):
                if iindex == jindex:
                    continue
                if abs(i - j) == abs(iindex - jindex):
                    return False
        return True

    def print(self, i=0):
        """计算 n 皇后"""
        # 遍历深度已至第num层,说明已经求出了一个解
        if i == self.__num:
            print("NO: %s" % self.__count)
            for line in self.__chessboard:
                print(line)
            print("--------")
            self.__count += 1
        else:
            # 遍历当前行的每一个位置
            j = 0
            while j < self.__num:
                # 当前位置放棋子
                self.__chessboard[i][j] = 1
                # 若当前布局合法则进入下一行
                if NQueen.is_vaild(self.__chessboard):
                    self.print(i + 1)
                # 移除当前位置的棋子
                self.__chessboard[i][j] = 0
                j += 1

# 计算8皇后
NQueen(8).print()

通过该算法我们可以抽象出一个回溯法的一般模式:

def get():
    if 已经计算到终点:
        输出
    else:
        j = 0
        while j < 某一条件:
            进行某一操作
            if 当前情况满足:
                # 进入下一层
                get()
            撤回刚才的操作
            j += 1

回溯法还是比较简单的,理解起来很容易,到这里就差不多了。

← C 语言中数字的存储方式  多行文本截断的新思路:shear.js →