贪心算法

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

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

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

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

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

算法细节

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

  1. 候选集,用于从中创建解
  2. 选择函数,用于选择要添加到解中的最佳候选
  3. 可行性函数,用于确定一个候选是否有助于解决问题
  4. 目标函数,用于为解或部分解赋值
  5. 解函数,当找到一个完整的解时,它会指示出来
  1. A candidate set, from which a solution is created
  2. A selection function, which chooses the best candidate to be added to the solution
  3. A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
  4. An objective function, which assigns a value to a solution, or a partial solution, and
  5. A solution function, which will indicate when we have discovered a complete solution


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

贪心选择性质

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

最优子结构

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

失效情况

页面模板: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]。

其他有保证的问题

Other problems for which the greedy algorithm gives a strong guarantee, but not an optimal solution, include

Other problems for which the greedy algorithm gives a strong guarantee, but not an optimal solution, include

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

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


应用

模板:Expand section

Greedy algorithms mostly (but not always) fail to find the globally optimal solution because they usually do not operate exhaustively on all the data. They can make commitments to certain choices too early which prevent them from finding the best overall solution later. For example, all known greedy coloring algorithms for the graph coloring problem and all other NP-complete problems do not consistently find optimum solutions. Nevertheless, they are useful because they are quick to think up and often give good approximations to the optimum.

Greedy algorithms mostly (but not always) fail to find the globally optimal solution because they usually do not operate exhaustively on all the data. They can make commitments to certain choices too early which prevent them from finding the best overall solution later. For example, all known greedy coloring algorithms for the graph coloring problem and all other NP-complete problems do not consistently find optimum solutions. Nevertheless, they are useful because they are quick to think up and often give good approximations to the optimum.

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


If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice because it is faster than other optimization methods like dynamic programming. Examples of such greedy algorithms are Kruskal's algorithm and Prim's algorithm for finding minimum spanning trees, and the algorithm for finding optimum Huffman trees.

If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice because it is faster than other optimization methods like dynamic programming. Examples of such greedy algorithms are Kruskal's algorithm and Prim's algorithm for finding minimum spanning trees, and the algorithm for finding optimum Huffman trees.

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


Greedy algorithms appear in network routing as well. Using greedy routing, a message is forwarded to the neighboring node which is "closest" to the destination. The notion of a node's location (and hence "closeness") may be determined by its physical location, as in geographic routing used by ad hoc networks. Location may also be an entirely artificial construct as in small world routing and distributed hash table.

Greedy algorithms appear in network routing as well. Using greedy routing, a message is forwarded to the neighboring node which is "closest" to the destination. The notion of a node's location (and hence "closeness") may be determined by its physical location, as in geographic routing used by ad hoc networks. Location may also be an entirely artificial construct as in small world routing and distributed hash table.

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


Examples

  • The activity selection problem is characteristic to this class of problems, where the goal is to pick the maximum number of activities that do not clash with each other.
  • The matching pursuit is an example of greedy algorithm applied on signal approximation.
  • A greedy algorithm finds the optimal solution to Malfatti's problem of finding three disjoint circles within a given triangle that maximize the total area of the circles; it is conjectured that the same greedy algorithm is optimal for any number of circles.
  • A greedy algorithm is used to construct a Huffman tree during Huffman coding where it finds an optimal solution.
  • In decision tree learning, greedy algorithms are commonly used, however they are not guaranteed to find the optimal solution.
    • One popular such algorithm is the ID3 algorithm for decision tree construction.
    • A* search is conditionally optimal, requiring an "admissible heuristic" that will not overestimate path costs.


See also

模板:Portal


Notes


References

  • 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.


External links

模板:Commons category


模板:Optimization algorithms模板: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