資料紹介
【東京大学】【優】欲張り法、分岐限定法の比較と考察
All rights reserved.
【ご注意】該当資料の情報及び掲載内容の不法利用、無断転載・配布は著作権法違反となります。
資料の原本内容 ( この資料を購入すると、テキストデータがみえます。 )
数理計画と最適化最終レポート
欲張り法、分岐限定法の比較と考察
欲張り法とは、「解を段階的に構築していく際に，常にその時点で最善であると思われるものを取り入れていく」方法である。つまり「その時点での最善の解の集合体としての最適解」を目的とする方法である。もちろん、単純かつ明快なこの方法では，問題の大域的最適解を求めることは難しい．それでも、ある種の問題に対して能率よく最適解（局所的最適解）を得られる。欲張り法をいた例としては最小木問題が挙げられる。最小木問題とは無向グラフの各枝の長さが与えられているとき、全節点を連結する木で、枝の長さの和が最小のものを見つける問題である。こ...
