回溯法（复习笔记一）

三、基本步骤

回溯法的基本步骤：

(1)针对所给问题，定义问题的解空间；

(2)确定易于搜索的解空间结构；

(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

常用剪枝函数：

用约束函数在扩展结点处剪去不满足约束的子树；

用目标函数剪去得不到最优解的子树。(优化问题)

剪枝的正确性：

●    对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，…，xi）满足D中仅涉及到x1，x2，…，xi的所有约束意味着j（j

●   换句话说，只要存在0≤j≤n-1，使得（x1,x2,…, xj）违反D中仅涉及到x1，x2，…，xj的约束之一，则以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）一定也违反D中仅涉及到x1，x2，…，xi的一个约束，n≥i>j。

●    因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1，x2，…，xj）违反D中仅涉及x1，x2，…，xj的一个约束，就可以肯定，以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）都不会是问题P的解，因而就不必去搜索它们、检测它们。

●   回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。

※重点提醒

•   回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。
•   回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。  
•   回溯法在用来求问题的最优解时，要回溯到根，且根结点的所有子树都已被搜索遍，保留问题的目标函数值最优的解。

  回溯算法中用到的几个概念：            

1.  如果已经搜索到的结点全部满足问题的约束条件，但搜索还没有到达空间树的叶子节点，则称为部分解。
2.  如果从根到当前节点的路径对应于问题的一个合法解，过程就终止(除非问题没有解)。      
3.  如果这条路径的长度小于n，并且相应的解是部分的，那么就生成现节点的一个子节点，并将它标记为现节点(活节点)。        
4. 如果对应的路径不是部分的，那么现节点标识为死节点。        
5. 回溯算法有递归形式和非递归形式两种。

四、深度剖析

问题描述：        

找出从自然数1、2、……、n中任取r个数的所有组合。

问题的状态空间为  E={（x1，x2，...，xr）∣xi∈S ，i=1，2，...，r }        

其中： S={1，2，3，...，n}       约束集为：   x1

INPUT: n个数分别为{1，2，…n}，r。
OUTPUT: n个数的所有r组合。
    1.    for  k =1 to r
    2.         c[k] =0
    3.    end for
    4.    k =1
    5.    while k≥1
    6.          while c[k]≤n-1
    7.                 c[k] =c[k]+1
    8.                 if c为合法的  then得到一个r组合，输出c数组
    9.                 else if c是部分解 then k =k+1
   10.         end while
   11.         c[k] =0
   12.         k =k-1
   13.  end while 

INPUT: n个数分别为{1，2，…n}，r。
OUTPUT: n个数的所有r组合。
    1.    for  k =1 to r
    2.         c[k] =0
    3.    end for
    4.    k =1
    5.    while k≥1
    6.          while c[k]≤n-1
    7.                 c[k] =c[k]+1
    8.                 if c为合法的  then得到一个r组合，输出c数组
    9.                 else if c是部分解 then k =k+1
   10.         end while
   11.         c[k] =0
   12.         k =k-1
   13.  end while