問題設定とアルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/08/16 07:57 UTC 版)
「グリードイド」の記事における「問題設定とアルゴリズム」の解説
グリードイドに対する最適化問題は次のように定式化できる。 入力 : グリードイド(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に戻る。 なお、マトロイドに対する上記アルゴリズムは最良選択貪欲法に一致し、無向根付き森グリードイドに対する上記アルゴリズムはプリム法に一致する(つまり、根付きグリードイドに対する貪欲法は最適解を出力する)。
※この「問題設定とアルゴリズム」の解説は、「グリードイド」の解説の一部です。
「問題設定とアルゴリズム」を含む「グリードイド」の記事については、「グリードイド」の概要を参照ください。
- 問題設定とアルゴリズムのページへのリンク
