笔记:coding:算法笔记
图解算法
第二章
NP完全问题的识别方法
元素较少时算法的运行速度非常快,但随着元素数量的增加,速度会变得非常慢。
涉及“所有组合”的问题通常是NP完全问题。
不能将问题分成小问题,必须考虑各种可能的情况。这可能是NP完全问题。
如果问题涉及序列(如旅行商问题中的城市序列)且难以解决,它可能就是NP完全问题。
如果问题涉及集合(如广播台集合)且难以解决,它可能就是NP完全问题。
如果问题可转换为集合覆盖问题或旅行商问题,那它肯定是NP完全问题。
动态规划
典型案例:背包问题
动态规划可帮助你在给定约束条件下找到最优解。在背包问题中,你必须在背包容量给定的情况下,获得最大价值。
在问题可分解为彼此独立且离散的子问题时,就可使用动态规划来解决。
每种动态规划解决方案都涉及网格。
单元格中的值通常就是你要优化的值。在前面的背包问题中,单元格的值为商品的价值。
每个单元格都是一个子问题,因此你应考虑如何将问题分成子问题,这有助于你找出网格的坐标轴。
笔记/coding/算法笔记.txt · 最后更改: 2019/01/28 16:36 由 winkidney