重み付きマトロイド

数学の一分野である組合せ論において、重み付きマトロイドは、各要素に重みを割り当てる関数を備えたマトロイドです。正式には、をマトロイドとし、E を要素の集合、I を独立集合の族とします。重み付きマトロイドは、の各要素に厳密に正の重みを割り当てる重み関数を持ちます。この関数を のサブセットに、 の和によって拡張します。 は、 における の和です。${\displaystyle M=(E,I)}$ ${\displaystyle w:E\rightarrow \mathbb {R} ^{+}}$${\displaystyle E}$${\displaystyle E}$${\displaystyle w(A)}$${\displaystyle w(x)}$${\displaystyle x}$${\displaystyle A}$

重み付きマトロイドに関する基本的な問題は、最大の総重みを持つ独立集合を見つけることです。この問題は、次の単純な貪欲アルゴリズムを使用して解決できます。

• 集合A を空集合に初期化します。マトロイドの定義により、A は独立集合であることに注意してください。
• E \ A内の各要素xについて、 Au{x} が依然として独立集合であるかどうかを確認します。
  • そのような要素がない場合、A はそれ以上拡張できないため停止します。
  • そのような要素が少なくとも 1 つある場合は、最大の重みを持つ要素を選択して A に追加します。

このアルゴリズムはマトロイド構造について何も知る必要はなく、マトロイドの 独立性オラクル、つまりセットが独立しているかどうかをテストするサブルーチンだけが必要です。

Jack Edmonds ^[1]は、この単純なアルゴリズムが実際に最大の重みを持つ独立集合を見つけることを証明しました。アルゴリズムによって見つかった集合をe ₁ ,...,e _kと表記します。マトロイド特性により、k = rank(M)であることは明らかで、そうでなければ集合を拡張できます。矛盾により、より高い重みを持つ別の集合があると仮定します。一般性を失うことなく、この集合にもrank(M)要素があると仮定することができます。これをf ₁ ,...,f _{kと表記します。これらの項目をw(f 1} ) ≥ ... ≥ w(f _k )となるように順序付けます。jをw(f _j ) > w(e _j )となる最初のインデックスとします。集合{f ₁ ,...,f _j }と{e ₁ ,...,e _j-1 }に拡張特性を適用すると、f _{i を{e 1} ,...,e _j-1 }に追加しても独立性を維持できるようなi ≤ jが存在するはずだという結論になります。しかしw(f _i ) ≥ w(f _j ) > w(e _j )なので、ステップjではe _{jではなくf iが}選択されるべきであり、これは矛盾である。^[2]

簡単な例として、グラフの最大全域の森を見つけたいとします。つまり、グラフと各辺の重みが与えられた場合、すべての頂点を含み、ツリー内の辺の合計重みを最大化する森を見つけます。この問題は、一部のクラスタリング アプリケーションで発生します。これは、上記の貪欲アルゴリズムのグラフィカル マトロイドへの特殊なケースと見なすことができるKruskal のアルゴリズムによって解決できます。

森林マトロイドの定義を見ると、最大全域森林は単純に合計重みが最大の独立集合であることがわかります。このような集合はグラフをまたがる必要があります。そうしないと、サイクルを作成せずにエッジを追加できます。しかし、どうやってそれを見つけるのでしょうか。

基底を見つけるための簡単なアルゴリズムがあります:

• 最初は空集合とします。${\displaystyle A}$
• それぞれについて${\displaystyle x}$${\displaystyle E}$
  • が独立している場合はに設定します。${\displaystyle A\cup \{x\}}$${\displaystyle A}$${\displaystyle A\cup \{x\}}$

結果は明らかに独立集合です。が の何らかのサブセットに対して独立でない場合、も独立ではないため、これは最大独立集合です (逆命題は遺伝的性質から得られます)。したがって、要素をパスすると、後でそれを使用する機会がなくなります。このアルゴリズムを一般化して、より難しい問題を解決します。 ${\displaystyle B\cup \{x\}}$${\displaystyle B}$${\displaystyle A}$${\displaystyle A\cup \{x\}}$

総重量が最大の独立セットは最適セットと呼ばれます。最適セットは常に基底です。なぜなら、エッジを追加できる場合は追加する必要があり、これにより総重量が増加するだけだからです。結局のところ、重み付きマトロイドの最適セットを計算するための簡単な貪欲アルゴリズムがあります。それは次のように機能します。

• 最初は空集合とします。${\displaystyle A}$
• のそれぞれについて、（単調に）重量が減少する順に並べると、 ${\displaystyle x}$${\displaystyle E}$
  • が独立している場合はに設定します。${\displaystyle A\cup \{x\}}$${\displaystyle A}$${\displaystyle A\cup \{x\}}$

このアルゴリズムは、上記のアルゴリズムの特殊なケースであるため、基底を見つけます。独立性を維持しながら、常に最大重みの要素を選択します (したがって、「貪欲」という用語が使用されています)。これにより、常に最適なセットが生成されます。つまり、 と が生成されるものとします。次に、である任意の について、開集合とについて考えます。は より小さいため、 の何らかの要素をに入れても結果が独立性を保つことができます。ただし、は独立性を維持するためにに追加できる最大重みの要素です。したがって、の何らかの要素よりも重みが小さくなることはありません。したがって、 として、 は少なくとも大きな a の重みを持ちます。これはすべての に当てはまるため、 はよりも重みが重いです。 ${\displaystyle A=\{e_{1},e_{2},\ldots ,e_{r}\}}$${\displaystyle B=\{f_{1},f_{2},\ldots ,f_{r}\}}$${\displaystyle k}$${\displaystyle 1\leq k\leq r}$${\displaystyle O_{1}=\{e_{1},\ldots ,e_{k-1}\}}$${\displaystyle O_{2}=\{f_{1},\ldots ,f_{k}\}}$${\displaystyle O_{1}}$${\displaystyle O_{2}}$${\displaystyle O_{2}}$${\displaystyle O_{1}}$${\displaystyle e_{k}}$${\displaystyle O_{1}}$${\displaystyle e_{k}}$${\displaystyle O_{2}}$${\displaystyle e_{k}}$${\displaystyle f_{k}}$${\displaystyle k}$${\displaystyle A}$${\displaystyle B}$

のメンバーを希望の順序で走査する最も簡単な方法は、メンバーをソートすることです。これには、比較ソートアルゴリズム を使用した時間が必要です。また、各 が独立しているかどうかをテストする必要があります。独立性テストに時間が必要であると仮定すると、アルゴリズムの合計時間は です。 ${\displaystyle E}$${\displaystyle O(|E|\log |E|)}$${\displaystyle x}$${\displaystyle A\cup \{x\}}$${\displaystyle O(f(|E|))}$${\displaystyle O(|E|\log |E|+|E|f(|E|))}$

代わりに最小全域木を見つけたい場合は、大きな定数から重み関数を減算して単純に「反転」します。より具体的には、がすべてのグラフ エッジの合計重みを超えるとします。この簡単な方法で、あらゆる種類のマトロイドと重み関数に関するさらに多くの最適化問題を解決できますが、多くの場合、より特殊な特性を利用するより効率的なアルゴリズムが見つかります。 ${\displaystyle w_{\text{min}}(x)=W-w(x)}$${\displaystyle W}$

また、ダウンセットではあるがマトロイドではない「独立した」集合の集合を取る場合、貪欲アルゴリズムが常に機能するわけではないことにも注意してください。 の場合、となる独立集合とが存在しますが、 の場合 となるような独立集合は存在しません。 ${\displaystyle I}$${\displaystyle I_{1}}$${\displaystyle I_{2}}$${\displaystyle |I_{1}|<|I_{2}|}$${\displaystyle e\in I_{2}\setminus I_{1}}$${\displaystyle I_{1}\cup e}$

となる と を選びます。からの範囲の の要素、から の範囲のの要素、からの範囲のの要素、 から の範囲の残りの要素に重みを付けます。貪欲アルゴリズムは の要素を選択し、その後 の要素を選択できなくなります。したがって、構築される独立集合の重みは最大で になり、 の重みよりも小さくなります。 ${\displaystyle \epsilon >0}$${\displaystyle \tau >0}$${\displaystyle (1+2\epsilon )|I_{1}|+\tau |E|<|I_{2}|}$${\displaystyle I_{1}\cup I_{2}}$${\displaystyle 2}$${\displaystyle 2+2\epsilon }$${\displaystyle I_{1}\setminus I_{2}}$${\displaystyle 1+\epsilon }$${\displaystyle 1+2\epsilon }$${\displaystyle I_{2}\setminus I_{1}}$${\displaystyle 1}$${\displaystyle 1+\epsilon }$${\displaystyle 0}$${\displaystyle \tau }$${\displaystyle I_{1}}$${\displaystyle I_{2}\setminus I_{1}}$${\displaystyle (1+2\epsilon )|I_{1}|+\tau |E|+|I_{1}\cup I_{2}|}$${\displaystyle I_{2}}$

この最適化アルゴリズムはマトロイドを特徴付けるために使用できます。集合の族Fが部分集合を取りながら閉じており、集合の重み付けに関係なく貪欲アルゴリズムによって族内で最大重み集合が見つかるという性質がある場合、Fはマトロイドの独立集合の族でなければなりません。^[3]

マトロイドの概念は、貪欲アルゴリズムが最適解を与える他の種類の集合を可能にするために一般化されました。詳細については、貪欲アルゴリズムとマトロイド埋め込みを参照してください。Korte と Lovász は、これらのアイデアを、貪欲アルゴリズムによってさらに大規模なクラスの問題を解決できる、貪欲なオブジェクトと呼ばれるオブジェクトに一般化しました。