グリードイド

グリードイド(greedoid)は、ある公理を満たす集合とそのべき集合の部分集合の組である。マトロイドと反マトロイドの一般化であり、マトロイド同様に貪欲法を考えることができる。

定義

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

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

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

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

問題設定とアルゴリズム

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

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

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

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