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

分治特点

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

分支限界

  1. 与回溯相似,但是广度优先

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

上一篇:轻松上手SpringBoot+SpringSecurity+JWT实RESTfulAPI权限控制实战


下一篇:JavaWeb-03-Servlet-12-多个Servlet之间的数据共享-03HttpServletRequest接口