回溯(二）

回溯法

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

回溯法的解空间

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

回溯法的基本思想

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

剪枝函数

在用回溯法搜索解空间树时，通常采用两种策略来避免无效搜索，提高回溯法的搜索效率。这两类方法统称为剪枝函数。

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

回溯法算法框架

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

   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)的计算时间。

      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]);
     }
  }

注：所以剪枝函数需要好好想想，以到达优化。当解题时，可以先将解空间都描绘出来，再慢慢确定剪枝函数

回溯(二）

原文：https://www.cnblogs.com/code-fun/p/12885521.html