貪欲法 — Termwire

各時点で一番良さそうな選択を積み重ねていく、シンプルな問題の解き方。

将来のことまで見通して最適な選択をするのではなく、今この瞬間に一番得だと思える選択をただ繰り返していく。常に最良の答えが出せるとは限らないが、シンプルで高速に計算できるのが利点。

おつりの計算で大きい硬貨から使っていく考え方などが、身近な貪欲法の例としてよく紹介される。