| 第15行： |
第15行： |
| | #目标函数，用于为解或部分解赋值 | | #目标函数，用于为解或部分解赋值 |
| | #解函数，当找到一个完整的解时，它会指示出来 | | #解函数，当找到一个完整的解时，它会指示出来 |
| − |
| |
| − | #A candidate set, from which a solution is created
| |
| − | #A selection function, which chooses the best candidate to be added to the solution
| |
| − | #A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
| |
| − | #An objective function, which assigns a value to a solution, or a partial solution, and
| |
| − | #A solution function, which will indicate when we have discovered a complete solution
| |
| − |
| |
| − |
| |
| | 贪心算法对一些数学问题上生成的解较好，但在另一些上的解不好。大多数可以使用贪心算法问题都有如下两个性质: | | 贪心算法对一些数学问题上生成的解较好，但在另一些上的解不好。大多数可以使用贪心算法问题都有如下两个性质: |
| | | | |
| 第47行： |
第39行： |
| | | | |
| | 对于许多其他问题，贪心算法不能产生最优解，甚至可能产生唯一的最坏可能解。比如上面提到的旅行商问题，对于任意给定的城市数量，都存在一个城市之间的距离分配，使得最近邻启发式算法产生唯一的最坏可能的旅行方案。其他可能使贪心算法失效的例子，请参阅[[地平线效应]]。 | | 对于许多其他问题，贪心算法不能产生最优解，甚至可能产生唯一的最坏可能解。比如上面提到的旅行商问题，对于任意给定的城市数量，都存在一个城市之间的距离分配，使得最近邻启发式算法产生唯一的最坏可能的旅行方案。其他可能使贪心算法失效的例子，请参阅[[地平线效应]]。 |
| − |
| |
| − |
| |
| | == 分类== | | == 分类== |
| | | | |
| 第68行： |
第58行： |
| | ===拟阵=== | | ===拟阵=== |
| | | | |
| − | {{Main|Matroid}} | + | {{Main|拟阵}} |
| | | | |
| | 拟阵是一种将线性无关的概念从向量空间推广到任意集合的数学结构。如果一个最优化问题具有拟阵的结构，那么这个问题可由贪心算法得到最优解。 | | 拟阵是一种将线性无关的概念从向量空间推广到任意集合的数学结构。如果一个最优化问题具有拟阵的结构，那么这个问题可由贪心算法得到最优解。 |
| 第81行： |
第71行： |
| | 可以证明，当对输出施加额外的约束（如基数约束）时，类似的保证依然成立，尽管贪心算法通常需要一些细微的变化。详见[3]。 | | 可以证明，当对输出施加额外的约束（如基数约束）时，类似的保证依然成立，尽管贪心算法通常需要一些细微的变化。详见[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
| |
| | | | |
| | 对其他问题，贪心算法提供了强保证，但不是最优解。这些问题包括： | | 对其他问题，贪心算法提供了强保证，但不是最优解。这些问题包括： |
| 第95行： |
第81行： |
| | *[[独立集]] | | *[[独立集]] |
| | 其中许多问题都有匹配的下限；即，贪心算法在最坏情况下的性能并不优于保证。 | | 其中许多问题都有匹配的下限；即，贪心算法在最坏情况下的性能并不优于保证。 |
| − |
| |
| − |
| |
| | ==应用 == | | ==应用 == |
| | | | |
| | {{Expand section|date=June 2018}} | | {{Expand section|date=June 2018}} |
| | | | |
| − | 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完全|NP 完全]]问题，[[贪心着色]]算法都不能保证找到最优解。尽管如此，贪心算法还是很有用的，因为它们很快就能想出来，而且常常能给出最佳的近似值。 |
| − | | |
| − | 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完全|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 tree]]s, and the algorithm for finding optimum [[Huffman tree]]s.
| |
| − | | |
| − | 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 树]]的算法。 | | 如果一个贪心算法被证明可以为给定的问题类产生全局最优解，它通常成为选择的方法，因为它比动态规划等其他优化方法更快。这种贪心算法的例子有 [[Kruskal 算法]]和 [[Prim 算法]]用于寻找[[最小生成树]]，以及寻找最优 [[Huffman 树]]的算法。 |
| | | | |
| | + | 贪心算法也出现在网络[[路由]]中。使用贪心路由，消息被转发到邻近的节点，这是“最接近”的目标。一个节点的位置(因此是“贴近度”)的概念可以由它的物理位置来决定，就像临时网络使用的[[地理路由]]一样。位置也可能是一个完全人为的构造，就像[[小世界路由]]和[[分散式哈希表]]路由。 |
| | + | ==举例== |
| | | | |
| | + | * [[活动选择问题]]是这类问题的特征，其目标是选择彼此不冲突的最大活动数。 |
| | + | * 在[[麦金塔电脑]]游戏''[[Crystal Quest]]''中，目标是收集水晶，其方式类似于[[旅行商问题]]。游戏有一个演示模式，游戏使用贪心算法去每一个水晶。游戏AI（[[人工智能]]）不考虑障碍物，因此演示模式通常会很快结束。 |
| | + | * [[匹配追求]]是应用于信号近似的贪心算法的一个例子。 |
| | + | * 贪心算法为[[马尔法蒂问题]]找到了最优解，即在给定的三角形内找到三个不相交的圆，使圆的总面积最大化;据推测，同样的贪心算法对于任何数量的圆圈都是最优的。 |
| | + | * 贪心算法用于在[[霍夫曼编码]]期间构造霍夫曼树，以找到最优解。 |
| | + | * 在[[决策树学习]]中，通常使用贪心算法，但是不能保证它们能找到最优解。 |
| | + | ** 一种流行的此类算法是用于决策树构造的[[ID3算法]]。 |
| | + | * [[Dijkstra算法]]和相关的[[A*搜索算法]]是用于[[图搜索]]和[[最短路径查找]]的可验证的最优贪心算法。 |
| | + | ** A* 搜索是有条件最优的，需要一种不会高估路径成本的“[[可接受启发式算法]]”。 |
| | + | * [[Kruskal算法]]和[[Prim算法]]是用于构造给定连通图的[[最小生成树]]的贪心算法。他们总能找到一个最佳解决方案，这在一般情况下可能不是唯一的。 |
| | | | |
| − | 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 network]]s. 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.
| |
| − | | |
| − | *In the [[Macintosh computer]] game ''[[Crystal Quest]]'' the objective is to collect crystals, in a fashion similar to the [[travelling salesman problem]]. The game has a demo mode, where the game uses a greedy algorithm to go to every crystal. The [[artificial intelligence]] does not account for obstacles, so the demo mode often ends quickly.
| |
| − | | |
| − | *The [[matching pursuit]] is an example of greedy algorithm applied on signal approximation.
| |
| − | | |
| − | *A greedy algorithm finds the optimal solution to [[Malfatti circles|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.
| |
| − | | |
| − | *[[Dijkstra's algorithm]] and the related [[A* search algorithm]] are verifiably optimal greedy algorithms for [[graph search]] and [[Shortest path problem|shortest path finding]].
| |
| − | | |
| − | **A* search is conditionally optimal, requiring an "[[admissible heuristic]]" that will not overestimate path costs.
| |
| − | | |
| − | *[[Kruskal's algorithm]] and [[Prim's algorithm]] are greedy algorithms for constructing [[minimum spanning tree]]s of a given [[connected graph]]. They always find an optimal solution, which may not be unique in general.
| |
| − | | |
| − | | |
| − | ==See also==
| |
| | | | |
| | {{Portal|Mathematics}} | | {{Portal|Mathematics}} |
| | | | |
| − | *[[Multi-armed bandit#Semi-uniform strategies|Epsilon-greedy strategy]] | + | *[[Epsilon-贪婪策略|Epsilon-贪心策略]] |
| − | | |
| − | *[[Greedy algorithm for Egyptian fractions]]
| |
| − | | |
| − | *[[Greedy source]]
| |
| − | | |
| − | *[[Matroid]]
| |
| − | | |
| − | *[[Best-first search]]
| |
| − | | |
| | | | |
| − | ==Notes==
| + | *[[埃及分数的贪婪算法|埃及分数的贪心算法]] |
| | | | |
| − | <references />
| + | *[[贪婪源|贪心源]] |
| | | | |
| | + | *[[拟阵]] |
| | | | |
| − | ==References== | + | *[[最佳优先搜索]] |
| | + | ==参考== |
| | | | |
| | *''[[Introduction to Algorithms]]'' (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 16 "Greedy Algorithms". | | *''[[Introduction to Algorithms]]'' (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 16 "Greedy Algorithms". |
| 第186行： |
第135行： |
| | | | |
| | | | |
| − | ==External links== | + | ==外部链接== |
| | | | |
| | {{commons category|Greedy algorithms}} | | {{commons category|Greedy algorithms}} |