本章导读

学习一个算法,可分为3个步骤:首先了解算法本身解决什么问题,然后学习它的解决策略,最后了解某些相似算法之间的联系。例如图算法中,

  • 广搜是一层一层往外遍历,寻找最短路径,其策略是采取队列的方法。
  • 最小生成树是最小代价连接所有点,其策略是贪心,比如Prim的策略是贪心+权重队列。
  • Dijkstra是寻找单源最短路径,其策略是贪心+非负权重队列。
  • Floyd是多结点对的最短路径,其策略是动态规划。

而贪心和动态规划是有联系的,贪心是“最优子结构+局部最优”,动态规划是“最优独立重叠子结构+全局最优”。一句话理解动态规划,则是枚举所有状态,然后剪枝,寻找最优状态,同时将每一次求解子问题的结果保存在一张“表格”中,以后再遇到重叠的子问题,从表格中保存的状态中查找(俗称记忆化搜索)。

 
Generated by mdtogh