グリードイド

グリードイド("greedoid")は、ある公理を満たす集合とそのべき集合の部分集合の組である。マトロイドと反マトロイドの一般化であり、マトロイド同様に貪欲法を考えることができる。
定義.
有限集合 formula_1 とその部分集合族 formula_2 の組 formula_3 が
を満たすとき、グリードイドと呼ぶ。
例.
Gをグラフ、Gのある頂点をformula_6とする。E=E(G)、Fをrを根とするグラフGの(全点でなくともよい)すべての木とする。このとき、(E,F)はグリードイドであり、Gの根付き森グリードイド("branching greedoid")と呼ぶ。根付き森グリードイドは、グリードイドであるが、マトロイドではない。実際、rを含む森の部分森が必ずしもrを含むとは限らないことは明らかである。
関連する概念.
有限集合 formula_1 とその部分集合族 formula_2 の組 formula_3 が(A1)および
を満たすとき、アクセス可能("accessible")であると呼ぶ。グリードイドはアクセス可能である。
また、(A1)、(A4)および
を満たすとき(つまり、アクセス可能で、和集合のもとで閉じているとき)、反マトロイド("antimatroid")と呼ぶ。反マトロイドはグリードイドである。
グリードイドに対する貪欲法.
マトロイドと同様に、グリードイドに対しても貪欲法を適用できる。ただし、マトロイドと異なり、常に最適解が得られるとは限らず、一般にはNP困難である。グリードイド(E,F)が、強交換性という性質を持つことが貪欲法で最適解を得られる必要十分条件である。
問題設定とアルゴリズム.
グリードイドに対する最適化問題は次のように定式化できる。
グリードイドに対する貪欲法は、次のようなアルゴリズムである。
なお、マトロイドに対する上記アルゴリズムは最良選択貪欲法に一致し、無向根付き森グリードイドに対する上記アルゴリズムはプリム法に一致する(つまり、根付きグリードイドに対する貪欲法は最適解を出力する)。
強交換性.
グリードイド(E,F)が次を満たすとき、強交換性を持つという。
グリードイド(E,F)が強交換性を持つとき、かつそのときのみ、すべてのモジュラーな重み関数 formula_28 でグリードイドに対する貪欲法は最適解を出力することが知られている。
NP-困難性.
一般のグリードイド上での最適化問題はNP-困難である。事実、頂点被覆問題は、グリードイド上での最適化問題に帰着できる。