用户工具

站点工具


笔记:coding:算法笔记

图解算法

第二章

  • 一种基本的排序算法 - 选择排序(挨个选取当前所有元素中最大或最小的元素插入新的排序队列里)
  • 递归的重要构成:基线条件(停止)和递归条件(继续)

NP完全问题的识别方法

  • 元素较少时算法的运行速度非常快,但随着元素数量的增加,速度会变得非常慢。
  • 涉及“所有组合”的问题通常是NP完全问题。
  • 不能将问题分成小问题,必须考虑各种可能的情况。这可能是NP完全问题。
  • 如果问题涉及序列(如旅行商问题中的城市序列)且难以解决,它可能就是NP完全问题。
  • 如果问题涉及集合(如广播台集合)且难以解决,它可能就是NP完全问题。
  • 如果问题可转换为集合覆盖问题或旅行商问题,那它肯定是NP完全问题。

动态规划

  • 典型案例:背包问题
  • 动态规划可帮助你在给定约束条件下找到最优解。在背包问题中,你必须在背包容量给定的情况下,获得最大价值。
  • 在问题可分解为彼此独立且离散的子问题时,就可使用动态规划来解决。
  • 每种动态规划解决方案都涉及网格。
  • 单元格中的值通常就是你要优化的值。在前面的背包问题中,单元格的值为商品的价值。
  • 每个单元格都是一个子问题,因此你应考虑如何将问题分成子问题,这有助于你找出网格的坐标轴。
笔记/coding/算法笔记.txt · 最后更改: 2019/01/28 16:36 由 winkidney