出典: フリー百科事典『ウィキペディア(Wikipedia)』
グリードイド(greedoid)は、ある公理を満たす集合とそのべき集合の部分集合の組である。マトロイドと反マトロイドの一般化であり、マトロイド同様に貪欲法を考えることができる。
有限集合
とその部分集合族
の組
が
- (A1)
![{\displaystyle \emptyset \in {F}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f01fc612c077f1cda30d69bfd523ea4bb29a5947)
- (A3)
![{\displaystyle X,Y\in F,\ |X|>|Y|\Rightarrow \exists \ x\in X\setminus Y{\text{ s.t. }}Y\cup \{x\}\in F.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3285969b0467c9986322c089ef8d1a7cac555ab)
を満たすとき、グリードイドと呼ぶ。[注 1]
Gをグラフ[注 2]、Gのある頂点を
とする。E=E(G)、Fをrを根とするグラフGの(全点でなくともよい)すべての木とする。このとき、(E,F)はグリードイドであり、Gの根付き森グリードイド(branching greedoid)と呼ぶ。根付き森グリードイドは、グリードイドであるが、マトロイドではない。実際、rを含む森の部分森が必ずしもrを含むとは限らないことは明らかである。
関連する概念[編集]
有限集合
とその部分集合族
の組
が(A1)および
- (A4) 任意の
に対して
となる
が存在する。
を満たすとき、アクセス可能(accessible)であると呼ぶ。グリードイドはアクセス可能である。
また、(A1)、(A4)および
を満たすとき(つまり、アクセス可能で、和集合のもとで閉じているとき)、反マトロイド(antimatroid)と呼ぶ。反マトロイドはグリードイドである。
グリードイドに対する貪欲法[編集]
マトロイドと同様に、グリードイドに対しても貪欲法を適用できる。ただし、マトロイドと異なり、常に最適解が得られるとは限らず、一般にはNP困難である。グリードイド(E,F)が、強交換性という性質を持つことが貪欲法で最適解を得られる必要十分条件である。
問題設定とアルゴリズム[編集]
グリードイドに対する最適化問題は次のように定式化できる。
- 入力 : グリードイド(E,F)[注 3] と重み関数
![{\displaystyle c:2^{E}\to \mathbb {R} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8cca093d1dea73f8f1687ed05a4714c66fee65f)
- 出力 :
かつ c(X)が最大となるようなXを求める。
グリードイドに対する貪欲法は、次のようなアルゴリズムである。
![{\displaystyle E_{ans}:=\emptyset }](https://wikimedia.org/api/rest_v1/media/math/render/svg/2fa875606f0d3a015ae4c1e348fb398768afd600)
となるような
が存在しない場合は、
を出力し終了する。
- 上記の条件を満たすeの中で
が最大となるeを見つける。
として、2に戻る。
なお、マトロイドに対する上記アルゴリズムは最良選択貪欲法に一致し、無向根付き森グリードイドに対する上記アルゴリズムはプリム法に一致する(つまり、根付きグリードイドに対する貪欲法は最適解を出力する)。
強交換性[編集]
グリードイド(E,F)が次を満たすとき、強交換性を持つという。
- 任意の
について、Bは
を満たす任意の極大元とする。このとき、
を満たす任意の
に対して、
と
を同時に満たす
が存在する。
グリードイド(E,F)が強交換性を持つとき、かつそのときのみ、すべてのモジュラーな重み関数
でグリードイドに対する貪欲法は最適解を出力することが知られている。
NP-困難性[編集]
一般のグリードイド上での最適化問題はNP-困難である。事実、頂点被覆問題は、グリードイド上での最適化問題に帰着できる。
- ^ 採番についてはマトロイドと平仄を合わせた。
- ^ 有向、無向どちらでもよい
- ^ 任意の
に対して
かどうかを判定するオラクルが与えられているものとする。
参考文献[編集]
- B.コルテ、J.フィーゲン『組合せ最適化-理論とアルゴリズム』浅野孝夫,平田富夫,小野孝男,浅野泰仁訳(第2版)、シュプリンガー・ジャパン、2012年2月29日。ISBN 978-4621062029。
関連項目[編集]
数学的対象[編集]