グリードイド

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

定義
有限集合  とその部分集合族  の組  が
(A1) 
(A3) 
を満たすとき、グリードイドと呼ぶ。

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

関連する概念
有限集合  とその部分集合族  の組  が(A1)および
(A4) 任意の  に対して  となる  が存在する。
を満たすとき、アクセス可能(accessible)であると呼ぶ。グリードイドはアクセス可能である。

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

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

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

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

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

 
 となるような が存在しない場合は、を出力し終了する。
 上記の条件を満たすeの中でが最大となるeを見つける。
 として、2に戻る。

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

強交換性
グリードイド(E,F)が次を満たすとき、強交換性を持つという。
 任意の  について、Bは  を満たす任意の極大元とする。このとき、 を満たす任意の  に対して、  と  を同時に満たす  が存在する。

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

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

脚注

注釈

参考文献

関連項目

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

数学的対象
ポリマトロイド
マトロイド
劣モジュラ関数

マトロイド理論
組合せ最適化
組合せ論
最適化
オペレーションズリサーチ
計算複雑性理論
数学に関する記事