数据结构&算法 贪婪算法

  • 贪婪算法

    设计了一种算法来针对给定问题实现最佳解决方案。在贪婪算法方法中,决策是从给定的解决方案域中做出的。由于贪婪,选择了似乎提供最佳解决方案的最接近的解决方案。贪婪算法试图找到局部最优解,最终可能导致全局最优解。但是,通常,贪心算法不会提供全局优化的解决方案。
  • 计数硬币

    这个问题是通过选择尽可能少的硬币来计数到期望值,并且贪婪方法迫使算法选择最大可能的硬币。如果我们给我们提供了1、2、5和10分的硬币,并且要求我们计数18分,那么贪婪的过程将是-
    • 1 - 选择一个10分硬币,剩余数量为8
    • 2 - 然后选择一个5硬币,剩余数量为3
    • 3 − 然后选择一个2硬币,剩余计数为1
    • 4 - 最后,选择1个1分硬币解决了这个问题
    虽然,这似乎工作正常,但对于此计数,我们只需要选择4个硬币。但是,如果我们稍微改变问题,则相同的方法可能无法产生相同的最佳结果。对于货币系统,如果我们有1、7、10枚硬币,则计数18枚硬币绝对是最佳选择,但对于15枚硬币,则可能会使用比必要数量更多的硬币。例如,贪婪方法将使用10 +1 + 1 +1 +1 + 1,总共6个硬币。只需使用3个硬币(7 + 7 + 1)就可以解决相同的问题
    因此,我们可以得出这样的结论:贪婪的方法选择了一种立即优化的解决方案,并且在全局优化是一个主要问题时可能会失败。
    例子
    大多数联网算法都使用贪婪方法。这是其中一些的列表-
    • 旅行推销员问题
    • Prim最小生成树算法
    • Kruskal的最小生成树算法
    • Dijkstra的最小生成树算法
    • 图-地图着色
    • 图-顶点覆盖
    • 背包问题
    • 作业调度问题