回溯算法

2019/08/16 算法

回溯算法

适用场景

  • 针对一组数据,我们定义了限制值和期望值,希望从中选出几个数据,在满足限制值的情况下,期望值最大。

方式

  • 在一组可能的解中,搜索满足期望的解。回溯的处理思想,有点类似枚举搜索。我们枚举所有的解,找到满足期望的解。为了有规律地枚举所有可能的解,避免遗漏和重复,我们把问题求解的过程分为多个阶段。每个阶段,我们都会面对一个岔路口,我们先随意选一条路走,当发现这条路走不通的时候(不符合期望的解),就回退到上一个岔路口,另选一种走法继续走。

结果

大部分情况下,都是用来解决广义的搜索问题,也就是,从一组可能的解中,选择出一个满足要求的解。回溯算法非常适合用递归来实现,在实现的过程中,剪枝操作是提高回溯效率的。

经典应用

八皇后。

范例

  1. 0-1背包问题(回溯解法是简单但没有那么高效的方式,经典解法是动态规划)
  2. 正则表达式匹配
  3. 深度优先搜索
  4. 图的着色
  5. 旅行商问题
  6. 数独
  7. 全排列

Search

    Table of Contents