グリードイド

有限集合 ${\displaystyle E}$ とその部分集合族 ${\displaystyle F\subseteq 2^{E}}$ の組 ${\displaystyle (E,F)}$ が

• (A1) ${\displaystyle \emptyset \in {F}}$
• (A3) ${\displaystyle X,Y\in F,\ |X|>|Y|\Rightarrow \exists \ x\in X\setminus Y{\text{ s.t. }}Y\cup \{x\}\in F.}$

を満たすとき、グリードイドと呼ぶ^{[注 1]}。

G をグラフ^{[注 2]}、G のある頂点を${\displaystyle r\in V(G)}$とする。E=E(G)、F を r を根とするグラフ G の（全点でなくともよい）すべての木とする。このとき、(E,F) はグリードイドであり、G の根付き森グリードイド（branching greedoid）と呼ぶ。根付き森グリードイドは、グリードイドであるが、マトロイドではない。実際、r を含む森の部分森が必ずしも r を含むとは限らないことは明らかである。

有限集合 ${\displaystyle E}$ とその部分集合族 ${\displaystyle F\subseteq 2^{E}}$ の組 ${\displaystyle (E,F)}$ が (A1) および

• (A4) 任意の ${\displaystyle X\in F\setminus \{\emptyset \}}$ に対して ${\displaystyle X\setminus \{x\}\in F}$ となる ${\displaystyle x\in X}$ が存在する。

を満たすとき、アクセス可能（accessible）であると呼ぶ。グリードイドはアクセス可能である。

また、(A1)、(A4) および

• (A5) F は和集合のもとで閉じている。

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

Summarize Timeline Fact Check

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

グリードイドに対する最適化問題は次のように定式化できる。

• 入力 : グリードイド (E,F)^{[注 3]} と重み関数 ${\displaystyle c:2^{E}\to \mathbb {R} }$
• 出力 : ${\displaystyle X\in F}$ かつ c(X) が最大となるような X を求める。

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

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

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

グリードイド (E,F) が次を満たすとき、強交換性を持つという。

任意の ${\displaystyle A\in F}$ について、B は ${\displaystyle A\subseteq B}$ を満たす任意の極大元とする。このとき、${\displaystyle A\cup \{x\}\in F}$ を満たす任意の ${\displaystyle x\in E\setminus B}$ に対して、${\displaystyle A\cup \{y\}\in F}$ と ${\displaystyle (B\setminus \{y\})\cup \{x\}\in F}$ を同時に満たす ${\displaystyle y\in B\setminus A}$ が存在する。

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

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