最良選択貪欲法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/07 04:53 UTC 版)
最良選択貪欲法は、 c ( e ) {\displaystyle c(e)} の大きい順に e ∈ E {\displaystyle e\in 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 ← ∅ {\displaystyle E_{ans}\leftarrow \emptyset } For i = 1 to n : E a n s ∪ { e i } ∈ F {\displaystyle E_{ans}\cup \{e_{i}\}\in F} ならば E a n s ← E a n s ∪ { e i } {\displaystyle E_{ans}\leftarrow E_{ans}\cup \{e_{i}\}} E a n s {\displaystyle E_{ans}} を解として出力する。 というアルゴリズムである。 最良選択貪欲法で得られる解のコストを c ( G ) {\displaystyle c(G)} 、最適解のコストを c ( O P T ) {\displaystyle c(OPT)} とすると、ランク商 q ( E , F ) {\displaystyle q(E,F)} を使って q ( E , F ) ≤ c ( G ) c ( O P T ) ≤ 1 {\displaystyle q(E,F)\leq {\frac {c(G)}{c(OPT)}}\leq 1} が任意のコスト関数に対して成立する。マトロイドのランク商は1なので、マトロイドである最大化問題は最良選択貪欲法によって最適解を得られる。これは逆も言えるので、独立性システム(E,F)がマトロイドであるための必要十分条件は最良選択貪欲法で全ての c : E → R + {\displaystyle c:E\to \mathbb {R} _{+}} に対して最大化問題の最適解を求めることができることである。これを Edmonds-Rado 定理という。
※この「最良選択貪欲法」の解説は、「マトロイド」の解説の一部です。
「最良選択貪欲法」を含む「マトロイド」の記事については、「マトロイド」の概要を参照ください。
- 最良選択貪欲法のページへのリンク
