Skip to content

alogrithom

Jump to bottom
Xiaolin Zhang edited this page Nov 17, 2019 · 6 revisions

算法概念

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

回溯算法

定义

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

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

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

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

思想

试错 约束编程 回溯

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

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

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

例子

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

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

模板

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

    // note2: 下面的意思是在level这一层, 遍历所有的可行解空间
    for(i of solution space)
    {
      // note3: 剪枝
      if cutdown(){
        return 
      }
      // 根据情况选择stats和ans
      update(stats)
      backtrack(space[1:], stats, update(ans))
      recover(stats)
    }
}

note1: 何时记录

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

  • 路径上的都有可能是. 比如求Subsets, Combinations系列

  • 只有叶子节点有可能是目标值. 比如八皇后, 长度一致的子集.

note2: 如何搜索子空间

就是如何遍历的问题:

  1. 分解子问题为: 必须以当前元素开头的子集, for循环递归
  2. 分解子问题为: 要不要当前元素.

note3: 如何剪枝

  1. 通过发现pattern及时return这样就不用在子空间搜索

例子

  1. 常用patten 思想是一定要让nums里每一个元素都有机会出现在结果集里的第一个
*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]
}
  1. 通过是否包含当前节点来搜索.
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()
  1. 通过target
// 1. 先找状态
func traceback(stats []int, preSum int, candidates []int, target int, ans *[][]int) {
  // 2. 保存条件
	if preSum == target {
		*ans = append(*ans, append([]int(nil), stats...))
	}
	// 3. 在写退出条件
	if preSum >= target {
		return
	}

	for i := 0; i < len(candidates); i++ {
		cur := candidates[i]
    // 4. 看需不需要剪枝. 遇到相同数字要求去重的问题经常这么搞
    // 解释: 因为候选集会出现相同的元素比如 1,2,2,3,4. 2第一次出现的时候已经解决了[2]|[3,4], 第二次的[2]|[3,4]就不需要在解决一次
		if i > 0 && cur == candidates[i-1] {
			continue
		}
    // 剪枝
		if preSum+cur > target {
			return
		}
    
    // 5. 回溯
		stats = append(stats, cur)
		traceback(stats, preSum+cur, candidates[i+1:], target, ans)
		stats = stats[:len(stats)-1]
	}

动态规划

定义

There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead.[1] This is why merge sort and quick sort are not classified as dynamic programming problems.

最优子结构: ABCD是最优的那么, BCD也得是最优的

重叠子问题: 相同的问题重复多次

关系

  • 动态规划属于分治算法的一种.区别是要求有最优子结构和重叠子问题.

  • 动态规划思想和回溯算法的区别是, 回溯算法面对的是不同的子问题, 是在搜索所有可行解他没有最优子结构, 他关注怎么剪枝怎么少搜索一点东西. 而动态规划关注子问题是不是重复出现, 可不可以只算一次.

实现

  • 自定而下. 一定是要有memory的, 有一些语言自带对函数结构的cache.
  • 自底而上. 先解决小规模的子问题, 然后在去用这些子问题的解去解更大的问题

回到首页

Clone this wiki locally