alogrithom

算法概念

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

回溯算法

定义

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

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

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

• 找到一个可能存在的正确的答案
• 在尝试了所有可能的分步方法后宣告该问题没有答案

思想

试错 约束编程 回溯

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

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

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

例子

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

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

模板

// space 是潜在的解空间, 通常是slice, 或者一个array + index
// stats 是之前已经成立的子部 记录下来的状态
// ans 是全局的解记录
void backtrack(space []int, stats []int, ans []int, ...)
{
    // note1: 已经得到正确解
    if(condition){
      ans = ans.append(answer.copy())
    }
    if checkSolutionSpace(){
        return 
    }

    // note2: 下面的意思是在level这一层, 遍历所有的可行解
    // 空间. 这个地方需要仔细
    for(i of solution space)
    {
      // 根据情况选择stats和ans
      update(stats)
      backtrack(space[1:], stats, update(ans))
      recover(stats)
    }
}

note1: 何时记录

取决于需要什么样子的数据, 以及遍历路径是什么样子的.

• 路径上的都要, record 然后接着搜索子空间

• 只要叶子节点, 判断是叶子节点, 然后返回

note2: 如何搜索子空间

就是如何遍历的问题:

1. 按照全子集遍历, 路径是全子集
2. 按照特定的要求搜索子空间, 比如每次减少一个要处理的元素.

例子

1. 路径搜索 + 什么都要

*ans = append(*ans, oneAns)

for i := 0; i < size; i++ {
  prefix = append(prefix, nums[i])
  traceback(nums[i+1:], prefix, ans)
  prefix = prefix[:len(prefix)-1]
}

2. 条件搜索 + 只记录子节点

if layer == len(nums) {
	*ans = append(*ans, oneAns)
	return
}

// solve current layer problem 
updateStats()
backtrack(i+1, stats, n,other parameters);
recoverStats()

updateStats()
backtrack(i+1, stats, n,other parameters);
recoverStats()