|
|
|
回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯；扩大当前候选解的规模，以继续试探的过程称为向前试探。
|
|
|
|
应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。
|
|
|
|
确定了解空间的组织结构后，回溯法从开始节点（根节点）出发，以深度优先的方式搜索整个解空间。这个开始节点就称为一个活节点，同时也称为当前的扩展节点。在当前的扩展节点处，搜索向纵深方向移至一个新节点。这个新节点就成为一个新的活节点，并成为当前扩展节点。如果在当前扩展节点处不能再向纵深方向移动，则当前的扩展节点就成为死节点。换句话说，这个节点不再是一个活节点。此时，应往回移动（回溯）至最近的一个活节点处，并使这个活节点成为当前的扩展节点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活节点时为止。
|
|
|
