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

調べるのをどこでやめるか — 探索と枝刈り

取引先候補が二十社あり、条件に合うところを探しています。全社に同じ深さで問い合わせ、同じ資料を読み込んでいたら、比較が終わる頃には締切が過ぎてしまいます。かといって適当に数社だけ選んで残りを見ないのも、見落としが怖くて踏み切れません。このページの問いは、調べる範囲をどう絞り、どこで打ち切るかです。

探索と枝刈りとは何か

探索とは、候補をひとつずつ調べながら、求める答えに近いものを見つけていく手順のことです。候補が少なければ全部を調べても大した手間ではありませんが、候補が増えると、調べる組み合わせは急激に増えていきます。候補の数が二倍になれば、単純に見ても調べる手間はおおよそ二倍以上に膨らみます。そこで使われるのが枝刈りという考え方です。枝刈りとは、調べる前に「この先は見込みがない」と判断できる候補を、実際に調べずに切り捨てて、探索する範囲そのものを減らす手法です。

たとえば道順を探す場面を思い浮かべます。目的地までの道を一本ずつすべてたどって比較する代わりに、明らかに遠回りになる道を最初から候補から外せば、比較する道の数は大きく減ります。切り捨てた道が本当に正解でないかどうかを、あとから確認する必要はありません。切り捨ての基準が正しければ、それだけで安全に候補を減らせます。この「基準が正しければ安全に減らせる」という点が、枝刈りの値打ちです。

裏を返すと、基準が間違っていれば、枝刈りは正解を取りこぼす原因になります。探索と枝刈りをセットで理解するときに大事なのは、枝刈りが速さのための工夫であって、正しさを保証する仕組みではないということです。基準の質が、結果の質をそのまま左右します。

仕事の言葉に訳すと

仕事の場面では、探索は「候補をひとつずつ検討していく作業」全般に対応します。取引先の比較検討、原因調査、書類選考など、複数の候補や可能性から絞り込んでいく作業はすべて探索です。そして枝刈りは、「明らかに条件に合わない候補を、詳しく調べる前に外す」という判断に対応します。

枝刈りの値打ちは、限られた時間を、見込みのある候補に集中させられる点にあります。二十社すべてに同じ手間をかけて問い合わせるのではなく、予算や取引条件で明らかに合わない候補を先に外し、残った数社だけをじっくり検討します。ここで大事なのは、外すための基準を、調べ始める前に決めておくことです。調べながら都合よく基準を変えると、その日の気分や第一印象で候補を落としてしまう危険があります。基準を先に決め、あとはその基準に沿って機械的に判定する、という順番を守ることが、枝刈りを安全に使う条件です。

基準を先に決めておくことには、もうひとつ利点があります。あとで「なぜこの候補を外したのか」と聞かれたときに、その場の印象ではなく、決めておいた基準を根拠として説明できることです。選定や選考の場面では、この説明のしやすさが、進め方そのものの信頼性を支えます。

具体的な場面で見る

まず取引先候補の比較検討です。二十社の候補に対して、まず予算の上限と必要な条件を明文化し、この条件に明らかに合わない候補を最初の段階で外します。残った候補についてだけ、詳しい資料を取り寄せたり、担当者と話したりする時間をかけます。全社に同じ深さで時間をかけるのではなく、絞り込んだ後の候補にこそ時間をかける、という配分の変え方です。

次に、原因調査やトラブルシューティングです。ここでいうトラブルシューティングとは、問題の原因を切り分けながら特定していく作業のことです。何か問題が起きたとき、考えられる原因をすべて同じ深さで検証しようとすると時間がかかります。まず、過去の経験や状況から見て可能性が低いと判断できる原因を、詳しく調べる前の段階で除外します。そのうえで、残った可能性の高い原因から順に深掘りしていきます。除外の基準は、事前に立てた仮説をもとに決めておき、調べながら基準がぶれないようにします。

三つめは、書類選考です。応募書類が多数集まったとき、必須条件に明らかに合わない応募を早い段階で外し、残った応募について詳しく読み込みます。全員分を同じ丁寧さで読もうとして選考が長引くよりも、この二段構えのほうが、限られた時間の中で誠実な選考につながります。ここでも、外すための必須条件を選考が始まる前に明文化しておくことが重要です。読みながら基準を作っていくと、応募順や読む順番によって判定がぶれてしまいます。

候補一覧 条件外 要検討 深掘り 条件外

図の左右にある「条件外」の枝は、印がついた時点で調べるのをやめています。真ん中の「要検討」だけが深掘りに進み、限られた時間をそこに集中させます。

落とし穴 — 基準の後付けと切りすぎ

枝刈りの一番の落とし穴は、基準を後付けにすることです。調べ始めたあとで「やっぱりこの候補は違う気がする」という理由で外すと、それは基準にもとづく判断ではなく、印象による判断になってしまいます。印象による判断は、外した理由をあとで説明できず、選考や選定の公正さが揺らぐ原因になります。基準は必ず調べ始める前に言葉にしておき、途中で変える場合はその理由も記録しておく必要があります。

もうひとつの落とし穴は、切りすぎです。基準を厳しくしすぎると、本来なら見込みのあった候補まで早い段階で外してしまい、残った候補の中に良い答えがない、という事態になります。基準の厳しさは、外した後に残る候補の数を見ながら調整する必要があります。極端に厳しい基準で一社しか残らなかった場合、その基準が本当に正しかったのか、いったん立ち止まって確認する価値があります。探索と枝刈りは、調べる手間を減らすための工夫であって、答えを見つける可能性そのものを減らしては本末転倒です。

三つめの落とし穴は、外した候補の記録を残さないことです。あとになって「あの候補、実はもう一度検討したほうがよかったのでは」という話が出たとき、いつどの基準で外したのかが分からないと、同じ議論を一からやり直すことになります。外した候補とその理由を一覧にしておくだけで、この手戻りは防げます。

持ち帰り

  • 探索は候補を調べる作業全般を指し、枝刈りは見込みのない候補を調べる前に外す工夫です。
  • 外すための基準は、調べ始める前に言葉にしておく必要があります。
  • 基準が厳しすぎて候補を切りすぎていないか、残った数を見ながら確認します。

やってみる

今検討している候補のリストについて、外すための基準をひとつだけ紙に書き出し、その基準に沿って機械的に絞り込み、外した候補と理由も一緒にメモしてください。