拟阵（Matroid）：组合数学中的一种抽象结构，用来概括“独立性/线性无关”这类概念（例如向量的线性无关、图中的无环边集）。它把“哪些子集算独立”用公理化方式描述，从而统一处理许多不同领域的“独立”问题。（该词基本是专业术语。）
/ˈmeɪtrɔɪd/
A matroid captures the idea of independence.
拟阵用来刻画“独立性”这一概念。
Using a matroid model, we can justify why a greedy algorithm finds an optimal solution for certain selection problems.
借助拟阵模型，我们可以解释为什么贪心算法在某些选择类问题中能得到最优解。
matroid 由 matrix（矩阵） 的词根联想与后缀 -oid（……状/类似……的） 组合而来，表示“类似矩阵所体现的线性无关结构的东西”。该术语通常被认为源于 Hassler Whitney 在 20 世纪 30 年代对“线性依赖的抽象性质”的研究命名传统。
Select Language