【東京大学】【優】欲張り法、分岐限定法の比較と考察
数理計画と最適化最終レポート
欲張り法、分岐限定法の比較と考察
欲張り法とは、「解を段階的に構築していく際に,常にその時点で最善であると思われるものを取り入れていく」方法である。つまり「その時点での最善の解の集合体としての最適解」を目的とする方法である。もちろん、単純かつ明快なこの方法では,問題の大域的最適解を求めることは難しい.それでも、ある種の問題に対して能率よく最適解(局所的最適解)を得られる。欲張り法をいた例としては最小木問題が挙げられる。最小木問題とは無向グラフの各枝の長さが与えられているとき、全節点を連結する木で、枝の長さの和が最小のものを見つける問題である。こ...