回溯算法

回溯算法，也叫试探法，用于系统地搜索问题的解。回溯算法的核心思想是：沿着一条路向前走，能进则进，不能进则退回来，换一条路重试。

使用回溯算法解决问题，一般分为三个步骤：

• 定义问题的解空间。在该解空间中应该至少包含问题的一个解

• 用易于搜索的方式组织解空间中的节点，比如：

  • 对于八皇后问题，使用树
  • 对于迷宫问题，使用图

• 以深度优先的方式，搜索整个解空间。在搜索的过程中，使用剪枝函数，剪掉那些无法到达最终状态的节点

在确定解空间的组织结构之后，回溯算法从开始节点出发，以深度优先的方式搜索整个解空间。在搜索开始时，开始节点成为活结点，并成为当前扩展节点，然后从当前扩展节点处出发，向纵深方向前进一步，到达一个新节点，这个新节点就成了新的活结点，并且成为当前扩展节点^注释1；如果从当前扩展节点处，无法继续向纵深方向搜索，那么当前扩展节点就成了死节点，此时需要回溯到最近的活结点^注释2，并使之称为当前扩展节点。回溯算法以这种方式递归地在解空间中进行搜索，直到找到问题的解或解空间中没有活结点为止。

• 注释1：
  当搜索到解空间中的某个节点时，需要先判断该节点是否一定不包含问题的解，如果是，则停止对以该节点为根的子树的搜索；否则，进入子树，继续以深度优先的策略进行搜索
• 注释2：
  需要借助栈保存所有活结点，栈顶的活结点，就是当前扩展节点，当当前扩展节点成为死节点时，需要从栈中弹出它，并且当栈空时，回溯算法应该停止搜索，因为此时解空间中已无活结点