Greedoid

释义 Definition

greedoid（拟阵/贪心结构）：一种在组合优化中使用的数学结构，用来刻画“贪心算法在某些约束下仍能逐步构造可行解”的情形。它与 matroid（拟阵） 相关，但更一般，常用于研究可行集合的“可逐步扩展性（accessibility）”等性质。（该词主要用于数学与计算机科学语境。）

发音 Pronunciation (IPA)

/ˈɡriːdɔɪd/

例句 Examples

A greedoid generalizes a matroid for certain greedy constructions.
Greedoid 在某些贪心式构造问题中是对 matroid（拟阵）的推广。

In the reachability problem, the family of feasible vertex sets can form a greedoid, which helps justify a step-by-step greedy procedure.
在可达性问题中，可行的顶点集合族可能构成一个 greedoid，从而为逐步推进的贪心过程提供理论依据。

词源 Etymology

greedoid 由 greedy（贪心的） + 类似结构名词后缀 -oid（……状/类似……的） 构成，字面含义接近“具有贪心特征的结构”。该术语在组合优化与离散数学文献中用于描述与贪心算法密切相关的一类集合系统。

相关词 Related Words

• Greedy
• Matroid
• Optimization
• Combinatorics
• Feasible
• Independence
• Algorithm

文学与著作中的用例 Literary / Notable Works

• Bernhard Korte, László Lovász, Rainer Schrader，《Greedoids》：系统介绍 greedoid 的定义、性质与应用的经典专著。
• Bernhard Korte, Jens Vygen，《Combinatorial Optimization: Theory and Algorithms》：在组合优化框架下讨论与 greedoid/拟阵相关的贪心思想与结构。
• 学术论文与教材中关于 antimatroid、branching greedoids、reachability greedoids 等主题的章节/条目也常出现该词。