首页 > 试题广场 >

以下算法中未用到贪心算法思想的是?

[单选题]
以下算法中未用到贪心算法思想的是?
  • 迪杰斯特拉(Dijkstra)
  • 库鲁斯卡尔(Kruskal)
  • 普里姆算法(Prim)
  • KMP
  1. 迪杰斯特拉(Dijkstra)贪心策略是每次选可达的点中距离源点最近的点进行扩展,即贪心选取最短距离的点
  2. 库鲁斯卡尔(Kruskal)贪心策略是每次选最短的边(刨除成环的边)来作为最小生成树,即贪心最短
  3. 普里姆算法(Prim)贪心策略是每次选可达的点中距离曾经扩展过的点中任意点的最短距离,类似Dij,只是不是找距离源点的最短距离
  4. KMP不是贪心是动态规划,动态规划的是当前状态失败之后上一次匹配的位置(求的是最长的与前缀子串匹配的左子串)

发表于 2019-10-14 14:16:53 回复(0)