Greedy Algorithm

定义 Definition

贪心算法：一种算法设计策略，在求解过程中每一步都选择当前看起来最优（局部最优）的选项，希望由此得到整体最优解。它通常实现简单、速度快，但不一定总能得到全局最优；在满足特定条件（如“贪心选择性质”“最优子结构”）的问题上才可靠。

发音 Pronunciation (IPA)

/ˈɡriːdi ˈælɡəˌrɪðəm/

例句 Examples

A greedy algorithm picks the best option at each step.
贪心算法在每一步都会选择当前最好的选项。

Although a greedy algorithm is efficient, it may fail to find the global optimum for some problems.
尽管贪心算法很高效，但对某些问题它可能无法找到全局最优解。

词源 Etymology

greedy 原义是“贪婪的”，引申为“只顾眼前、每次都想拿最多”。algorithm 源自中世纪拉丁语 algorismus，与波斯数学家 al-Khwarizmi（花剌子密） 的名字相关，后来演变为“算法”的通用术语。合起来 greedy algorithm 形象地表达“每一步都先拿眼前最划算的”这种解题方式。

相关词 Related Words

• Heuristic
• Optimization
• Dynamic Programming
• Backtracking
• Dijkstra’s Algorithm
• Prim’s Algorithm
• Kruskal’s Algorithm
• Minimum Spanning Tree
• Matroid

文学与经典著作中的用例 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在“Greedy Algorithms”相关章节系统讲解贪心思想与典型问题。
• Algorithms（Robert Sedgewick & Kevin Wayne）：涵盖多种贪心相关主题（如最小生成树、最短路径的相关算法与思想对比）。
• The Algorithm Design Manual（Steven S. Skiena）：以设计策略视角讨论贪心法的适用性、陷阱与案例。
• Combinatorial Optimization: Algorithms and Complexity（Papadimitriou & Steiglitz）：在组合优化框架下讨论贪心方法与其理论条件（如与拟阵等结构的联系）。