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

小さく割って、賢く選んで、やめ時を決める

この章では、大きい問題を小さくするための四つの型を見てきました。分割統治、貪欲法、動的計画法、探索と枝刈りです。このページの問いは、目の前の問題に出会ったとき、四つのうちどれを選べばよいか、です。型を知っているだけでは足りず、使い分けができて初めて仕事に効きます。

四つの型はどれも「大きい問題を小さく割る」という同じ目的から出発していますが、割り方の発想がそれぞれ違います。分割統治は空間的に分け、貪欲法は時間の流れに沿って一歩ずつ選び、動的計画法は過去と今をつなぎ、探索と枝刈りは調べる範囲そのものを制御します。同じ「小さくする」でも、切り口がまったく異なることを、まずここで押さえておきます。

四つの型をふり返る

分割統治は、大きな仕事を独立して解ける部分に切り分け、それぞれを片付けてから最後にひとつへ合わせる考え方でした。三十ページの資料チェックを複数人で分担する場面や、複数拠点の集計を積み上げる場面がこれにあたります。分けることよりも、最後に合わせる手順まで決めておくことが成功の条件でした。分ける境界を業務の実態に合わない場所に引いてしまうと、統合の段階で書き直しが発生するという落とし穴も見ました。

貪欲法は、いま選べる選択肢の中から一番良さそうなものを選び、それを繰り返して答えに近づく考え方でした。締切が重なった依頼を、早く終わるものや影響の大きいものから順に片付けていく場面がこれにあたります。速さが値打ちである一方、重要だが着手しにくい仕事を先送りし続けていないか、基準を定期的に見直す必要がありました。この選択が後の選択肢を狭めてしまわないかを確認することが、貪欲法を安全に使うための目安でした。

動的計画法は、一度出した部分的な答えを保存しておき、次に似た場面が来たときに計算し直さずに使い回す考え方でした。同じ質問への回答をFAQとして残す場面や、見積もりの内訳をテンプレート化する場面がこれにあたります。保存した答えは、次にも使える形で残し、状況の変化に応じて見直す仕組みが欠かせませんでした。保存する価値があるのは、繰り返し現れる部分に限られるという線引きも重要でした。

探索と枝刈りは、候補をひとつずつ調べながら、見込みのない候補を早い段階で切り捨てて、限られた時間を有望な候補に集中させる考え方でした。取引先候補の比較検討や書類選考の場面がこれにあたります。外すための基準を調べ始める前に決め、切りすぎていないかを確認する必要がありました。基準を後付けにすると印象による判断に変わってしまう、という注意点も見ました。

どれを選ぶかの判断フレーム

四つの型は、それぞれ効く場面の特徴が異なります。目の前の問題が「独立した部分に分けられるかどうか」を最初に確認してください。分けられて、かつ分けた部分同士に依存関係がなければ、分割統治が候補になります。分けられない、あるいは分けても部分同士がつながっているなら、別の型を検討します。

仕事の構造を先に見極めてから手順を決めるという姿勢は、2章で見た「複数の仕事をどう並べるか」という問いにも通じるものです。

次に、「同じ部分問題がこれまでに何度も出てきたか、これからも出てきそうか」を確認します。繰り返し現れる部分があるなら、動的計画法によって過去の答えを使い回せないかを考えます。繰り返し現れないなら、保存する手間をかけるだけ無駄になります。この確認は、分割統治で問題を分けたあとに、分けた先の部分同士を見比べる形で行うと見つけやすくなります。分けた部分の中に、形の似たものがいくつも並んでいないかを探すのがこつです。

続いて、「各段階の選択が、あとの選択の幅を狭めてしまわないか」を確認します。狭めないなら貪欲法で速く進めても大きな損失はありません。狭めるなら、目先の判断だけで進めることに慎重になる必要があります。この確認をさぼると、あとになって「あのとき別の選び方をしていれば」という後悔が積み重なる場面に出会いやすくなります。

最後に、「候補の数が多く、全部を同じ深さで調べる余裕がないか」を確認します。当てはまるなら、探索と枝刈りの考え方で、調べる前に基準を立てて絞り込みます。四つの問いに順番に答えていくことで、目の前の問題にどの型が合うかが見えてきます。ひとつの問題の中に複数の型が同時に登場することも珍しくない、という点は、この章の最初のページで見たとおりです。

四つの問いは、どれかひとつだけに「はい」と答えて終わりにする必要はありません。複数の問いに同時に「はい」と答えられることもあります。そのときは、あとで見るように複数の型を組み合わせて使います。逆に、どの問いにも当てはまらないと感じたら、それは分け方そのものを見直すべきサインです。問題の切り口を変えると、四つのどれかが当てはまる形に見えてくることがよくあります。

四つの判断フレームを図にまとめると、次のようになります。それぞれの問いに「はい」と答えたときに、どの型が候補になるかを示しています。

独立して分けられる → 分割統治 繰り返し現れる → 動的計画法 選択が幅を狭めない → 貪欲法 候補が多すぎる → 探索と枝刈り 複数の問いに同時に「はい」なら、型を組み合わせる

四つの箱は互いに排他的ではありません。ひとつの問題が複数の箱に同時に当てはまることのほうが、実際にはよくあります。

型を組み合わせて使う

実際の仕事では、四つの型はしばしば組み合わさって登場します。年に一度の全社イベントの準備を思い出してください。会場選びとケータリング手配は独立した作業として分担し(分割統治)、会場の候補は予算条件で早めに絞り込み(探索と枝刈り)、招待状の文面は過去のイベントのものを使い回し(動的計画法)、当日の役割分担は確定しやすい人から決めていく(貪欲法)。ひとつの大きな仕事の中で、四つの型がそれぞれの持ち場を担っています。

この例で注目してほしいのは、四つの型が対立せずに共存している点です。分割統治で全体を部分に分けたあと、それぞれの部分の中でさらに貪欲法や探索と枝刈りが使われています。大きい問題を小さく割るという作業は、一度きりの操作ではなく、割った先でもう一度別の型を当てはめる、という入れ子の構造になっていることが多いのです。ひとつの型で全体を解決しようとせず、部分ごとに最適な型を選び直す姿勢が、四つの型を使いこなす鍵になります。

型を組み合わせるときに大事なのは、どの部分にどの型を当てはめているかを、自分の中で言葉にしておくことです。「ここは分けて分担する部分」「ここは過去の答えを使い回す部分」と整理できていれば、途中で状況が変わったときも、どこを見直せばよいかがすぐに分かります。型を意識せずに進めていると、うまくいかない箇所が出てきても、何が原因なのか特定しにくくなります。

たとえば全社イベントの準備が途中で予算を減らすことになったとします。型を意識していれば、影響が出るのは「探索と枝刈り」で使っていた会場の絞り込み基準だとすぐに分かり、条件を見直すだけで対応できます。型を意識していないと、準備全体をもう一度最初から見直す羽目になります。型ごとに担当箇所を切り分けておくことは、変化への対応力そのものを底上げします。

次の章への橋

この章で見た四つの型は、いずれも「ひとつの問題を、ひとりまたは一つのチームがどう解くか」という視点で書かれています。ところが仕事は、同じような問題が形を変えて何度も、しかも複数の人の手で繰り返されます。動的計画法で見た「同じ計算を二度しない」という発想を、個人の頭の中の話で終わらせず、チーム全体の仕組みにまで広げるとどうなるでしょうか。

たとえば、この章で見たFAQ化や見積もりのテンプレート化は、担当者一人の工夫として行えば動的計画法ですが、同じ仕組みをチーム全員が使える形にすれば、話はもう一段大きくなります。個人の引き出しの中身を、チームの共有財産に変える動きです。この動きには、個人で答えを保存するときとは違う難しさが伴います。誰が更新するのか、誰でも見つけられる場所にあるか、古くなったときに誰が気づくのか。これらは個人の工夫だけでは解決できない、チームの仕組みの問題です。

次の章では、同じ手順を複数人がそれぞれ独自にやり直してしまう問題と、その手順を共通の部品として仕組み化する考え方を見ていきます。

持ち帰り

  • 分割統治・貪欲法・動的計画法・探索と枝刈りは、それぞれ効く場面の条件が異なります。
  • 「独立して分けられるか」「繰り返し現れるか」「選択が後の幅を狭めるか」「候補が多すぎないか」の順に確認すると、型を選びやすくなります。
  • ひとつの仕事の中で複数の型を組み合わせて使うことは自然であり、どこにどの型を当てているかを言葉にしておくと見直しやすくなります。

やってみる

今抱えている大きめの仕事をひとつ選び、四つの判断フレームを順番に当てはめて、どの型が使えそうかを紙に書き出してみてください。