第五章：回溯法

1，什么是回溯法？

答： 回溯法：是一个既带有系统性又带有跳跃性的搜索算法。这在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

空间树构造:

1).子集树:当解向量为不定长n元组时, 树中从根至每一结点的路径集合构成解空间.树的每个结点称为一个解状态,有儿子的结点称为可扩展结点,叶结点称为终止结点, 若结点v对应解状态(x1, x2,… xi),则其儿子对应扩展的解状态(x1, x2,…xi, xi+1 ).满足所有约束条件的解状态结点称为回答结点.

2).排序树:当解向量为定长n元组时, 树中从根至叶结点的路径的集合构成解空间.树的每个叶结点称为一个解状态.

2，请简要描述回溯法的实现过程。用回溯法求解0/1背包问题、TSP问题、N皇后问题和连续邮资问题时，其各自的解空间树各是什么形式？

答：实现过程：确定解空间的组织结构，然后从开始结点（根结点）出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。

在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为新的活结点，并成为扩展结点。否则如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）到最近的活结点处，并使该结点成为当前的扩展结点。

回溯法按上述方式递归地在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。

0/1背包：n+1层的子集树  TSP问题：(n-1)!个叶节点的排列树

N皇后问题：完全n叉树    连续邮资问题：n层树，其中结点的度随着本结点取值范围而变化的树？？

 

3、影响回溯法效率的主要因素有哪些？如何有效地估算回溯法在求解具体实例时产生的中间节点数量？

答：影响回溯法效率的主要因素

1）产生x[k]的时间

2）满足显约束的x[k]值的个数

3）计算约束函数constrain的时间

4）计算限界函数bound的时间

5）满足约束函数和限界函数约束的所有x[k]的个数

采用概率方法可以有效地估算回溯法在求解具体实例时产生的中间节点数量：

（即在解空间树上产生一条随机路径，然后沿该路径估算解空间中满足约束条件的节点数m，由于使用静态约束函数，在某些情况下产生的估计较为保守。因此还可以多选取几条不同的路径，分别计算m，然后平均，这样的估算结果会更准确些。）

 例题：

1，旅行售货员问题

某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线。目标是使总的路程最短。

 

 

2，

 

3，

 

4，

 

 

本文转自 梦朝思夕 51CTO博客，原文链接:http://blog.51cto.com/qiangmzsx/802718