贪心算法

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索

此词条暂由彩云小译翻译,翻译字数共1208,Tanpopo正在进行审校,带来阅读不便,请见谅。

文件:Greedy algorithm 36 cents.svg
利用贪心算法确定在找零时要提供的最小硬币数量。图中大多数人会采用的步骤,通过模拟贪心算法来只用面值为1、5、10、20 美分的硬币来表示 36 美分。价值最高且金额小于所欠的剩余零钱的硬币,是局部最优的。(一般来说,找零问题需要动态规划来找到最优解;然而,大多数货币系统,包括欧元系统和美元系统,都是贪心策略可以找到最优解的特殊情况。)

贪心算法是一种在每个阶段中都进行局部最优选择来进行问题求解的启发式算法。在许多问题中,贪心策略通常不会产生最优解,但贪心启发式算法可以产生局部最优解,即在合理的时间内得到全局最优解的近似。

例如,旅行商问题(计算复杂度很高)的贪心策略是以下启发式算法: “旅程的每一步都去最近的没去过的城市。”这种启发式方法并不打算找到最优解,但是它在合理的步骤数后终止,而通常为这种复杂问题找到最优解所需要的步骤数通常多到不合理。在最优化中,贪心算法可最优求解具有拟阵性质的组合问题,并给出具有子模结构的优化问题的常数因子近似。

算法细节

一般来说,贪心算法有五个组成部分:

  1. 候选集,用于从中创建解
  2. 选择函数,用于选择要添加到解中的最佳候选
  3. 可行性函数,用于确定一个候选是否有助于解决问题
  4. 目标函数,用于为解或部分解赋值
  5. 解函数,当找到一个完整的解时,它会指示出来

贪心算法对一些数学问题上生成的解较好,但在另一些上的解不好。大多数可以使用贪心算法问题都有如下两个性质:

贪心选择性质

贪心选择性质指,可以首先做出目前最优选择,然后再解决随后出现的子问题。贪心算法所做的选择可能取决于过去所做的所有选择,但不考虑未来的选择,也不会考虑子问题的所有解。它通过迭代来依次做出贪心选择,将每个给定的问题缩小为一个更小的问题。换句话说,贪心算法不会重新考虑已做出的选择,这是贪心算法与动态规划的主要区别。动态规划是穷举式的,并且保证能够找到解。在每个阶段之后,动态规划基于之前的所有决策做出下一步决策,并可能重新考虑之前求解的算法路径。

最优子结构

“如果问题的最优解包含子问题的最优解,则问题具有最优子结构。”

失效情况

页面模板:Multiple image/styles.css没有内容。

贪心算法可能无法获得最优解的例子。
从 a 开始,一个贪心算法试图通过跟随最大斜率来寻找最大值,会在“ m”处找到局部最大值,不会注意到“ m”处的全局最大值。
为了达到最大和的目标,在每一步,贪心算法将选择看起来是最优的即时选择,所以在第二步它将选择12而不是3,并且不会达到包含99的最优解。

对于许多其他问题,贪心算法不能产生最优解,甚至可能产生唯一的最坏可能解。比如上面提到的旅行商问题,对于任意给定的城市数量,都存在一个城市之间的距离分配,使得最近邻启发式算法产生唯一的最坏可能的旅行方案。其他可能使贪心算法失效的例子,请参阅地平线效应

分类

模板:More citations needed section

贪心算法可以被描述为“目光短浅” ,也可以被描述为“不可恢复”。它们只适用于具有“最优子结构”的问题。尽管如此,对于许多简单的问题,最适合的算法依然是贪心算法。但是,值得注意的是,贪心算法可以用于在搜索或分支定界算法中对选项进行优先级排序。贪心算法有以下几种变体:

  • 纯贪心算法
  • 正交贪心算法
  • 松弛贪心算法

理论

贪心算法在组合优化理论计算机科学领域有着悠久的研究历史。众所周知,贪心启发法会在许多问题上产生次优的结果,因此自然会提出以下问题:

  • 怎样的问题可以保证贪心算法能产生最优解?
  • 怎样的问题可以保证贪心算法能产生近似最优解?
  • 怎样的问题可以保证贪心算法无法产生最优解?

大量的文献都在回答上述问题,例如拟阵等回答一般类问题,以及集合覆盖等回答具体问题。

拟阵

拟阵是一种将线性无关的概念从向量空间推广到任意集合的数学结构。如果一个最优化问题具有拟阵的结构,那么这个问题可由贪心算法得到最优解。

子模函数

定义在一个集合[math]\displaystyle{ \Omega }[/math]的子集上的一个函数[math]\displaystyle{ f }[/math],如果对于每个 [math]\displaystyle{ S, T \subseteq \Omega }[/math],有[math]\displaystyle{ f(S)+f(T)\geq f(S\cup T)+f(S\cap T) }[/math],则称这个函数为子模函数。

假设我们想要找到一个使[math]\displaystyle{ f }[/math]最大化的集合[math]\displaystyle{ S }[/math]。贪心算法通过在每一步中逐步添加元素,使得每一步的[math]\displaystyle{ f }[/math]的增量最大,从而建立一个集合[math]\displaystyle{ S }[/math],产生一个至少[math]\displaystyle{ (1 - 1/e) \max_{X \subseteq \Omega} f(X) }[/math]的集合作为输出。也就是说,在常数因子[math]\displaystyle{ (1 - 1/e) \approx 0.63 }[/math]下,贪心算法的表现和最优解一样好。

可以证明,当对输出施加额外的约束(如基数约束)时,类似的保证依然成立,尽管贪心算法通常需要一些细微的变化。详见[3]。

其他有保证的问题

对其他问题,贪心算法提供了强保证,但不是最优解。这些问题包括:

其中许多问题都有匹配的下限;即,贪心算法在最坏情况下的性能并不优于保证。

应用

模板:Expand section

贪心算法通常(但并不总是)无法找到全局最优解,这是因为这些算法通常不会遍历所有数据。贪心算法可能过早地做出某些选择,妨碍了之后找到全局最优解。例如,针对所有已知的图着色问题和所有其他NP 完全问题,贪心着色算法都不能保证找到最优解。尽管如此,贪心算法还是很有用的,因为它们很快就能想出来,而且常常能给出最佳的近似值。

如果一个贪心算法被证明可以为给定的问题类产生全局最优解,它通常成为选择的方法,因为它比动态规划等其他优化方法更快。这种贪心算法的例子有 Kruskal 算法Prim 算法用于寻找最小生成树,以及寻找最优 Huffman 树的算法。

贪心算法也出现在网络路由中。使用贪心路由,消息被转发到邻近的节点,这是“最接近”的目标。一个节点的位置(因此是“贴近度”)的概念可以由它的物理位置来决定,就像临时网络使用的地理路由一样。位置也可能是一个完全人为的构造,就像小世界路由分散式哈希表路由。

举例

  • 活动选择问题是这类问题的特征,其目标是选择彼此不冲突的最大活动数。
  • 麦金塔电脑游戏Crystal Quest中,目标是收集水晶,其方式类似于旅行商问题。游戏有一个演示模式,游戏使用贪心算法去每一个水晶。游戏AI(人工智能)不考虑障碍物,因此演示模式通常会很快结束。
  • 匹配追求是应用于信号近似的贪心算法的一个例子。
  • 贪心算法为马尔法蒂问题找到了最优解,即在给定的三角形内找到三个不相交的圆,使圆的总面积最大化;据推测,同样的贪心算法对于任何数量的圆圈都是最优的。
  • 贪心算法用于在霍夫曼编码期间构造霍夫曼树,以找到最优解。
  • 决策树学习中,通常使用贪心算法,但是不能保证它们能找到最优解。
    • 一种流行的此类算法是用于决策树构造的ID3算法
  • Dijkstra算法和相关的A*搜索算法是用于图搜索最短路径查找的可验证的最优贪心算法。
  • Kruskal算法Prim算法是用于构造给定连通图的最小生成树的贪心算法。他们总能找到一个最佳解决方案,这在一般情况下可能不是唯一的。

参见

模板:Portal

参考

  • Gutin, Gregory; Yeo, Anders; Zverovich, Alexey (2002). "Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP". Discrete Applied Mathematics. 117 (1–3): 81–86. doi:10.1016/S0166-218X(01)00195-0.
  • Bang-Jensen, Jørgen; Gutin, Gregory; Yeo, Anders (2004). "When the greedy algorithm fails". Discrete Optimization. 1 (2): 121–127. doi:10.1016/j.disopt.2004.03.007.
  • Bendall, Gareth; Margot, François (2006). "Greedy-type resistance of combinatorial problems". Discrete Optimization. 3 (4): 288–298. doi:10.1016/j.disopt.2006.03.001.


外部链接

模板:Commons category


模板:Data structures and algorithms

Category:Optimization algorithms and methods

类别: 优化算法和方法

Category:Combinatorial algorithms

类别: 组合算法

Category:Matroid theory

范畴: 拟阵理论

Category:Exchange algorithms

类别: Exchange 算法


This page was moved from wikipedia:en:Greedy algorithm. Its edit history can be viewed at 贪心算法/edithistory