グリードイドのソースを表示

'''グリードイド'''（{{Lang-en-short|greedoid}}）は、ある[[公理]]を満たす[[集合]]とその[[冪集合|べき集合]]の部分集合の組である。[[マトロイド]]と[[反マトロイド]]の一般化であり、マトロイド同様に貪欲法を考えることができる。

== 定義 ==
有限集合 <math>E</math> とその部分集合族 <math>F \subseteq 2^E</math> の組 <math>(E, F)</math> が
*('''A1''') <math>\emptyset\in{F}</math>
*('''A3''') <math>X, Y \in F,\ |X|>|Y| \Rightarrow \exists\ x \in X \setminus Y \text{ s.t. } Y \cup \{x\} \in F.</math>
を満たすとき、'''グリードイド'''と呼ぶ<ref group="注">採番については[[マトロイド]]と平仄を合わせた。</ref>。

== 例 ==
G を[[グラフ (データ構造)|グラフ]]<ref group="注">有向、無向どちらでもよい</ref>、G のある頂点を<math>r\in V(G)</math>とする。E=E(G)、F を r を根とするグラフ G の（全点でなくともよい）すべての木とする。このとき、(E,F) はグリードイドであり、G の'''根付き森グリードイド'''（branching greedoid）と呼ぶ。根付き森グリードイドは、グリードイドであるが、マトロイドではない。実際、r を含む森の部分森が必ずしも r を含むとは限らないことは明らかである。

== 関連する概念 ==
有限集合 <math>E</math> とその部分集合族 <math>F \subseteq 2^E</math> の組 <math>(E, F)</math> が ('''A1''') および
*('''A4''') 任意の <math>X \in F \setminus \{\emptyset\}</math> に対して <math>X \setminus \{x\} \in F</math> となる <math>x \in X</math> が存在する。
を満たすとき、'''アクセス可能'''（accessible）であると呼ぶ。グリードイドはアクセス可能である。

また、('''A1''')、('''A4''') および
*('''A5''') F は和集合のもとで閉じている。
を満たすとき（つまり、アクセス可能で、和集合のもとで閉じているとき）、'''反マトロイド'''（antimatroid）と呼ぶ。反マトロイドはグリードイドである。

== グリードイドに対する貪欲法 ==
マトロイドと同様に、グリードイドに対しても貪欲法を適用できる。ただし、マトロイドと異なり、常に最適解が得られるとは限らず、一般には[[NP困難]]である。グリードイド (E,F) が、強交換性という性質を持つことが貪欲法で最適解を得られる必要十分条件である。

=== 問題設定とアルゴリズム ===
グリードイドに対する最適化問題は次のように定式化できる。

* 入力 : グリードイド (E,F)<ref group="注">任意の<math>X\subseteq E</math>に対して<math>X\in F</math>かどうかを判定するオラクルが与えられているものとする。</ref> と重み関数 <math>c:2^E \to \mathbb{R}</math>
* 出力 : <math>X \in F</math> かつ c(X) が最大となるような X を求める。

グリードイドに対する貪欲法は、次のようなアルゴリズムである。

# <math>E_{ans} := \emptyset</math>
# <math>E_{ans} \cup \{e\} \in F</math> となるような <math>e \in E \setminus E_{ans}</math> が存在しない場合は、<math>E_{ans}</math>を出力し終了する。
# 上記の条件を満たす e の中で <math>c(E_{ans} \cup \{e\})</math> が最大となる e を見つける。
# <math>E_{ans} := E_{ans} \cup \{e\}</math>として、2に戻る。

なお、マトロイドに対する上記アルゴリズムは[[マトロイド#最良選択貪欲法|最良選択貪欲法]]に一致し、無向根付き森グリードイドに対する上記アルゴリズムは[[プリム法]]に一致する（つまり、根付きグリードイドに対する貪欲法は最適解を出力する）。

=== 強交換性 ===
グリードイド (E,F) が次を満たすとき、強交換性を持つという。
: 任意の <math>A \in F</math> について、B は <math>A \subseteq B</math> を満たす任意の極大元とする。このとき、<math>A \cup \{x\} \in F</math> を満たす任意の <math>x \in E \setminus B</math> に対して、<math>A \cup \{y\} \in F</math> と <math>(B \setminus \{y\}) \cup \{x\} \in F</math> を同時に満たす <math>y \in B \setminus A</math> が存在する。

グリードイド (E,F) が強交換性を持つとき、かつそのときのみ、すべてのモジュラーな重み関数 <math>c:2^E \to \mathbb{R}_+</math> でグリードイドに対する貪欲法は最適解を出力することが知られている。

=== NP困難性 ===
一般のグリードイド上での最適化問題はNP困難である。事実、[[頂点被覆#計算問題|頂点被覆問題]]はグリードイド上での最適化問題に帰着できる。

==脚注==
{{脚注ヘルプ}}
===注釈===
{{Reflist|group="注"}}

==参考文献==
*{{Cite book |和書 |author=B.コルテ |coauthors=J.フィーゲン |others=浅野孝夫,平田富夫,小野孝男,浅野泰仁訳 |title=組合せ最適化-理論とアルゴリズム |edition=第2版 |date=2012-2-29 |publisher=シュプリンガー・ジャパン |isbn=978-4621062029 }}

==関連項目==
===分野===
*[[組合せ最適化]]
*[[グラフ理論]]
*[[計算複雑性理論]]
===数学的対象===
*[[ポリマトロイド]]
*[[マトロイド]]
*[[劣モジュラ関数]]

{{DEFAULTSORT:くりいといと}}
[[Category:マトロイド理論]]
[[Category:組合せ最適化]]
[[Category:組合せ論]]
[[Category:最適化]]
[[Category:オペレーションズリサーチ]]
[[Category:計算複雑性理論]]
[[Category:数学に関する記事]]