算法概念

为什么要叫算法概念呢? 因为算法本身不重要重要的是解决那个问题用到的思想. 就和设计模式一样, 重要的是patten

回溯算法

定义

backtracking是暴力搜索法中的一种。相比于暴力搜索.

对于某些计算问题而言,回溯法是一种可以找出所有(或一部分)解的一般性算法,尤其适用于约束满足问题(在解决约束满足问题时,

递归到最后的返回条件是:

思想

试错 约束编程 回溯

回溯是说当不满足条件的时候回到刚才的 状态 .值得注意的是这个状态返回到之前的状态有两种做法,一种是自顶而下拷贝,这样子方法结束立马就丢掉了子方法的状态. 一种是维护一个全局变量.

一旦在过程中发现当前的部分解不满足约束条件,那么就不需要这个部分解后面的拓展出来的其他解(子集), 直接扔掉就好了. 这样大大优化了空间复杂度.

在最坏的情况下,回溯法会导致一次复杂度为指数时间的计算。

例子

八皇后问题, 暴力的解法是生成整个棋盘上所有可能的解法(N^N). 这个解法产生了太多无用的解, 比如第一行和第二行的皇后就冲突了, 就没必要在探索下面的可能性了.

这时候回溯法通过 约束 + 回溯 就解决了这个问题. 当部分解已经不满足的时候就向前看不需要探索其子集.

模板

void backtrack(level int, stats collector, ans collector, ...)
{
    if(已经得到正确解){
      ans = ans.append(answer.copy());
      return;
    }
    // 下面的意思是在level这一层, 遍历所有的可行解
    // 空间. 这个地方需要仔细
    for(i of solution space)
    {
      backtrack(i+1,n,other parameters);
    }
}