貪欲な

コンテンツへジャンプ

メインメニュー

メインメニュー

サイドバーに移動隠れる

ナビゲーション

• メインページ
• コンテンツ
• 時事問題
• ランダム記事
• Wikipediaについて
• お問い合わせ

貢献する

• ヘルプ
• 編集方法を学ぶ
• コミュニティポータル
• 最近の変更
• ファイルをアップロード
• 特別ページ

検索

検索

外観

• 寄付する
• アカウントを作成する
• ログイン

個人用ツール

• 寄付する
• アカウントを作成する
• ログイン

コンテンツ

サイドバーに移動隠れる

• （トップ）
• 1定義
• 2クラス
• 3つの例
• 4貪欲アルゴリズム
• 5参照
• 6参考文献
• 7外部リンク

目次を切り替える

2つの言語

• イタリア語
• 日本語

リンクを編集

• 記事
• 話す

英語

• 読む
• 編集
• 履歴を表示

ツール

ツール

サイドバーに移動隠れる

アクション

• 読む
• 編集
• 履歴を表示

一般的な

• ここへのリンク
• 関連する変更
• ファイルをアップロード
• パーマリンク
• ページ情報
• このページを引用する
• 短縮URLを取得する
• QRコードをダウンロード

印刷/エクスポート

• PDFとしてダウンロード
• 印刷可能なバージョン

他のプロジェクト

• ウィキデータ項目

外観

サイドバーに移動隠れる

フリー百科事典『ウィキペディア』より

貪欲最適化で使用される集合システム

組合せ論において、グリードイドは集合系の一種です。これはマトロイドの概念に由来します。マトロイドは、1935年にホイットニーによって平面グラフの研究のために最初に導入され、後にエドモンズによって、貪欲アルゴリズムによって解ける最適化問題のクラスを特徴付けるために使用されました。1980年頃、コルテとロヴァースは、この貪欲アルゴリズムの特徴付けをさらに一般化するためにグリードイドを導入しました。そのため、グリードイドという名前が付けられました。数理最適化に加えて、グリードイドはグラフ理論、言語理論、順序理論、その他の数学の分野にも関連付けられています。

定義

[編集]

集合系 ( 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\})}$

クラス

[編集]

グリードイドのほとんどのクラスは、集合体系、言語、半集合、単体複体などにおいて、同等の定義が多数存在します。以下では、よりよく知られている特徴付けをいくつか挙げるという伝統的な方法を用います。

区間グリードイド （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の頂点とし、 rを含む頂点部分集合のうちGの連結部分グラフを誘導するものを可能集合とする。これは頂点探索グリードイドと呼ばれ、反マトロイドの一種である。
• rを根とする有限有向グラフ D を考えます。基底集合を D の（有向）辺とし、実行可能集合をrを根とする各有向部分木の辺集合とし、すべての辺がrから離れる方向を向いているものとします。これは直線探索グリードイド、または有向分岐グリードイドと呼ばれます。これは区間グリードイドですが、反マトロイドでもマトロイドでもありません。
• m × n 行列 Mを考えます。基底集合E を1 からnまでの列のインデックスとし、実行可能集合をとします。これはガウス消去法のアルゴリズムの基礎となる構造であるため、ガウス消去法グリードイドと呼ばれます。これはグリードイドですが、区間グリードイドではありません。 $${\displaystyle F=\{X\subseteq E:{\text{ submatrix }}M_{\{1,\ldots ,|X|\},X}{\text{ is an invertible matrix}}\}.}$$

貪欲アルゴリズム

[編集]

一般的に、貪欲アルゴリズムとは、局所的に最良の選択肢（通常は最大重みの入力）を、利用可能な選択肢がすべて尽きるまで各ラウンドで選択する反復プロセスです。貪欲アルゴリズムが最適となる（つまり、最大値の基底を得る）という貪欲に基づく条件を記述するためには、貪欲理論におけるより一般的な用語が必要になります。一般性を損なうことなく、 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互換線形目的関数に最適です。

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

参照

[編集]

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

参考文献

[編集]

1. アクセス可能性の特性は、独立集合のすべての部分集合が独立であることを要求するマトロイドの遺伝的特性よりも厳密に弱いことに注意してください。
2. Björner, Anders ; Ziegler, Günter M. (1992)、「8. グリードイド入門」、White, Neil (ed.)、『マトロイド応用』、Encyclopedia of Mathematics and its Applications、第40巻、ケンブリッジ：ケンブリッジ大学出版局、pp.  284–357、doi : 10.1017/CBO9780511662041.009、ISBN 0-521-38165-7、MR  1165537、Zbl  0772.05026

• Björner, Anders ; Ziegler, Günter M. (1992)、「8. greedoids 入門」、White, Neil (ed.)、『Matroid Applications』、Encyclopedia of Mathematics and its Applications、第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 (編)、『計算理論の基礎：1981年国際FCT会議の議事録』、ハンガリー、セゲド、1981年8月24～28日、Lecture Notes in Computer Science、第117巻、ベルリン：Springer-Verlag、pp.  205～ 209、doi：10.1007/3-540-10854-8_22、ISBN 978-3-540-10854-2、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年3月4日アーカイブ- Wayback Machine
• 劣モジュラ関数と最適化
• マッチング、マトロイド、劣モジュラー関数

Retrieved from "https://en.wikipedia.org/w/index.php?title=Greedoid&oldid=1289693578"

• This page was last edited on 10 May 2025, at 07:06 (UTC).
• テキストはクリエイティブ・コモンズ 表示-継承4.0ライセンスの下で利用可能です。追加の条件が適用される場合があります。このサイトを利用することにより、利用規約とプライバシーポリシーに同意したことになります。Wikipedia®は、非営利団体であるウィキメディア財団の登録商標です。

• プライバシーポリシー
• Wikipediaについて
• 免責事項
• Wikipediaへのお問い合わせ
• 法的および安全に関する連絡先
• 行動規範
• 開発者
• 統計
• クッキーに関する声明
• モバイルビュー

• 
• 

検索

検索

目次を切り替える

貪欲な

2つの言語トピックを追加

Set system used in greedy optimization

組合せ論において、グリードイドは集合系の一種です。これはマトロイドの概念に由来します。マトロイドは、1935年にホイットニーによって平面グラフの研究のために最初に導入され、後にエドモンズによって、貪欲アルゴリズムによって解ける最適化問題のクラスを特徴付けるために使用されました。1980年頃、コルテとロヴァースは、この貪欲アルゴリズムの特徴付けをさらに一般化するためにグリードイドを導入しました。そのため、グリードイドという名前が付けられました。数理最適化に加えて、グリードイドはグラフ理論、言語理論、順序理論、その他の数学の分野にも関連付けられています。

定義

集合系 ( 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\})}$

クラス

グリードイドのほとんどのクラスは、集合体系、言語、半集合、単体複体などにおいて、同等の定義が多数存在します。以下では、よりよく知られている特徴付けをいくつか挙げるという伝統的な方法を用います。

区間グリードイド （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の頂点とし、 rを含む頂点部分集合のうちGの連結部分グラフを誘導するものを可能集合とする。これは頂点探索グリードイドと呼ばれ、反マトロイドの一種である。
• rを根とする有限有向グラフ D を考えます。基底集合を D の（有向）辺とし、実行可能集合をrを根とする各有向部分木の辺集合とし、すべての辺がrから離れる方向を向いているものとします。これは直線探索グリードイド、または有向分岐グリードイドと呼ばれます。これは区間グリードイドですが、反マトロイドでもマトロイドでもありません。
• m × n 行列 Mを考えます。基底集合E を1 からnまでの列のインデックスとし、実行可能集合をとします。これはガウス消去法のアルゴリズムの基礎となる構造であるため、ガウス消去法グリードイドと呼ばれます。これはグリードイドですが、区間グリードイドではありません。 $${\displaystyle F=\{X\subseteq E:{\text{ submatrix }}M_{\{1,\ldots ,|X|\},X}{\text{ is an invertible matrix}}\}.}$$

貪欲アルゴリズム

一般的に、貪欲アルゴリズムとは、局所的に最良の選択肢（通常は最大重みの入力）を、利用可能な選択肢がすべて尽きるまで各ラウンドで選択する反復プロセスです。貪欲アルゴリズムが最適となる（つまり、最大値の基底を得る）という貪欲に基づく条件を記述するためには、貪欲理論におけるより一般的な用語が必要になります。一般性を損なうことなく、 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互換線形目的関数に最適です。

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

参照

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

参考文献

1. アクセス可能性の特性は、独立集合のすべての部分集合が独立であることを要求するマトロイドの遺伝的特性よりも厳密に弱いことに注意してください。
2. Björner, Anders ; Ziegler, Günter M. (1992)、「8. グリードイド入門」、White, Neil (編)、『マトロイド応用』、Encyclopedia of Mathematics and its Applications、第40巻、ケンブリッジ：ケンブリッジ大学出版局、pp. 284–357、doi :10.1017/CBO9780511662041.009、ISBN 0-521-38165-7、MR  1165537、Zbl  0772.05026

• Björner, Anders ; Ziegler, Günter M. (1992)、「8. グリードイド入門」、White, Neil (編)、『マトロイド応用』、Encyclopedia of Mathematics and its Applications、第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 (編)、『計算理論の基礎：1981年国際FCT会議の議事録』（ハンガリー、セゲド、1981年8月24～28日）、Lecture Notes in Computer Science、第117巻、ベルリン：Springer-Verlag、pp.  205～ 209、doi :10.1007/3-540-10854-8_22、ISBN 978-3-540-10854-2、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年3月4日アーカイブ - Wayback Machine
• 劣モジュラ関数と最適化
• マッチング、マトロイド、劣モジュラー関数

Retrieved from "https://en.wikipedia.org/w/index.php?title=Greedoid&oldid=1289693578"

Original text

Rate this translation

Your feedback will be used to help improve Google Translate