例如,旅行推销员问题(计算复杂度很高)的贪婪策略的启发式方法如下:“在旅程的每一步,访问最近的未游览城市。”这种启发式方法并不打算找到最佳的解决方案,但它以合理数量的步骤结束;为如此复杂的问题找到最佳解决方案通常需要进行多次不合理的步骤。在数学优化中,贪婪算法优化求解具有拟阵性质的组合问题,并对具有子模型结构的优化问题给出了常数因子逼近。
一般来说,贪婪算法有五个组成部分:
贪婪算法对一些数学问题能够产生很好的解决方案,但对另一些其他数学问题却没有。他们解决的大多数问题都有两个属性:
举例说明贪婪算法可能无法达到最优解
贪婪算法可以被描述为“短视的”,也可以被描述为“不可恢复的”。它们仅适用于具有“最佳子结构”的问题。尽管如此,对于许多简单的问题,最适合的算法是贪婪算法。但是更需要注意的是,贪婪算法可以用作选择算法,在搜索中对选项进行优先排序,或者分支定界算法。贪婪算法有一些变化:
有大量的文献回答了一般类问题,如拟阵,以及特殊问题,如集合覆盖。
贪婪算法提供了强有力的保证但不是最优解的其他问题包括
许多这些问题都有匹配的下限;即,在最坏的情况下,贪婪算法没有比保证的性能好。
贪婪算法大多(但不总是)无法找到全局最优解,因为它们通常不会对所有数据都进行彻底的操作。他们可能过早地做出某些选择,这妨碍了他们以后找到最优解。例如,所有已知的图着色问题和所有其他NP完全问题的贪婪着色算法都不能始终找到最优解。然而,它们是有用的,因为它们很快就能想出,并且经常给出很好的近似最优解。
如果贪婪算法能够被证明为给定问题类产生全局最优,它通常会成为选择的方法,因为它比其他优化方法(如动态规划)更快。这种贪婪算法的例子是用于寻找最小生成树的克鲁斯卡尔(Kruakal)算法和普林(Prim)算法,以及用于寻找最优霍夫曼树(Huffmantrees)的算法。
贪婪算法也出现在网络路由中。使用贪婪路由,消息被转发到离目的地“最近”的相邻节点。节点位置的概念(以及因此的“接近度”)可以由它的物理位置来确定,如在自组织网络使用的地理路由中。在区域路由和分布式哈希表中,位置也可以是完全人工构建的。