貪欲な

組合せ論において、グリードイドは集合システムの一種です。これはマトロイドの概念から生まれました。マトロイドはもともと1935 年にWhitneyによって平面グラフの研究のために導入され、後にEdmondsによって貪欲アルゴリズムによって解決できる最適化問題のクラスを特徴付けるために使用されました。1980 年頃、KorteとLovász は貪欲アルゴリズムのこの特徴付けをさらに一般化するためにグリードイドを導入しました。これがグリードイドという名前が付けられた理由です。数学的最適化の他に、グリードイドはグラフ理論、言語理論、順序理論、その他の数学の分野にも関連付けられています。

集合系 ( F , E )は、基底集合Eの部分集合の集合Fです(つまり、FはEのべき集合の部分集合です)。グリードイドを考えるとき、Fのメンバーは実行可能集合と呼ばれます。マトロイドを考えるとき、実行可能集合は独立集合とも呼ばれます。

アクセス可能な集合系 （F , E ）は、空でない実行可能集合Xのすべてが実行可能な要素xを含む集合系である。これは、空でない有限のアクセス可能な集合系には必ず空集合∅が含まれることを意味する。^[1]${\displaystyle X\setminus \{x\}}$

グリードイド（F、E）は、交換 特性を満たすアクセス可能な集合システムです。

• すべてに対して、​${\displaystyle X,Y\in F}$${\displaystyle |X|>|Y|,}$${\displaystyle x\in X\setminus Y}$${\displaystyle Y\cup \{x\}\in F.}$

(注: 一部の人々は、交換特性という用語を貪欲に基づく条件のために留保し、上記の条件を「増加特性」と呼ぶことを好みます。)

グリードイドの基底は最大実行可能集合です。つまり、実行可能集合ですが、他のどの集合にも含まれていません。 EのサブセットXの基底は、 Xに含まれる最大実行可能集合です。

グリードイドのランクは基底のサイズです。交換特性により、すべての基底は同じサイズです。したがって、ランク関数は明確に定義されます。EのサブセットXのランクは、 Xの基底のサイズです。マトロイドと同様に、グリードイドはランク関数に関して暗号同型性を持ちます。 ^[2] 関数が基底セットE上のグリードイドのランク関数であるためには、rがサブカーディナル、単調、局所的に半モジュラである必要があります。 つまり、任意の および任意の に対して、次が成り立ちます。${\displaystyle r:2^{E}\to \mathbb {Z} }$${\displaystyle X,Y\subseteq E}$${\displaystyle e,f\in E}$

• サブカーディナリティ:${\displaystyle r(X)\leq |X|}$
• 単調性:いつでも${\displaystyle r(X)\leq r(Y)}$${\displaystyle X\subseteq Y\subseteq E}$
• 局所的半モジュール性:いつでも${\displaystyle r(X)=r(X\cup \{e,f\})}$${\displaystyle r(X)=r(X\cup \{e\})=r(X\cup \{f\})}$

グリードイドのほとんどのクラスには、集合システム、言語、poset、単体複体などの観点から同等の定義が多数あります。以下の説明では、よく知られている特徴のいくつかのみをリストするという従来の方法を採用しています。

区間グリードイド （F、E）は区間プロパティを満たすグリードイドです。

• とすれば、すべてに対して${\displaystyle A,B,C\in F}$${\displaystyle A\subseteq B\subseteq C,}$${\displaystyle x\in E\setminus C:}$

$${\displaystyle {\begin{matrix}A\cup \{x\}\in F\\C\cup \{x\}\in F\end{matrix}}\implies B\cup \{x\}\in F.}$$

同様に、区間グリードイドは、任意の 2 つの実行可能集合の和集合が別の実行可能集合に含まれている場合に実行可能であるようなグリードイドです。

反マトロイド ( F , E ) は、上限のない区間特性を満たすグリードイドです。

• ⁠ ⁠${\displaystyle A,B\in F}$と⁠ ⁠${\displaystyle A\subseteq B,}$の場合、すべての⁠ ⁠ ${\displaystyle x\in E\setminus B,}$ ⁠ ⁠に対して${\displaystyle A\cup \{x\}\in F}$⁠ ⁠ ⁠が成り立ちます。${\displaystyle B\cup \{x\}\in F.}$

同様に、反マトロイドは (i) 一意の基底を持つグリードイド、または (ii) 和集合の下で閉じたアクセス可能な集合システムです。反マトロイドが区間グリードイドでもあることは容易にわかります。

マトロイド( F , E ) は、 下限のない区間特性を満たす空でないグリードイドです。

• ⁠ ⁠${\displaystyle B,C\in F}$と⁠ ⁠${\displaystyle B\subseteq C,}$の場合、すべての⁠ ⁠ ${\displaystyle x\in E\setminus C,}$ ⁠ ⁠に対して${\displaystyle C\cup \{x\}\in F}$⁠ ⁠ ⁠が成り立ちます。${\displaystyle B\cup \{x\}\in F.}$

マトロイドが区間グリードイドでもあることは容易にわかります。

• 無向グラフ Gを考えてみましょう。基底集合をGの辺とし、実行可能集合をGの各フォレスト（つまり、サイクルを含まないサブグラフ）の辺集合とします。この集合系はサイクルマトロイドと呼ばれます。集合系が何らかのグラフのサイクルマトロイドである場合、その集合系はグラフィックマトロイドと呼ばれます。（もともとサイクルマトロイドは回路、つまり最小従属集合上で定義されていました。そのためサイクルという名前が付けられています。）
• 頂点rを根とする有限の無向グラフGを考えます。基底集合を Gの頂点とし、実行可能集合をGの連結サブグラフを誘導するr を含む頂点サブセットとします。これは頂点探索グリードイドと呼ばれ、反マトロイドの一種です。
• rを根とする有限の有向グラフ D を考えます。基底集合を D の (有向) 辺とし、実行可能集合をrを根とし、すべての辺がrから離れる方向を向いている各有向部分木の辺集合とします。これは直線探索グリードイド、または有向分岐グリードイドと呼ばれます。これは区間グリードイドですが、反マトロイドでもマトロイドでもありません。
• m × n 行列 Mを考えます。基底集合E を1 からnまでの列のインデックスとし、実行可能集合を とします。これは、この構造がガウス消去法アルゴリズムの基礎となるため、ガウス消去法グリードイドと呼ばれます。これはグリードイドですが、区間グリードイドではありません。$${\displaystyle F=\{X\subseteq E:{\text{ 部分行列 }}M_{\{1,\ldots ,|X|\},X}{\text{ は可逆行列}}\}}.}$$

一般的に、貪欲アルゴリズムは、利用可能な選択肢がすべて尽きるまで、各ラウンドで局所的に最良の選択（通常は最大重みの入力）が選択される反復プロセスにすぎません。貪欲アルゴリズムが最適である（つまり、最大値の基底を取得する）貪欲ベースの条件を説明するには、貪欲理論のより一般的な用語が必要です。 一般性を失うことなく、 Eが有限である貪欲G = ( F、E )を検討します。

EのサブセットX は、Xと任意の実行可能セットとの最大の交差のサイズがXのランクに等しい場合、ランク実行可能です。マトロイドでは、Eのすべてのサブセットはランク実行可能です。ただし、この等式は一般にグリードイドには当てはまりません。

関数がR互換であるとは、すべての実数cに対してランク実行可能である場合です。 ${\displaystyle w:E\to \mathbb {R} }$${\displaystyle \{x\in E:w(x)\geq c\}}$

目的関数が集合上で線形であるのは、ある重み関数に対して${\displaystyle f:2^{S}\to \mathbb {R} }$${\displaystyle S}$${\displaystyle X\subseteq S,}$${\displaystyle f(X)=\sum _{x\in X}w(x)}$ ${\displaystyle w:S\to \Re .}$

命題。貪欲アルゴリズムは、貪欲法上のすべてのR互換の線形目的関数 に最適です。

この命題の背後にある直感は、反復プロセス中に、最小の重みのそれぞれの最適な交換が交換特性によって可能になり、基礎となる貪欲法の実行可能セットから最適な結果が得られるというものです。この結果により、多くのよく知られたアルゴリズムの最適性が保証されます。たとえば、重み付きグラフの最小全域木は、サイクルマトロイドの貪欲アルゴリズムであるクラスカルのアルゴリズムを使用して取得できます。プリムのアルゴリズムは、代わりに直線探索貪欲法を取ることで説明できます。

• マトロイド
• ポリマトロイド

• Björner, Anders ; Ziegler, Günter M. (1992)、「8. グリードイド入門」、White, Neil (編)、『マトロイドの応用』、数学とその応用百科事典、第 40 巻、ケンブリッジ: ケンブリッジ大学出版局、pp. 284–357、doi :10.1017/CBO9780511662041.009、ISBN 0-521-38165-7、MR  1165537、Zbl  0772.05026
• エドモンズ、ジャック(1971)、「マトロイドと貪欲アルゴリズム」、数学プログラミング、1 : 127–136、doi :10.1007/BF01584082、S2CID  5599224、Zbl  0253.90027。
• ヘルマン、ポール; モレット、バーナード ME; シャピロ、ヘンリー D. (1993)、「貪欲構造の正確な特徴付け」、SIAM Journal on Discrete Mathematics、6 (2): 274–283、CiteSeerX  10.1.1.37.1825、doi :10.1137/0406021、Zbl  0798.68061。
• Korte, Bernhard ; Lovász, László (1981)、「貪欲アルゴリズムの基礎となる数学的構造」、Gecseg, Ferenc (編)、Fundamentals of Computation Theory: Proceedings of the 1981 International FCT-Conference、Szeged、Hungaria、1981 年 8 月 24 ～ 28 日、Lecture Notes in Computer Science、vol. 117、ベルリン: Springer-Verlag、pp. 205 ～ 209、doi :10.1007/3-540-10854-8_22、Zbl  0473.68019。
• コルテ、ベルンハルト。Lovász, ラスロー; Schrader、Rainer (1991)、Greedoids、Algorithms and Combinatorics、vol. 4、ニューヨーク、ベルリン: Springer-Verlag、ISBN 3-540-18190-3、ZBL  0733.05023。
• オクスリー、ジェームズ・G.（1992）「マトロイド理論」、オックスフォード・サイエンス・パブリケーションズ、オックスフォード：オックスフォード大学出版局、ISBN 0-19-853563-5、ZBL  0784.05002。
• ホイットニー、ハスラー（1935）、「線形独立性の抽象的性質について」、アメリカ数学誌、57（3）：509–533、doi：10.2307/2371182、hdl：10338.dmlcz/100694、JSTOR  2371182、Zbl  0012.00404。

• グリードイドの紹介
• 貪欲アルゴリズムの理論 2016-03-04 にWayback Machineでアーカイブ
• 劣モジュラ関数と最適化
• マッチング、マトロイド、劣モジュラー関数