回溯法总结

1.影响回溯算法的效率的因素：
（1）产生x[k]的时间
（2）满足显约束的x[k]值的个数（剪枝的多少）
（3）计算显约束函数constraint的时间
（4）计算上界函数bound的时间
（5）满足约束函数和上界函数的所有x[k]的个数

2.最坏情况时间复杂度：
O(p(n) n! ) 或O(p(n) 2^n ) 或O(p(n) n^n )

3.重排原理：
x[i]的顺序通常随意，有时最小的排前比较好。

4.概率方法
蒙特卡罗方法估算结点数目

该方法的基本思想是:在解空间树上产生一条随机的路径，沿此路径估算满足约束条件的结点总数m
■设x是所产生的随机路径 上的一个结点，且位于解空间树的第i层上;
■对于x的所有儿子结点用约束函数检测出满足条件的结点数目mi;
■路径上下一个结点是从x的这m个孩子中随机选取的；这条路径一直延伸到一个叶结点或没有满足条件的子结点为止;
■通过这些 mi 的值，就可以估算出解空间树中满足约束条件的结点总数m。

5.回溯法小结

• 回溯法要求问题P的状态能表达为n元组(x1, … xn),要求xi∈si, i=1,2…n,si是一个有穷集， 对于给定关于n元组中的分量的一个约束集D，满足D的全部约束条件的所有n元组为问题P的解。
• 从k=1开始构造k元组，如果k元组满足约束，k=k+1,扩展搜索;
• 如果试探了x[k的所有值，仍不能满足约束，则k=k-1,回溯到上一层重新选择x[k-1的值。
• 这种扩展回溯的搜索方法可以表示为状态空间树上的带约束条件的深度优先的搜索。