详细的描述

回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。
回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。
常用剪枝函数包括两类：
1.约束函数，剪去不满足约束条件的路径(在扩展结点处剪去不满足约束的子树)
2.限界函数，剪去不能得到最优解的路径(剪去得不到最优解的子树,处死那些实际上不可能产生所需解的活结点，以减少问题的计算量)
问题的关键在于如何定义问题的解空间，转化成树(即解空间树)。解空间树分为两种：子集树和排列树。两种在算法结构和思路上大体相同。

回溯法的基本思想

(1)针对所给问题，定义问题的解空间；
(2)确定易于搜索的解空间结构；
(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯法应用

当问题是要求满足某种性质（约束条件）的所有解或最优解时，往往使用回溯法。
基本思想类同于：

  • 图的深度优先搜索

  • 二叉树的后序遍历

    问题的解空间

  • 问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式

  • 显约束：对分量xi的取值限定。
  • 隐约束：为满足问题的解而对不同分量之间施加的约束。
  • 解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。

    生成问题状态的基本方法

    深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）
    广度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点
    回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法

    子集数与排列树

    1、子集数

    所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间成为子集树。如0-1背包问题，从所给重量、价值不同的物品中挑选几个物品放入背包，使得在满足背包不超重的情况下，背包内物品价值最大。它的解空间就是一个典型的子集树。
    这类子集树由2n个节点，遍历子集树需O(2n)计算时间
    1. void backtrack (int t)
    2. {
    3. if (t>n)
    4.     output(x);
    5. else
    6.     for (int i=0;i<=n;i++) {
    7.         x[t]=i;
    8.         if (constraint(t)&&bound(t))
    9.             backtrack(t+1);
    10.     }
    11. }

    2、排列数

    所给的问题是确定n个元素满足某种性质的排列时，相应的解空间就是排列树。如旅行售货员问题，一个售货员把几个城市旅行一遍，要求走的路程最小。它的解就是几个城市的排列，解空间就是排列树。
    排列树有n!个节点，遍历排列树需要O(n!)计算时间 
    1. void backtrack (int t)  
    2. {  
    3. if (t>n)
    4.     output(x);  
    5.   else  
    6.     for (int i=t;i<=n;i++) {  
    7.       swap(x[t], x[i]);  
    8.       if (constraint(t)&&bound(t))
    9.           backtrack(t+1);  
    10.       swap(x[t], x[i]);  
    11.     }  
    12. }
    Constraint(t)和Bound(t)表示当前扩展节点处的约束函数和限界函数。

    经典问题

    回溯法的算法框架按照问题的解空间一般分为子集树算法框架与排列树算法框架。
    （1）装载问题—————————>子集树
    （2）0-1背包问题———————>子集树 O(n2**n**)
    （3）旅行售货员问题—————>排列树
    （4）八皇后问题———————->排列树、n叉树
    （5）批处理作业调度问题——->排列树
    （6）图的m着色问题
    （7）迷宫问题

    考点：

    1、回溯法是指具有限界函数的深度优先生成法。
    2、回溯算法的基本思想是：在问题的状态空间树上作带剪枝的深度优先（DFS） 搜索
    3、 回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间。
    4、采用回溯法求解的问题，其解如何表示？有什么规定？
    问题的解可以表示为 n 元组：（x1,x2,……xn），xi∈Si, Si 为有穷集合，xi∈Si, (x1,x2,……xn)具备完备性，即(x1,x2,……xn)是合理的，则（x1,x2,……xi）(i5、回溯法的搜索特点是什么？
    在解空间树上跳跃式地深度优先搜索，即用判定函数考察 x[k]的取值，如果 x[k] 是合理的就搜索 x[k]为根节点的子树，如果 x[k]取完了所有的值，便回溯到 x[k-1]。
    6、n 皇后问题回溯算法的判别函数 place 的基本流程是什么？
    将第 K 行的皇后分别与前 k-1 行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回 true。
    7、回溯法的解（x1,x2,……xn）的隐约束一般指什么？
    回溯法的解（x1,x2,……xn）的隐约束一般指个元素之间应满足的某种关系。
    8、用回溯法求解哈密顿环，如何定义判定函数？
    当前选择的节点 X[k]是从未到过的节点,即 X[k]≠Xi，且 C(X[k-1], X[k])≠∞，如果 k=-1，则 C(X[k], X[1]) ≠∞。
    9、剪枝函数是回溯法中为避免无效搜索采取的策略。
    10、在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是:分支限界法
    11、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是0/1背包问题，只使用约束条件进行裁剪的是N皇后问题。
    12、回溯法是一种既带有系统性又带有跳跃性的搜索算法。
    13、以深度优先方式系统搜索问题解的算法称为回溯法
    14、回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数
    15、回溯法中常见的两类典型的解空间树是子集树和排列树。
    当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O(2**n**)计算时间。
    当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。
    16、请画出用回溯法解4皇后问题的解空间树和搜索空间树：
    解空间树：image.png
    用回溯法的搜索空间树：image.png

    回溯法的效率

    (1)产生x[k]的时间；
    (2)满足显约束的x[k]值的个数；
    (3)计算约束函数constraint的时间；
    (4)计算上界函数bound的时间；
    (5)满足约束函数和上界函数约束的所有x[k]的个数。
    好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折中。
    1、回溯法的效率不依赖于下列哪些因素（D）
    A.满足显约束的值的个数 B. 计算约束函数的时间
    C. 计算限界函数的时间 D. 确定解空间的时间
    2、回溯法的效率不依赖于以下哪一个因素？（C ）
    A.产生 x[k]的时间；
    B.满足显约束的 x[k]值的个数；
    C.问题的解空间的形式；
    D.计算上界函数 bound 的时间；
    E.满足约束函数和上界函数约束的所有 x[k]的个数。
    F. 计算约束函数 constraint 的时间；

14. 回溯法
回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。