マトロイドとは？
まとろいど
マトロイドとは、線形代数の「一次独立」という概念を抽象化した数学的構造で、組合せ最適化や貪欲アルゴリズムの理論的基盤として重要です。
マトロイドは、1935年にハスラー・ホイットニーが提唱した数学的構造で、集合とその部分集合族（独立集合族）によって定義されます。名前は行列（matrix）に由来し、線形独立という概念を一般化したものです。
集合Eとその部分集合族Iがマトロイドをなすには、次の条件が必要です。
- 空集合は独立集合に含まれる
- 独立集合の部分集合も独立集合である（遺伝性）
- 小さい独立集合は大きい独立集合から要素を1つ追加して拡張できる（拡張性）
代表的な例として線形マトロイド（行列の列ベクトル間の線形独立性）とグラフマトロイド（グラフの閉路を含まない辺集合＝森）があります。後者では最大の独立集合が全域木に対応します。
マトロイドが特に重要なのは、貪欲アルゴリズムが最適解を保証する問題の構造的条件がマトロイドと一致するからです。クラスカル法による最小全域木の探索がその典型例で、毎回最小コストの辺を加える貪欲戦略が必ず最適になる理由はグラフマトロイドの性質によって説明されます。ネットワーク設計・スケジューリング・機械学習の特徴選択など幅広い領域で活用されています。
使い方・例文
グラフの最小全域木を求めるクラスカル法が「なぜ貪欲に辺を選んでも最適になるのか」を理論的に説明するとき、マトロイドの概念が使われます。
この用語をシェア
最終更新: