Java教程

分治、动态规划、贪心、回溯算法特点的自我总结

本文主要是介绍分治、动态规划、贪心、回溯算法特点的自我总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

分治特点

  1. 分解：
    1. 使用递归的方式将问题的范围逐渐缩小看作子问题
    2. 比如
      1. 一分为二：0~n/2,n/2+1~结尾
      2. 首尾相互靠近
  2. 求解：通常被看作最小子问题的求解（注意边界判断）
  3. 合并：子问题的返回值处理

动态规划特点

  1. 最优子结构
    1. 一个问题的最优解包含了其子问题的最优解：第n层子问题需要根据第n-1层子问题的解得出答案
  2. 子问题被重复求解（重叠的）：
    1. 解原问题的递归算法可反复解同样的子问题，而不是总在产生新问题（分治法会产生新问题）　　
    2. 需要使用表记录子问题的解，并在该表中得出最优解（全局最优解）

贪心

  1. 最优子结构（与动态规划一致）
  2. 局部最优的选择策略（与动态规划的主要区别）
    1. 最优解可能不止一个
    2. 重点在于选择，根据策略做最优的选择
    3. 具有度量标准
    4. 通常会先排好序

回溯

  1. 树
    1. 深度优先
    2. 解空间：一般是二叉树画路径，取叶子节点，数量为2n
    3. 满足条件的所有解在解空间中获取
  2. 活/死节点
    1. 满足条件的节点是活结点，不满足的则是死结点
    2. 当碰到死结点时，需要从该节点返回到上一个节点，选择另一个节点，若依旧是死的，则返回到上一个节点的父节点
  3. 限界函数（剪枝）
    1. 尽可能多和尽可能早地“杀掉”不可能产生最优解的活结点
  4. 多重循环
    1. 常涉及下标的++（去往子节点）、--（回到父节点）

分支限界

  1. 与回溯相似，但是广度优先
这篇关于分治、动态规划、贪心、回溯算法特点的自我总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航