回溯(二)

回溯法

回溯法在包含问题的全部解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任何一个结点时,老是先判断该结点是否确定不包含问题的解,若是确定不包含,则跳过对以该结点为根的子树搜索。不然,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的全部解时,要回溯到根,且根结点的全部子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可结束。算法

回溯法的解空间

回溯法解问题时,首先应明肯定义问题的解空间。问题的解空间应至少包含问题的一个最优解。一般将问题的解空间组织成树或图的形式。例如,对于n=3的0-1背包问题,其解空间树可用下面的彻底二叉树表示。
框架

回溯法的基本思想

回溯法即以这种工做方式递归地在解空间中搜索,直至找到所要求的解或解空间中已无活结点时为止。函数

剪枝函数

在用回溯法搜索解空间树时,一般采用两种策略来避免无效搜索,提升回溯法的搜索效率。这两类方法统称为剪枝函数。优化

其一是用约束函数在扩展结点处剪去不知足约束条件的子树;
其二是用限界法剪去不能获得最优解的子树。3d

回溯法算法框架

回溯法是对解空间的深度优先搜索code

void Backtrack(int t)
    { if(t>n) Output(x);
       else 
       for(int i=f(n,t);i<=g(n,t);i++) // f(n,t)和g(n,t):在当前扩展结点处未  
      { x[t]=h(i);                             //搜索过的子树的起始编号和终止编号
         if (Constraint(t)&&Bound(t)) Backtrack(t+1);}
     }     // Constraint(t)和Bound(t):在当前扩展结点处的约束函数和限界函数

背包问题和旅行售货员问题的解空间树是两种典型的解空间树。

子集树算法框架

当所给的问题是从n个元素的集合S中找出知足某种性质的子集时,相应的解空间树为子集树。这类子集树常有2n个叶结点,其结点个数为2n+1-1。遍历子集树的任何算法均需Ω(2n)的计算时间。
blog

void Backtrack(int t)
        { if(t>n) Output(x);
           else  for(int i=0;i<=1;i++)
                   { x[t]=i;
                     if(Constraint(t)&&Bound(t)) Backtrack(t+1);}
        }

排列树算法框架

当所给问题是肯定n个元素的知足某种性质的排列时,相应的解空间树为排列树。排列树一般有n!各叶结点。所以遍历排列树所需的计算时间须要Ω(n!) 的计算时间。
递归

void Backtrack(int t)
 { if(t>n) Output(x);
   else
     for(int i=t;i<=n;i++)
     { Swap(x[t],x[i]);
        if(Constraint(t)&&Bound(t)) 
             Backtrack(t+1);
        Swap(x[t],x[i]);
     }
  }

注:因此剪枝函数须要好好想一想,以到达优化。当解题时,能够先将解空间都描绘出来,再慢慢肯定剪枝函数class

相关文章
相关标签/搜索