強交換性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/08/16 07:57 UTC 版)
グリードイド(E,F)が次を満たすとき、強交換性を持つという。 任意の A ∈ F {\displaystyle A\in F} について、Bは A ⊆ B {\displaystyle A\subseteq B} を満たす任意の極大元とする。このとき、 A ∪ { x } ∈ F {\displaystyle A\cup \{x\}\in F} を満たす任意の x ∈ E ∖ B {\displaystyle x\in E\setminus B} に対して、 A ∪ { y } ∈ F {\displaystyle A\cup \{y\}\in F} と ( B ∖ { y } ) ∪ { x } ∈ F {\displaystyle (B\setminus \{y\})\cup \{x\}\in F} を同時に満たす y ∈ B ∖ A {\displaystyle y\in B\setminus A} が存在する。 グリードイド(E,F)が強交換性を持つとき、かつそのときのみ、すべてのモジュラーな重み関数 c : 2 E → R + {\displaystyle c:2^{E}\to \mathbb {R} _{+}} でグリードイドに対する貪欲法は最適解を出力することが知られている。
※この「強交換性」の解説は、「グリードイド」の解説の一部です。
「強交換性」を含む「グリードイド」の記事については、「グリードイド」の概要を参照ください。
ウィキペディア小見出し辞書の「強交換性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 強交換性のページへのリンク
