総当たり検索

コンピュータサイエンスにおいて、総当たり探索または網羅的探索（生成とテストとも呼ばれる）は、考えられるすべての候補を体系的にチェックし、それぞれの候補が問題の記述を満たしているかどうかを検証する、非常に一般的な問題解決手法およびアルゴリズムのパラダイムである。

自然数nの約数を見つける総当たりアルゴリズムは、1 から n までのすべての整数を列挙し、それぞれがn を割り切るかどうかを確認します。8クイーンパズルに対する総当たりアプローチでは、64 マス目のチェス盤上の 8 個の駒のすべての可能な配置を調べ、それぞれの配置について、各 (クイーン) 駒が他の駒を攻撃できるかどうかを確認します。^{[ 1 ]}

総当たり探索は実装が簡単で、解が存在する場合は必ず見つけられますが、実装コストは候補解の数に比例します。多くの実際的な問題では、問題の規模が大きくなるにつれて候補解の数は非常に急速に増加する傾向があります（§組み合わせ爆発）。^{[ 2 ]}したがって、総当たり探索は通常、問題のサイズが限られている場合、または候補解のセットを管理可能なサイズに減らすために使用できる問題固有のヒューリスティックがある場合に使用されます。この方法は、処理速度よりも実装の容易さが重要な場合にも使用されます。 

これは、例えば、アルゴリズムのエラーが非常に深刻な結果を招くような重要なアプリケーションや、コンピュータを使用して数学の定理を証明する場合などに当てはまります。総当たり探索は、他のアルゴリズムやメタヒューリスティクスをベンチマークする際のベースライン手法としても役立ちます。実際、総当たり探索は最も単純なメタヒューリスティクスと見なすことができます。総当たり探索は、バックトラッキングと混同してはいけません。バックトラッキングでは、多数の解を明示的に列挙することなく破棄できます（上記の8クイーン問題の教科書のコンピュータによる解法のように）。テーブル内の項目を見つけるための総当たり法、つまり、テーブルのすべてのエントリを順番にチェックする方法は、線形探索と呼ばれます。  

総当たり法の主な欠点は、多くの現実世界の問題において、自然候補の数が法外に多いことです。たとえば、上記のように数の約数を探す場合、テストされる候補の数は与えられた数nになります。したがって、 n が16 桁の小数である場合、検索には少なくとも 10 ^{15 回のコンピュータ命令の実行が必要となり、一般的な}PCでは数日かかります。n が平均して約 19 桁の小数を持つランダムな 64 ビットの自然数である場合、検索には約 10 年かかります。データのサイズが増加するにつれて候補の数が急激に増加するこの現象は、あらゆる種類の問題で発生します。たとえば、10 文字の特定の並べ替えを探す場合、10! = 3,628,800 通りの候補を考慮する必要がありますが、一般的な PC では 1 秒未満で生成およびテストできます。しかし、文字を1つ追加するだけで（データサイズはわずか10%増加するだけですが）、候補の数は11倍、つまり1000%増加します。20文字の場合、候補の数は20!、つまり約2.4×10¹⁸ ^、または2.4京となり、検索には約10年かかります。この好ましくない現象は、一般的に組み合わせ爆発、または次元の呪いと呼ばれています。  

組み合わせの複雑さが解決限界につながるケースの1つは、チェスを解くことです。チェスは解決済みのゲームではありません。2005年に、6個以下の駒で終了するすべてのチェスのゲームが解決され、各局面を完璧にプレイした場合の結果が示されました。さらに10年かけて、チェスの駒を1つ追加してテーブルベースを完成させ、7個の駒のテーブルベースを完成させました。チェスの終了に駒を1つ追加すること（つまり8個の駒のテーブルベースを作ること）は、組み合わせの複雑さが増すため、手に負えないと考えられています。^{[ 3 ] [ 4 ] [ 5 ]}

総当たりアルゴリズムを高速化する 1 つの方法は、問題クラスに特有のヒューリスティックを使用して、探索空間、つまり候補解の集合を削減することです。たとえば、 8 クイーン問題では、標準的なチェス盤に 8 つのクイーンを配置して、どのクイーンも他のクイーンを攻撃しないようにすることが課題です。各クイーンは 64 マスのいずれにも配置できるため、原則として 64 ⁸ = 281,474,976,710,656 通りの可能性を考慮する必要があります。しかし、すべてのクイーンは同じであり、2 つのクイーンを同じマスに配置することはできないため、候補は64 マスすべてから 8 マスを選択するすべての可能な方法になります。つまり、64 から 8 を選択する = 64!/(56!*8!) = 4,426,165,368 通りの候補解があり、これは前の推定値の約 1/60,000 です。さらに、同じ行または同じ列に2つのクイーンを配置する配置は解になり得ません。したがって、候補となる配置をこれらの配置に限定することができます。 

この例が示すように、少し分析するだけで候補となる解決策の数を劇的に減らすことができ、解決困難な問題を些細な問題に変えることができる場合が多い。

場合によっては、分析によって候補が有効な解の集合に絞り込まれることがあります。つまり、テストや無効な候補の生成に時間を費やすことなく、必要な解をすべて直接列挙する（または、状況に応じて1つの解を見つける）アルゴリズムが得られる可能性があります。たとえば、「1から1,000,000までの整数で417で割り切れるすべての整数を見つける」という問題の場合、単純な総当たり解法では、範囲内のすべての整数を生成し、それぞれについて割り切れるかどうかをテストします。しかし、この問題は、417から始めて、数が1,000,000を超えるまで417を繰り返し加算することで、はるかに効率的に解決できます。これにはわずか2398ステップ（= 1,000,000 ÷ 417）しかかからず、テストも必要ありません。 

すべての解ではなく、1つの解のみを必要とするアプリケーションでは、総当たり探索の期待実行時間は、候補をテストする順序に依存することがよくあります。一般的には、最も有望な候補からテストする必要があります。たとえば、乱数nの適切な約数を探す場合、n が c で割り切れる確率は1/ cであるため、候補の約数を 2 からn − 1まで昇順に列挙する方が逆よりも良いです。さらに、候補が有効である確率は、以前の失敗した試行によって影響を受けることがよくあります。たとえば、与えられた 1000 ビットの文字列 P 内の 1 ビットを見つける問題を考えてみましょう。この場合、候補となる解はインデックス 1 から 1000 であり、候補cはP [ c ] = 1の場合に有効です。ここで、 Pの最初のビットは0または1になる可能性が等しいが、それ以降の各ビットは 90% の確率で前のビットと同じであるとします。候補を 1 から 1000 まで昇順に列挙すると、成功するまでに調べられる候補の数tは平均して約 6 になります。一方、候補を 1,11,21,31...991,2,12,22,32 などの順に列挙すると、tの期待値は 2 をわずかに超える程度になります。より一般的には、探索空間は、前の試行が有効でなかった場合に、次の候補が有効である可能性が最も高くなるように列挙する必要があります。したがって、有効な解が何らかの意味で「クラスター化」している可能性が高い場合、新しい候補は、同じ意味で前の候補からできるだけ離れている必要があります。もちろん、解が偶然に期待されるよりも均一に分散している可能性が高い場合は、その逆が成り立ちます。 

他にも、解に関する様々な部分的な知識を活用するように設計された、メタヒューリスティクスと呼ばれる探索手法が数多く存在します。ヒューリスティクスは、探索の一部を早期に打ち切るためにも使用できます。その一例として、ゲームツリーの探索におけるミニマックス原理があり、これは探索の初期段階で多くのサブツリーを排除します。言語解析などの特定の分野では、チャート解析などの手法を用いることで、問題の制約を利用して指数関数的な複雑さの問題を多項式的な複雑さの問題に縮小できます。制約充足問題など、多くの場合、制約伝播を用いることで探索空間を大幅に縮小できます。制約伝播は、制約プログラミング言語で効率的に実装されています。また、完全な問題を簡略化されたバージョンに置き換えることで、問題の探索空間を縮小することもできます。例えば、コンピュータチェスでは、ゲームの残りの部分で可能なすべての手の完全なミニマックスツリーを計算するのではなく、ミニマックスの可能性のより限定されたツリーが計算され、特定の手数でツリーが剪定され、ツリーの残りの部分は静的な評価関数によって近似されます。

暗号学において、総当たり攻撃とは、正しい鍵が見つかるまで考えられるすべての鍵を体系的にチェックする攻撃のことです。 ^{[ 6 ]}この戦略は、理論的には、攻撃者が暗号化システムの弱点を利用して攻撃を容易にすることができない場合、あらゆる暗号化データ^{[ 7 ]}（ワンタイムパッドを除く）に対して使用できます。

暗号化に使用される鍵の長さは、総当たり攻撃の現実的な実行可能性を左右し、鍵が長いほど解読は指数関数的に困難になります。総当たり攻撃は、暗号化するデータを難読化することで効果を弱めることができます。難読化によって、攻撃者は解読に成功したことを認識しにくくなります。暗号化システムの強度を測る指標の一つは、攻撃者が理論上、総当たり攻撃を成功させるのにどれくらいの時間がかかるかということです。

• 数独パズルを解くための総当たりアルゴリズム。
• 力ずくの攻撃
• ビッグオー記法
• 反復計算