matroid greedy

概要

安い順に選んでも、後で必要な要素を追加できなくなれば最適とは限らない。matroid では交換公理がこの行き詰まりを防ぎ、独立性を保つ候補だけを価格順に採用すると最小費用の基底になる。具体的な選択を追った後、その理由を「どの prefix でも選択数が最大になる」という性質から証明する。

考え方

価格順の選択とoracleの中身

親単元の三ベクトル a=(1,0),b=(0,1),c=(1,1)a=(1,0),b=(0,1),c=(1,1) を、価格 1,2,31,2,3 の順に見る。加算は二元体 F2\mathbf F_2 上の XOR とする。選択集合 GG は空から始める。独立性 oracle は、候補を現在の基底で消去して、零になるかを判定する手続きである。

候補(価格)消去と判定集合・費用
a (1)a\ (1)基底は空なので (1,0)(1,0) が残る。採用{a}, 1\{a\},\ 1
b (2)b\ (2)aa では (0,1)(0,1) を消せない。採用{a,b}, 3\{a,b\},\ 3
c (3)c\ (3)c⊕a=(0,1)c\oplus a=(0,1)、さらに bb と XOR すると 00。拒否{a,b}, 3\{a,b\},\ 3

第三ベクトルを拒否するのは、既に c=a⊕bc=a\oplus b と表せるからである。採用済みの集合が独立である限り、消去して零になることと、候補を加えると従属になることは同値である。三つの基底 {a,b},{a,c},{b,c}\{a,b\},\{a,c\},\{b,c\} の費用は 3,4,53,4,5 なので、この選択は最小費用になっている。

交換も小例で追える。別の基底 {b,c}\{b,c\} に最初の選択 aa を入れたければ、c=a⊕bc=a\oplus b を使って cc と aa を交換し、{a,b}\{a,b\} にできる。作れるベクトルの範囲を保ったまま、費用を 55 から 33 に下げられる。ABC236 F の解説では、この「貪欲な選択を含む最適基底を残す」という交換を一般のベクトルで示している。

全てのprefixで選択数を最大にする

一般の matroid でも同じことを示す。要素集合を EE、独立集合族を I\mathcal I とする。空集合が独立であり、独立集合の部分集合も独立であり、A,B∈IA,B\in\mathcal I かつ ∣A∣<∣B∣|A|<|B| なら B∖AB\setminus A のある要素を AA へ追加できると仮定する。最後が交換公理で、全ての基底(極大独立集合)は同じサイズ r=rank⁡(E)r=\operatorname{rank}(E) を持つ。

まず最大重み基底を考える。候補数を m=∣E∣m=|E| とし、重みが w1≥w2≥⋯≥wmw_1\geq w_2\geq\cdots\geq w_m となるように要素を並べ、同じ重みの順序は任意に固定する。以下では要素をその順番 1,…,m1,\ldots,m で表す。空集合から、独立性を保つ候補だけを採用する。

最初の jj 要素の集合を prefix と呼び、Pj={1,…,j}P_j=\{1,\ldots,j\} と書く。そこまで処理した選択集合を GjG_j とする。一度拒否した要素を、後で追加できるようになることはない。もし後の大きい選択集合に追加して独立なら、その部分集合である拒否時の集合に追加しても独立となり、拒否したことと矛盾するからである。

従って GjG_j は PjP_j 内で極大である。これより大きい独立集合が PjP_j 内にあれば交換公理で一つ追加できてしまうので、

∣Gj∣=rank⁡(Pj)|G_j|=\operatorname{rank}(P_j)

が成り立つ。最終的な選択を G=GmG=G_m とすると、G∩Pj=GjG\cap P_j=G_j である。任意の基底 BB に対して B∩PjB\cap P_j も独立なので、

∣G∩Pj∣≥∣B∩Pj∣|G\cap P_j|\geq |B\cap P_j|

となる。貪欲法は最終的なサイズを合わせるだけでなく、どの prefix でも他の基底以上に多く選んでいる。

三ベクトルの最小費用の例は、価格の符号を反転した重み (−1,−2,−3)(-1,-2,-3) の最大化とみなせる。prefix は {a},{a,b},E\{a\},\{a,b\},E で、rank と選択数は順に 1,2,21,2,2 である。他の基底 {a,c}\{a,c\} の prefix 内個数は 1,1,21,1,2、{b,c}\{b,c\} では 0,1,20,1,2 となり、上の不等式を確かめられる。

prefixの個数から重みの合計へつなぐ

基底 BB の重み合計は、全要素に最低の重み wmw_m を割り当て、早い位置にある要素ほど差分を足す形に分解できる。

∑i∈Bwi=wmr+∑j=1m−1(wj−wj+1) ∣B∩Pj∣\begin{gathered} \sum_{i\in B}w_i\\ =w_m r+\sum_{j=1}^{m-1}(w_j-w_{j+1})\,|B\cap P_j| \end{gathered}

位置 ii の要素には j=i,…,m−1j=i,\ldots,m-1 の差分が加わり、望遠和でちょうど wiw_i になる。全基底でサイズ rr は共通なので第一項は同じであり、各差 wj−wj+1w_j-w_{j+1} は非負である。貪欲法は全ての prefix の個数を最大にするから、重み合計も最大になる。要素がない場合は空基底を返し、上の式は m≥1m\geq1 の場合に使う。

三ベクトルでは、貪欲な基底の重みは (−3)⋅2+1⋅1+1⋅2=−3(-3)\cdot2+1\cdot1+1\cdot2=-3 で、符号を戻すと費用 33 である。価格の符号反転は大小を逆にするので、最小重み基底は価格の昇順で同じ選択をすればよい。

成立条件と計算量

この証明は負重みを含む基底にも成立する。基底まで選ぶ問題では、重みが負でもサイズ rr になるまで独立な要素を追加する。一方、サイズを固定しない任意独立集合の最大化では、負重みの要素を外すと必ず改善するので採用しない。非負の要素だけに候補を制限しても matroid の公理は保たれるため、その範囲で同じ貪欲法を使える。重みが零の要素は採用してもしなくてもよい。最小化でサイズを固定しない場合も、正の費用まで払って基底を完成させる必要はない。この三ベクトルの例なら空集合の費用は 00 だが、全ベクトルを生成するという要求を満たさないので基底を求める。

候補数 mm、一回の追加判定・採用時の更新に高々 TT 時間かかるなら、ソートを含めて O(mlog⁡m+mT)O(m\log m+mT) 時間である。候補・重み・選択集合の保存に O(m)O(m)、それに oracle が保持する作業領域を加える。dd bit 整数の XOR 線形基底を使い、各整数の XOR を定数時間と数えるなら、一候補の消去は O(d)O(d) 時間、基底の領域は O(d)O(d) 語なので、全体は O(mlog⁡m+md)O(m\log m+md) 時間・O(m+d)O(m+d) 語となる。

二つの matroid の共通制約には、この証明をそのまま使えない。親単元の三辺の道では、中辺一つの matching に両端のどちらも追加できず、prefix 内で極大でも最大とは限らない。単一 matroid の基底の貪欲法と、matching や matroid 交差の最適化を区別する。

問題一覧

  • ABC236 F「Spices」 公式問題
    組合せ: XOR線形基底
    技能・出典
    主題: matroid greedy(独立集合族の交換公理を確認し、重み順に独立性oracleを通すgreedyが最適基底を作ることを証明する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: XOR線形基底(整数をF2 vectorとして最高bit pivotで消去し、独立性判定・最大XOR・表現可能性をonlineに保つ。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。

    主タグ: matroid greedy / 補助タグ: XOR線形基底

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

前提・学習成果・出典

習得対象の目安: 黄色(2000–2399)。独立性oracleと交換公理から、重み順の選択が最適基底を与えることを示す。

対象色の読み方は本書の読み方を参照してください。

概念上の親: Matroidの独立性・greedy・線形交差。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-matroid-greedy

matroid greedy

習得する技能

  • 独立集合族の交換公理を確認し、重み順に独立性oracleを通すgreedyが最適基底を作ることを証明する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 交換論から選択順を導く。

このUnitを直接前提とする単元: 線形matroid交差の乱択rank判定。

独立集合族と交換公理を確認し、重み順の貪欲法が最適基底を作る理由を、prefix の rank と重み合計の分解から証明する。

このUnitでは扱わないもの

  • matroid greedyの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠