Matroidの独立性・greedy・線形交差
概要
安いものから選び、条件を壊す候補だけを飛ばす貪欲法は、どの選択問題でも正しいわけではない。ベクトルの線形独立性や、辺集合が森であるという条件では、選択の正しさを「独立集合」と「交換公理」で共通に説明できる。この構造を matroid(マトロイド)と呼ぶ。
まず一つの matroid で何を確かめれば貪欲法を使えるかを学び、その後に二つの独立性条件を同時に課す場合へ進む。
考え方
三ベクトルから独立集合・基底・rankを知る
は、成分を とし、加算を XOR で行う二元体である。選べる要素を、次の三つのベクトルとする。価格は順に とする。
選べる要素全体の集合を と書く。ここでは、選んだベクトルが線形独立である集合、つまり空でない部分集合の XOR が にならない集合を独立集合とする。全ての部分集合を調べると、次のようになる。
| 選ぶ集合 | 独立性と理由 |
|---|---|
| 独立。非空の部分集合がない | |
| 独立。どれも零ベクトルではない | |
| 独立。異なる二本なので、一本でも二本の XOR でも にならない | |
| 従属。 になる |
独立集合に、残りのどの要素も追加できなくなったら極大という。「極大」は追加できないという意味で、個数が最大かどうかは定義に含まない。極大な独立集合を基底と呼ぶ。この例の基底は三つの二要素集合で、価格の合計はそれぞれ である。
集合 に含まれる独立集合の最大サイズを (rank、階数)と呼ぶ。この例では であり、どの基底も二本で全ベクトルを XOR で作れる。価格順に を採用すると、 は作れる値を増やさないので拒否し、費用 の最小基底を得る。各判定の手順と最適性は子単元の matroid greedyで追う。
貪欲法を支える三つの公理
一般に、有限の要素集合 と、独立とみなす部分集合を全て集めた族 を考える。次の三条件を満たす組 が matroid である。
- 空集合は独立である: 。
- 独立集合の部分集合も独立である(遺伝性)。
- 独立集合 が を満たすなら、ある を に加えても独立である(交換公理)。
三つ目は、まだ選択数が少ない側には、大きい独立集合から一つ追加する余地があるという条件である。例えば なら、 のどちらを に追加しても独立になる。
交換公理により、極大独立集合は全て同じサイズになる。もし基底 より大きい独立集合 があれば、 に一つ追加できて極大性に反するからである。同じ議論は任意の候補集合 の中でも成り立つため、 内で極大まで選べばサイズは必ず になる。これが、重み順に見た候補のどの範囲でも、貪欲法が選択数で損をしない理由になる。
線形独立性と森では、何を判定するか
**独立性 oracle(判定手続き)**は、与えた集合が独立かを返す処理を指す。貪欲法では、現在の独立集合に候補を一つ加えてよいかを問い合わせる。matroid であることの証明と、判定を速く実装することは別の仕事である。
- 線形 matroid: ベクトルの線形独立な集合を使う。空集合・遺伝性は線形独立性から従う。交換公理は、 のとき、独立な の全ベクトルが の張る空間に入ることはない、と次元を比較すれば分かる。oracle は候補を現在の基底で消去し、零になれば拒否、零でなければ採用して基底を更新する。 上の実装は XOR線形基底へ進む。
- グラフ的 matroid: 無向グラフの辺を要素とし、閉路を持たない辺集合(森)を独立とする。辺を減らしても森である。森 で のとき、 の全辺が の各連結成分内に収まると仮定すると、各成分内で が持てる辺数は頂点数から一を引いた数以下なので、合計も 以下となり矛盾する。従って の異なる成分を結ぶ の辺を追加できる。oracle は Union-Find で両端が別成分なら採用・併合し、同じ成分なら拒否する。重みの小さい順に行うと Kruskal 法になる。
二つのmatroidを同時に課すと交換できないことがある
四頂点を順に結ぶ三辺の道を考える。辺を 、、 とする。端点を共有しない辺の集合を matching(マッチング)という。この道の matching は、空集合、三つの一辺集合、 の計五つである。
と はどちらも matching で、 である。しかし を に足すと 、 を足すと が重なる。 のどれも追加できず、交換公理が壊れる。 は極大だが最大ではなく、中辺を先に採用するだけで最大の二辺を逃す。
この matching の条件は、実は二つの matroid の共通条件である。道を二部グラフとして、片側を 、もう片側を に分ける。
| 課す条件 | 辺の分割(各グループから高々一本) |
|---|---|
| 側の各頂点で高々一本 | |
| 側の各頂点で高々一本 |
それぞれは**分割 matroid(partition matroid)**である。空集合と遺伝性を満たし、 なら、 が一本選んでいて がまだ選んでいないグループがあるので、そこから一辺追加できる。一方、両方を同時に満たすと matching になり、上の反例が生じる。一方で追加できる辺が、もう一方でも追加できるとは限らないのである。
成立条件と計算量
単一 matroid の最適基底は、重み順に oracle で独立性を確かめる貪欲法で求まる。候補数を 、一回の追加判定・更新の費用を高々 とすると、ソートを含む時間は である。具体的な判定費用と保存領域は oracle の実装で決まる。
二つの matroid の共通独立集合を最適化するmatroid 交差では、この貪欲法の保証は失われる。一般の matching や交差を同じ選択手順で解けるとは考えない。線形matroid交差の乱択rank判定では、二つの制約がともに線形表現できる場合に、共通独立集合の最大サイズを乱択行列の rank で調べる。ABC399 G の森林・色別上限もこの側の問題であり、集合の復元まで rank 一回でできるとは限らない。
下位単元
- matroid greedy — 黄色
- 線形matroid交差の乱択rank判定 — 赤色
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
導入対象の目安: 黄色(2000–2399)。独立性と交換公理を使い、貪欲法の成立範囲を整理する入口。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 組合せ・多項式・線形代数。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-matroid-theory
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
このUnitでは扱わないもの
- 線形方程式一般、graph matching一般、および交換公理を用いない単なる貪欲選択。