回溯法有“通用的解题法”之称，用它可以系统地搜索一个问题的所有解或任一解。

基本思想

在确定了解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。

从根结点开始成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为一个新的活结点，并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。

回溯法的算法框架

回溯法的算法框架有非递归和递归两种方式。

回溯法的典型实例

背包问题

N 皇后问题

N 皇后问题要求在一个 n * n 格的棋盘上放置 n 个皇后，使得彼此之间不处于同一行、同一列或同一斜线上。

参考链接

  • 《软件设计师教程》