グリードイドに対する貪欲法

ウィキペディア小見出し辞書

グリードイドに対する貪欲法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/08/16 07:57 UTC 版)

「グリードイド」の記事における「グリードイドに対する貪欲法」の解説

マトロイドと同様に、グリードイドに対しても貪欲法を適用できる。ただし、マトロイドと異なり、常に最適解が得られるとは限らず、一般にはNP困難である。グリードイド(E,F)が、強交換性という性質を持つことが貪欲法で最適解を得られる必要十分条件である。