最悪棄却貪欲法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/07 04:53 UTC 版)
独立性システム (E,F) とコスト関数 c : E → R + {\displaystyle c:E\to \mathbb {R} _{+}} に対する最小化問題を解く。最悪棄却貪欲法は、都合の悪い e∈E を優先して解から除外する。つまり、 c ( e 1 ) ≥ c ( e 2 ) ≥ ⋯ ≥ c ( e n ) {\displaystyle c(e_{1})\geq c(e_{2})\geq \cdots \geq c(e_{n})} となるように E = { e 1 , e 2 , ⋯ , e n } {\displaystyle E=\{e_{1},e_{2},\cdots ,e_{n}\}} をソートする。 E a n s ← E {\displaystyle E_{ans}\leftarrow E} For i = 1 to n : E a n s ∖ { e i } {\displaystyle E_{ans}\setminus \{e_{i}\}} が基を含むならば、 E a n s ← E a n s ∖ { e i } {\displaystyle E_{ans}\leftarrow E_{ans}\setminus \{e_{i}\}} E a n s {\displaystyle E_{ans}} を解として出力する。 というアルゴリズムである。 最悪棄却貪欲法で得られる解のコストを c(G) 、最適解のコストを c(OPT) とすると、ランク商 q(E,F) 、双対な独立性システム(E,F*)の下方ランク関数ρ*、ランク関数r*を使って 1 ≤ c ( G ) c ( O P T ) ≤ max X ⊆ E | X | − ρ ∗ ( X ) | X | − r ∗ ( X ) {\displaystyle 1\leq {\frac {c(G)}{c(OPT)}}\leq \max _{X\subseteq {E}}{\frac {|X|-\rho ^{*}(X)}{|X|-r^{*}(X)}}} と書ける。マトロイドならばρ*=r*なので、常に最適解を得られることが分かる。
※この「最悪棄却貪欲法」の解説は、「マトロイド」の解説の一部です。
「最悪棄却貪欲法」を含む「マトロイド」の記事については、「マトロイド」の概要を参照ください。
- 最悪棄却貪欲法のページへのリンク
