04-回溯算法的搜索

15.1.2　回溯算法的搜索

确定了解空间的组织结构后，回溯算法就从开始节点（即根节点）出发，以深度优先搜索的方式搜索整个解空间。该开始节点就成为一个活节点，同时也成为当前的扩展节点。从该扩展节点开始，搜索向纵深方向移至一个新节点。该新节点又成为新的活节点，并成为当前的扩展节点。若在当前节点的扩展节点处不能继续向纵深方向移动，则当前的扩展节点就成为死节点。此时，应往回移动（回溯）至最近的活节点处，并使这个活节点成为当前扩展节点。回溯算法就是以这种方式递归地在解空间中搜索，直到找到要求的解或解空间中无活节点为止。在回溯算法中，每次扩大当前部分解时，都面临一个可选的状态集合，新的解就在该集合中选择构造而成。回溯算法通常有两种实现方式——递归回溯的深度优先搜索和非递归迭代回溯的深度优先搜索。

用递归实现回溯的算法框架如下。

void Backtrack(int m)
{
    if(m>n)
        Output(x);
    else
    {
        for(i=下界;i<=上界;i++)
        {
             x[m]取一个可能的值;
             if(Constraint(m) && Bound(m))
                 Backtrack(m+1);
        }
     }
}

其中，m为递归深度，即当前扩展节点在解空间树中的深度；n用来控制递归的深度，即解空间树的高度。当m>n时，表示回溯算法已搜索到一个叶子节点，则输出可行解。

非递归迭代实现回溯的算法框架如下。

void Backtrack(int m)
{
    int m=1;
while(m>0)
    {
if(IsExist(m))//若当前节点存在子节点
         {
for(i=下界;i<=上界;i++)
            {
                if(Constraint(m) && Bound(m))
                {
                     if(Solution(m))//若找到问题的可行解
                        Output(m);//输出可行解
                     else//若不是问题的可行解
                     {
                        m++;//继续向纵深方向搜索
                     }
                 }
             }
     }
     else//若当前节点不存在子节点，则回溯
        m--;
}

其中，Solution(m)用于判断是否投到问题的一个可行解。若为真，则输出可行解；否则，则继续向纵深方向搜索。IsExist(m)用于判断当前节点是否存在子节点。若存在，则向前搜索；否则，则返回上一层，即回溯。

回溯算法与枚举算法有一定联系，它们都是基于试探的算法。枚举算法要将一个可行解的各个部分全部生成后，才检查是否满足条件；若不满足，则直接放弃该可行解，然后再尝试另一个可能的可行解，它并没有沿着一个可能的可行解的各个部分逐步回退，生成可行解。而对于回溯算法，一个可行解的各个部分是逐步生成的，当发现当前生成的某部分不满足约束条件时，就放弃该步所做的工作，退到上一步（回溯）进行新的尝试，而不是放弃整个可行解重新开始。