グリードイド

グリードイド（テンプレート:Lang-en-short）は、ある公理を満たす集合とそのべき集合の部分集合の組である。マトロイドと反マトロイドの一般化であり、マトロイド同様に貪欲法を考えることができる。

定義

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

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

を満たすとき、グリードイドと呼ぶ。

例

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

関連する概念

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

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

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

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

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

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

グリードイドに対する貪欲法

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

問題設定とアルゴリズム

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

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

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

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

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

強交換性

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

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

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

NP困難性

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

参考文献

• テンプレート:Cite book

関連項目

分野

• 組合せ最適化
• グラフ理論
• 計算複雑性理論

数学的対象

• ポリマトロイド
• マトロイド
• 劣モジュラ関数