グリードイド
グリードイドに対する最適化問題は次のように定式化できる。
入力 : グリードイド(E,F) と重み関数 c : 2 E → R {\displaystyle c:2^{E}\to \mathbb {R} }
出力 : X ∈ F {\displaystyle X\in F} かつ c(X)が最大となるようなXを求める。
グリードイドに対する貪欲法は、次のようなアルゴリズムである。
E a n s := ∅ {\displaystyle E_{ans}:=\emptyset }
E a n s ∪ { e } ∈ F {\displaystyle E_{ans}\cup \{e\}\in F} となるような e ∈ E ∖ E a n s {\displaystyle e\in E\setminus E_{ans}} が存在しない場合は、 E a n s {\displaystyle E_{ans}} を出力し終了する。
上記の条件を満たすeの中で c ( E a n s ∪ { e } ) {\displaystyle c(E_{ans}\cup \{e\})} が最大となるeを見つける。
E a n s := E a n s ∪ { e } {\displaystyle E_{ans}:=E_{ans}\cup \{e\}} として、2に戻る。
なお、マトロイドに対する上記アルゴリズムは最良選択貪欲法に一致し、無向根付き森グリードイドに対する上記アルゴリズムはプリム法に一致する(つまり、根付きグリードイドに対する貪欲法は最適解を出力する)。
一般のグリードイド上での最適化問題はNP-困難である。事実、頂点被覆問題は、グリードイド上での最適化問題に帰着できる。