貪欲法
貪欲法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/07 04:53 UTC 版)
マトロイドにおいては貪欲法で最適解が得られることを示す。なお、マトロイドの貪欲法は組合せ最適化の貪欲法の全てを網羅しているわけではない。たとえば、クラスカル法はマトロイド上の貪欲法で説明できるが、プリム法やダイクストラ法は異なる。
※この「貪欲法」の解説は、「マトロイド」の解説の一部です。
「貪欲法」を含む「マトロイド」の記事については、「マトロイド」の概要を参照ください。
貪欲法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/28 01:04 UTC 版)
貪欲法は動的計画法に似ているが、部分問題の解を各段階では知る必要がないという点が異なる。その代わりに、各時点で最もよい選択と思われるものを選んでいく。貪欲法では、それまでの選択と現時点の局所最適解から最適と思われる解を構築していくのであって、考えられるあらゆる解を評価することはない。したがって網羅的ではなく、必ずしも正解にたどり着けるわけではない。しかし、性能は非常によい。貪欲法としてよく知られている例として、最短経路木を求めるクラスカル法、プリム法、ダイクストラ法などがある。
※この「貪欲法」の解説は、「アルゴリズム」の解説の一部です。
「貪欲法」を含む「アルゴリズム」の記事については、「アルゴリズム」の概要を参照ください。
ウィキペディア小見出し辞書の「貪欲法」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 貪欲法のページへのリンク
