仕事に効くコンピュータサイエンス
大きい問題を小さく割る — アルゴリズム設計読了目安 10分

目先の最善を選び続ける — 貪欲法の便利さと罠

問い合わせ対応の一覧に、五分で終わりそうな案件と、調査に半日かかりそうな案件が混ざって並んでいます。件数は減らしたいし、重要な案件も見落としたくありません。どちらから手をつけるべきでしょうか。じっくり全体の優先度を計算する時間はなく、その場で判断しなければなりません。このページの問いは、目先の判断を積み重ねるやり方が、いつ機能し、いつ機能しないかです。

貪欲法とは何か

貪欲法とは、いま選べる選択肢の中から、その時点で一番良さそうなものを選び、それを繰り返していくことで答えに近づく考え方です。全体を見渡してから最善の組み合わせを探すのではなく、各段階での最善だけを積み重ねます。この方法の一番の魅力は速さです。全体の組み合わせを比較する必要がないため、判断にかかる時間が短く済みます。

一方で、貪欲法には弱点もあります。各段階で最善に見えた選択が、あとから振り返ると全体の最善ではなかった、ということが起こり得ます。たとえば手持ちの小銭で特定の金額をできるだけ少ない枚数で支払おうとするとき、常に一番大きい硬貨から使っていく方法は、多くの通貨の組み合わせではうまくいきますが、硬貨の額面の組み合わせによっては、もっと少ない枚数で払える組み合わせを見逃すことがあります。貪欲法が全体の最善にたどり着けるかどうかは、問題の構造次第だという点は覚えておく必要があります。構造を厳密に見極めなくても、まずは「速さを取りに行っている」という自覚を持っておくだけで、あとから結果を振り返るときの姿勢が変わります。

この性質は、仕事の判断にそのまま当てはまります。貪欲法が全体の最善と一致する場面もあれば、一致しない場面もあります。厄介なのは、事前にどちらの場面かを完全に見分ける簡単な方法がないことです。だからこそ、貪欲法を使うときは「速さを取る代わりに、全体の最善は保証されない」という前提を持っておくことが重要になります。速さと確実さのどちらを優先するかを、場面ごとに意識して選ぶ必要があります。

仕事の言葉に訳すと

仕事の場面では、貪欲法は「目の前の選択肢の中から、いま一番効果が高そうなもの、あるいはいま一番早く終わりそうなものを選び、それを繰り返す」という進め方に翻訳できます。全体の計画を綿密に立てる時間がないとき、あるいは状況が刻々と変わり計画を立ててもすぐ崩れるときに、貪欲法は現実的な選択になります。

貪欲法の値打ちは、判断そのものにかかる時間を減らせる点にあります。五件の依頼が来たときに、優先順位の計算に十分かけるくらいなら、単純な基準をひとつ決めて機械的に処理したほうが、全体として速く進むことが少なくありません。ただしこれは「何も考えずに手当たり次第に処理する」こととは違います。貪欲法は、選ぶための基準をひとつはっきり決めたうえで、それに従い続けるという規律のある進め方です。

基準の決め方にも種類があります。「早く終わるものを優先する」という基準は、対応件数を早く減らしたいときに向いています。「影響が大きいものを優先する」という基準は、少数の重要な案件を早めに片付けたいときに向いています。どちらの基準も貪欲法ですが、選ぶ基準によって結果として片付く仕事の顔ぶれがまったく変わります。基準を決めずに「なんとなく効果が高そうなもの」で選び続けると、その日の気分によって基準がぶれ、あとから振り返って一貫性のない進め方になっていたということが起こります。

具体的な場面で見る

貪欲法の進み方を図にすると、次のようになります。毎回、その時点で並んでいる選択肢の中から一番良さそうなものだけを選び、選んだら次の段階に進みます。全体を見渡す動作は、どの段階にも登場しません。

選択肢A・B・C 最善を選ぶ 選択肢D・E 最善を選ぶ 結果

各段階は、その前後の段階を振り返らずに完結します。この「振り返らない」という単純さが、貪欲法の速さの源であり、同時に全体最適を見落とす原因にもなります。

まず問い合わせ対応です。届いた順ではなく「一番早く終わりそうなものから片付ける」という基準を採用すると、未対応の件数が早いペースで減っていきます。件数そのものを減らすことを重視する場面、たとえば月末の対応件数を報告する場面などでは、この基準が効果的です。ただし、この基準だけに頼ると、対応に時間はかかるが影響の大きい案件が後回しになり続ける危険があります。この点はあとの落とし穴で扱います。

次に、経費精算や小さな事務作業の片付け方です。まとまった作業時間が取れないとき、すぐ終わる作業から順に消化していくと、未処理のリストが目に見えて短くなっていきます。心理的な負担が減るという効果に加えて、残ったリストが本当に手間のかかる作業だけになるため、次にまとまった時間を確保したときに何に取り組むべきかが明確になります。細切れの時間しか取れない日ほど、この基準は使い勝手が良くなります。まとまった時間が取れる日には、あえて残しておいた手間のかかる作業に集中するという使い分けもできます。

三つめは、会議のスロット調整です。参加予定者の予定を全員分同時にすり合わせようとすると、調整の組み合わせが増えて時間がかかります。代わりに、予定が確定しやすい人から順にスロットを仮決めしていき、残りの人をそのスロットに合わせてもらう、という進め方を取ることがあります。早く決まる人から確定させるという貪欲な基準によって、調整全体が前に進みやすくなります。

ただしこの場面でも、基準の選び方次第で結果は変わります。「予定が確定しやすい人」を優先する基準の代わりに、「その会議に絶対必要な人」を優先する基準を使うこともできます。前者は調整のスピードを優先し、後者は会議の質を優先します。どちらも貪欲法ですが、どちらの基準を採用するかは、その会議で何を大事にしたいかによって決めるべきものです。基準を決めずに調整を始めると、途中で優先順位が揺れ、結局すり合わせに時間がかかってしまいます。

落とし穴 — 目先の最善が全体を壊すとき

貪欲法の一番の落とし穴は、目先の選択を積み重ねた結果、重要だが着手しにくい仕事がいつまでも先送りされることです。「すぐ終わる案件から片付ける」という基準を無条件に使い続けると、時間のかかる重要な案件は毎回リストの最後に回され、締切の直前になって初めて着手する、という事態が起こります。これは基準そのものが悪いのではなく、基準を状況に応じて見直さずに使い続けたことが原因です。

もうひとつの落とし穴は、貪欲法が効かない構造の問題にまで適用してしまうことです。貪欲法が全体の最善に近づけるのは、ある段階での選択が、あとの段階の選べる幅を狭めない場合に限られます。たとえば人員を複数のプロジェクトに割り振る場面で、目先の忙しさだけを基準に一人ずつ割り振っていくと、後半になって「この人がいれば解決したのに、先に他へ割り振ってしまった」という組み合わせの悪さに気づくことがあります。このような場面では、貪欲法よりも、あとで見る動的計画法のように、複数の組み合わせを比較しながら決める考え方のほうが適しています。

貪欲法を安全に使うための目安は、「この選択をあとで後悔したときに、簡単にやり直せるか」です。やり直しがきく場面では貪欲法の速さが活きます。やり直しがきかない、あるいはやり直しの代償が大きい場面では、いったん立ち止まって選択肢全体を見渡す価値があります。

見分け方をもう一段具体的にすると、「この選択によって、次の選択肢が広がるか狭まるか」を自問する方法があります。狭まる一方であれば、貪欲な選び方は徐々に選択の自由を失わせていきます。逆に、選んでも次の選択肢がほとんど変わらないなら、貪欲法を使って速さを優先しても大きな損失にはなりません。

持ち帰り

  • 貪欲法は、各段階での最善を積み重ねて答えに近づく、速さを重視した考え方です。
  • 基準をひとつ決めて従い続けることで、判断そのものにかかる時間を減らせます。
  • 重要だが着手しにくい仕事を先送りし続けていないか、基準を定期的に見直す必要があります。

やってみる

今抱えているタスクの一覧に「一番早く終わるものから片付ける」という基準を一度当ててみて、そのままだと先送りされ続けている仕事がないか、リストの下のほうまで目を通して確認してください。