欲張り法・貪欲法

greedy-method.png

別名最良優先探索(Best-first search)
幅優先探索で、何らかの規則に従って、次は最も良いノードを選択する。
幅優先探索+αってかんじ。
幅優先探索の、探索の順序を工夫したに過ぎない。
解を探索する過程で全体的な最適性を考えて網羅的に探索するのではなく、
局所的に最も良いと思われる方向へのみ探索を進める。
網羅的な探索ではないので一般的には最適解を得る保証はないが、
計算時間を大幅に短くできる他、
多くの場合にかなり最適解に近い解を得ることができるので、
実際にはよく使われる方法である。
問題の種類によっては、欲張り法によって最適解が得られることが保証されているということも多い。
全探索動的計画法が、複数の場合を考えた上での最善を調べるのに対し、
貪欲法のアルゴリズムは1つのルールに従って「その場での最善」を選択することを繰り返します。
つまり、貪欲法は全探索や動的計画法よりも簡単で取り組みやすいのです。

TopCoderで貪欲法の問題

簡単な順に並べます

  • SkiResortEasy….スキーリゾートの工事費を最も安くするにはどうしたらいいか?という問題。
  • TheSquareDivTwo….問題文を理解するのがむずかった。
  • CostOfDancing….一見難しい探索に思えるが、やり方がわかると簡単。

サポートサイト Wikidot.com