ブルートフォース検索: 基礎と応用

By Fouad Sabry

ブルート フォース検索とは

コンピュータ サイエンスの分野では、ブルート フォース検索、徹底的な検索、または生成とテストは、非常に一般的な問題解決手法です。 そしてアルゴリズムパラダイム。 この手法とパラダイムは、考えられるすべての候補を体系的に調べて、各オプションが問題のステートメントを満たすかどうかを判断することで構成されます。 この手法の別名は、全数検索、総当たり検索、または全数検索です。

メリット

(I) 洞察と検証 次のトピックについて説明します。

第 1 章: ブルートフォース検索

第 2 章: 数独解決アルゴリズム

第 3 章: 順列

第 4 章: バックトラッキング

第 5 章: 分岐と限界

第 6 章: 二分探索アルゴリズム

第 7 章: 中間者攻撃

第 8 章: 並列コンピューティング

第 9 章: ランダム化アルゴリズム

第 10 章: ブルートフォース攻撃

(II) 一般トップへの回答 ブルート フォース検索に関する質問。

(III) 多くの分野におけるブルート フォース検索の使用例。

(IV) 266 の新興テクノロジーを簡潔に説明する 17 の付録 各業界のブルート フォース検索テクノロジーを 360 度完全に理解するための本です。

本書の対象者

専門家、大学生、大学院生、 愛好家、愛好家、そして基本的な知識や情報を超えてあらゆる種類の総当たり検索をしたい人。

 

• Language: 日本語
• Publisher: 10億人の知識があります [Japanese]
• Release date: Jun 28, 2023

Book preview

第1章:ブルートフォース検索

コンピュータサイエンスの分野では、ブルートフォース検索、網羅的検索、または生成とテストは、非常に一般的な問題解決手法とアルゴリズムパラダイムであり、ソリューションのすべての可能な候補を体系的に列挙し、各候補が問題のステートメントを満たしているかどうかを確認します。このタイプの検索の他の名前には、網羅的検索とブルートフォース検索が含まれます。生成とテストは、網羅的な検索の別名です。

ブルートフォースを使用して自然数nの除数を識別する方法は、1からnまでのすべての数をリストし、それぞれが剰余を残さずにnを除算するかどうかを確認します。これは、すべての除数が見つかるまで繰り返されます。8つのクイーンの問題は、ブルートフォースと呼ばれる方法を使用して解決できます.これは、64個の正方形を持つチェス盤上の8つの駒の考えられる各配置をチェックして、駒のいずれか(クイーンの駒)がボード上の他の駒のいずれかを攻撃できるかどうかを確認します。その結果、ブルートフォース検索は、問題のサイズが制限されている場合、または考えられる解決策のコレクションをより管理しやすいサイズに最小限に抑えるために利用できる問題固有のヒューリスティックがある場合に、ほとんどの場合使用されます。このアプローチは、実装の容易さが所要時間よりも優先される状況でも採用されます。

これは、たとえば、アルゴリズムの障害が非常に壊滅的な影響を与える重要なアプリケーションや、コンピューターを使用して数学的定理を証明する場合に当てはまります。どちらの状況でも、メソッドの間違いは非常に深刻な影響を及ぼします。ブルートフォースを使用した検索は、さまざまなアルゴリズムまたはメタヒューリスティクスのパフォーマンスを比較するためのベースラインアプローチとしても有益である可能性があります。実際、「ブルートフォース検索」という用語は、メタヒューリスティックの最も基本的な形式を指すために使用される場合があります。バックトラッキングでは、最初に明示的にリストされることなく、膨大な潜在的な解決策のセットが排除される可能性があるため、リトレースはブルートフォース検索と間違えないでください(上記の8つの女王の問題に対する教科書のコンピューターソリューションのように)。線形検索は、データベース内の何かを見つけるブルートフォースアプローチの別の用語であり、テーブルの各エントリを作成された順序でチェックすることを含みます。

大統領の地位の次の可能な候補者はcです。

有効 (P, c): 問題の候補 c が P の解であるかどうかを判断します。

出力(P、c):アプリケーションに適した方法でPのソリューションcを実装します。

後続の方法は、インスタンスPの潜在的な候補のすべてがいつ除去されたか、その前の候補cの後にいつ除去されるかを示す必要があります。

これは、実際の候補とは異なる従来のデータ値Λである「ヌル候補」を返すことによって、迅速かつ容易に達成され得る。

同様に、最初のプロシージャは、インスタンス P の候補がまったくない場合に Λ を返す必要があります。

次に、アルゴリズムは、問題を解決するためのブルートフォースアプローチを表現します。

c ← 最初(P)

一方、c ≠ Λ do

有効な場合(P,c)

出力(P, c)

  c ← 次へ(P, c)

終了する間

例えば、nを整数で除算する因子を求めようとしている間に、nの値はインスタンスデータP中に見出され得る。

呼び出し first(n) は、n  ≥が 1 の場合は整数 1 を返し、それ以外の場合は Λ を返す必要があります。c が n より小さい場合、next(n,c) 呼び出しは c プラス 1 を返し、それ以外の場合は Λ を返します。valid(n,c) は、引数 c を n で除算できる場合にのみ true を返す必要があり、その場合にのみ true を返します。

(真実は)、Λをn + 1に選択すると、 n≥1とc< n のテストは不要です。上記のブルートフォース検索アルゴリズムは、 与えられたインスタンスPの解であるすべての候補の出力を呼び出します。

最初の解、または所定の量の潜在的な答えを見つけた後に終了するようにメソッドを適応させるのは簡単です。または、一定数の応募者のスクリーニング後、またはプロセッサを使用して一定期間費やされた後。

ブルートフォース技術を使用することの主な欠点は、実生活で発生する多くの状況で、 すべての自然な選択の中から選択することは不可能でしょう。

たとえば、上記の方法を使用して特定の整数を除算する数値を検索すると、指定された数nは、評価される潜在的な応募者の量になります。

したがって、nに16桁の10進数が含まれている場合、たとえば、検索には少なくとも10 15のコンピューター命令を実行する必要があります。

nが64ビットの任意の自然整数である場合、:、通常、小数点以下約19桁になります。 狩りには約10年かかると予想されます。

データ量がより大きくなると、潜在的な候補のプールのこの劇的な増加は、さまざまな問題で発生します。

たとえば、10文字の特定の再配置を探している場合、したがって、評価する3,628,800の潜在的な候補の10倍があり、標準のパーソナルコンピュータは1秒未満で生成および分析できます。

ただし、もう1文字追加すると、潜在的な候補の数は11倍に増加し、データのサイズは10%増加し、1000%増加します。

20文字の場合、20人がそのポジションに立候補しています!、これは約2.4×10¹⁸ または2.4キンティリオンです。そして、狩りには約10年かかると推定されています。

この望ましくない現象は、一般的な用語では組み合わせ爆発、または次元が多すぎるという問題と呼ばれます。

チェスで勝つ方法を理解することは、組み合わせの複雑さが解きやすさの限界につながる可能性があることを例示する1つのシナリオです。チェスのゲームは完全に解決することはできません。2005年は、6個以下のチェスゲームのすべての可能なエンディングが解決され、正しくプレイされた場合の各ポジションの結果が明らかになった年でした。テーブルベースを完成させるのにさらに10年かかり、チェスの駒をもう1つ追加した後、7ピースのテーブルベースが完成しました。チェスのエンドゲームにもう1つのピースを追加すると、8ピースのテーブルベースになるのは扱いにくいと考えられています。これは、組み合わせの複雑さが増すためです。

検索空間の削減は、問題の種類に固有のヒューリスティックを使用して、ブルートフォース アルゴリズム、つまり問題に対する潜在的な回答のプールの速度を上げる方法の 1 つです。

たとえば、8人の女王の問題の目的は、通常のチェス盤に8人の女王を配置して、どの女王も他の女王を攻撃しないようにすることです。

各女王が64の正方形のいずれかに入ることができるという事実の結果として、原則として考慮すべき64⁸ = 281,474,976,710,656の可能性があります。

ただし、女王の間に区別はなく、同じ正方形に同時に2つの女王が存在することは決してないため、候補はすべて、合計64の正方形から8つの正方形を選択するときに利用できるさまざまな組み合わせです。したがって、8 つのうち 64 は 64!/(56!*8!) = 4,426,165,368 の潜在的な回答に等しく、これは事前の推定値の約 1/60,000 です。

さらに、同じ行または列に2つのクイーンを同時に配置することを含む可能な解決策はありません。

したがって、これらの構成に焦点を当てることで、オプションのプールをさらに絞り込むことができます。

上記の例が示すように、少しでも調査を行うと、潜在的な解決策のプールが大幅に削減されることが多く、困難な問題を簡単に解決できる問題に減らす可能性があります。

場合によっては、分析により、実行可能なソリューションのセットのみを含むように潜在的な選択肢を絞り込むことができます。つまり、 これにより、1つの答えを発見するか、必要に応じて必要なすべてのソリューションを直接列挙するアルゴリズムが得られる可能性があります)、試験や資格のない個人の生産に時間を費やすことなく。

たとえば、「417で均等に割り切れる1〜1,000,000のすべての数値を見つける」という問題を解決するための単純なブルートフォースアプローチには、1〜1,000,000の範囲のすべての整数の生成が含まれ、それぞれを分割できる程度を決定します。

ただし、この問題は、417から始めて、数が1,000,000を超えるまで417を繰り返し追加することで、テストさえも必要な÷2398(= 1,000,000417)ステップのみで解決できます。

すべてのソリューションではなく、1つのソリューションのみを必要とするアプリケーションでは、ブルートフォース検索の予想される実行時間は、多くの場合、候補がテストされる順序によって異なります。これは、ブルートフォース検索が、考えられるすべての解決策を試すことによって問題の解決策を見つけようとするためです。最も可能性の高い応募者からスクリーニングプロセスを開始することをお勧めします。たとえば、ランダムな整数nの正しい除数を探す場合、候補の除数を2からn 1までの昇順で列挙することが望ましいです。これは、nがcで割り切れる確率が1 / cに等しいという事実によるものです。さらに、過去に失敗したテストの数は、候補者が正当である可能性に影響を与えることがよくあります。たとえば、P として提供される 1000 ビットの文字列内に 1 のビット値を見つけるという課題を考えてみましょう。このシナリオでは、考えられる答えはインデックス 1 から 1000 であり、候補 c は Pc] = 1 の場合にのみ正しいと見なされます。ここで、Pの最初のビットは0または1のいずれかであると仮定しますが、それ以降のすべてのビットは、その前のビットと同じになる可能性が90%あります。応募者が1人から1000人の降順でリストされている場合、成功する前に評価する必要がある候補者の数は平均して約6人になります。一方、候補が1,11,21,31...991,2,12,22,32などの順序で列挙されている場合、tの予測値は2より少し大きくなります。より広い意味では、検索領域は、それ以前の試行が成功しなかった場合、後続の候補者が正当である可能性が最も高いように列挙する必要があります。正解が何らかの形で「クラスター化」される可能性が高い場合、新しい候補者はそれぞれ、その意味でその前の候補者から可能な限り離れている必要があります。もちろん、ランダムな偶然のために回答が当初の予想よりも均等に分配される可能性が高い場合は、逆のことが当てはまります。

メタヒューリスティックと呼ばれるさまざまな代替検索戦略があり、個人が答えについて持つ可能性のあるいくつかの形式の不完全な情報を利用することを目的としています。ヒューリスティックは、検索の特定の側面を早期に排除するために使用できる別のツールです。ゲームツリーの検索に使用され、検索の初期段階で多数のサブツリーを削除するミニマックス手法は、この概念の一例です。チャート解析などの手法は、問題の制限を利用することにより、言語解析などの一部の分野でのタスクの複雑さを指数レベルから多項式レベルに軽減する場合があります。制約プログラミング言語で効果的に実装できる制約伝播と呼ばれる手法を使用することで、制約充足問題を扱う場合など、多くの状況で検索領域を大幅に減らすことができます。問題の検索領域は、問題全体を問題のより簡単なバージョンと交換することによっても縮小できます。たとえば、コンピュータチェスでは、ゲームの残りの部分で可能なすべての動きの完全なミニマックスツリーを計算する代わりに、ミニマックスの可能性のより限定されたツリーが計算され、ツリーは特定の移動数で剪定され、ツリーの残りの部分は静的評価関数によって近似されます。これは、ゲームの残りの部分で可能なすべての動きの完全なミニマックスツリーを計算するのではなく行われます。

ブルートフォース攻撃は、正しいキーが発見されるまで、各潜在的なキーを順番に調べることを含む暗号化で使用される方法です。(ワンタイムパッドを除く)暗号化スキームの欠陥を利用できない敵対者による、そうでなければ彼らがやろうとしている仕事をより簡単にするであろう。

暗号化キーの長さは、ブルートフォース攻撃が実際に実行可能かどうかを決定するものです。短いキーは、長いキーよりも指数関数的に壊れやすいです。長い暗号化キーは、短い暗号化キーよりも解読が指数関数的に困難です。エンコードされるデータを難読化することで、ブルートフォース攻撃の有効性を減らすことができます。これにより、攻撃者がコードの解読に成功したかどうかを判断することがより困難になります。攻撃者が暗号化システムに対するブルートフォース攻撃を成功させるのに仮想的にかかる時間は、システムの強度を評価するために使用されるメトリックの1つです。

{第 1 章終了}

第2章:数独解決アルゴリズム

典型的な数独は81セルで構成されています, 9×9グリッドで, それは9ボックスで構成されています, 最初のボックスと後続の各ボックスとの交点, 中央, または最後の3行, プライマリ, 中央, または最後の3列.

各セルには 1 から 9 までの数値を含めることができるため、各行、列、およびボックスには、各数値のインスタンスが 1 つだけ存在できます。

数独を解くための最初のステップは、特定のセルを数字(手がかり)で埋めることです。 ここでの目的は、残りのセルを仕上げることです。

有効な数独に対して答えは1つだけです。

数独を解決するために、プレイヤーと研究者はさまざまなコンピューター手法を利用し、その特性を研究し、魅力的な対称性と他のいくつかの品質を持つ数独を特徴とするまったく新しい謎を作成します。

9×9パズル(n = 9)をほんの一瞬で解くいくつかのコンピュータアルゴリズムがありますが、 一方、組み合わせ爆発はnが高くなるにつれて起こり、nの値が大きくなるにつれて作成、分析、解決できる数独の可能な特性に制限が課せられます。

コンピュータシステムを構築した特定のアマチュアコンピュータプログラマによる数独パズルの解き方には、圧倒的な力を使った一種の探索というバックトラッキングアプローチが用いられている。

バックトラックの手法は、別のパスに進む前に、潜在的な解決策につながる1つのパスを徹底的に調査するため、深さ優先検索(幅優先検索とは対照的に)として知られています。

約5.96 x 1126の最終グリッドが存在することが確立されていますが、 ブルートフォースと呼ばれるアルゴリズムの使用は、数独問題を解決するための有用な方法である可能性があります。

ブルートフォースを使用するメソッドは、空の各セルを何らかの順序で調べ、数字で順番に埋めるか、数値が無効であることが検出されたときに逆方向に移動します。一言で言えば、コンピュータプログラムは、最初のセルに数字「1」を入力し、そこにいることが許可されているかどうかを判断することによって、謎を解くかもしれません。違反がない場合(行、列、およびボックスの制限を確認する)、アルゴリズムは次のセルに進み、そのセルに「1」を入力します。違反がある場合、アルゴリズムは前のセルに戻ります。違反をチェックするプロセス中に、数値「1」が許可されていないと判断された場合、値は「2」に増加します。9桁のいずれも使用できないセルが見つかった場合、アルゴリズムはそのセルを空白のままにして、その前のセルに移動します。その後、そのセルの現在の値が1つ増えます。このプロセスは、最後 (81 番目) のセルに格納できる最大値が見つかるまで続行されます。

アニメーションは、このアプローチを使用して数独を解く方法を示しています。アルゴリズムは、問題内の開いている各セルを調査して潜在的な答えを探しますが、赤い数字で表されるパズルの手がかりは変わりません。このメソッドは、現在のセットが数独パズルの要件を満たしていないと判断した場合、以前にチェックされた値をすべて破棄する可能性があることに注意してください。

このアプローチを使用することには、いくつかの利点があります。

間違いなく解決策があります(パズルが有効である限り)。

複雑さの程度は、問題の解決にかかる時間にはほとんど関係ありません。

この方法(ひいてはコンピューターコード)は、他のアルゴリズム、特に最も困難な問題に対する解決策を保証する強力なアルゴリズムと比較して理解しやすいです。

論理プロシージャーの後にパターン化された他のアプローチと比較して、問題解決の速度が遅くなる可能性があることは、この方法を使用することの欠点の 1 つです。あるコーダーは、このようなアルゴリズムが数独を解くのに一般的にわずか15,000サイクル、または最大900,000サイクルしか必要としないと推定しました。各サイクルは、数独パズルのセルを通過するときの「ポインター」の位置の変化を表します。

バックトラッキングも利用する代替戦略は、通常の数独の解における個々のシンボル(値)の分布がわずか46656パターンの1つでなければならないという事実に基づいています。手動数独パズルを解くこのアプローチは、パターンオーバーレイまたはテンプレートの利用として知られており、パズルに欠けている値のみを入力することに限定されています。アプリケーションが最初に起動されると、使用可能なすべてのパターンを含むライブラリがロードまたはビルドされることが考えられます。次に、個々のシンボルには、提供された情報と一致するパターンを含むフィルタリングされたセットが与えられます。次の段階である実際の再トレースプロセスでは、競合を引き起こさない方法で、これらの各セットのパターンをマージまたはオーバーレイしようとします。このプロセスは、許可されている 1 つの組み合わせが見つかるまで続行されます。行と列にまたがる入れ子になった反復ではなく、すべてのテストに必要なのはビット単位の論理演算だけであるため、ビット ベクターを使用すると、実装が非常に簡単になります。これは、テストが実行されるためです。フィルタリングプロセス中に、パターンセットの数をさらに大幅に減らすと、最適化が大幅に向上する可能性があります。疑わしい可能性のある各パターンを、他のシンボルについて以前に検証された削減されたセット全体と比較することにより、バックトラックする必要があるパターンの総数が大幅に減少します。

数独を解くためのブルートフォースアプローチの場合と同様に、パズルを解くための最も簡単な方法のいくつかを最初に使用することで、パズルを解くのにかかる時間が大幅に短縮され、特定の「簡単な」数字が完成する可能性があります。

後戻りできないように数独を作成することが可能です。ソルバーが(アニメーションのように)上から下に向かって動作すると仮定すると、手がかりの数が少なく(17)、一番上の行に手がかりがなく、最初の行の「987654321」の解がある問題は、アルゴリズムの反対方向に動作します。したがって、コンピューターは、問題の解決策を提供するグリッドに到達する前に、上向きに「カウント」するのにかなりの時間を費やす必要があります。ある例では、プログラマーは、ブルートフォースアルゴリズムがそのような数独の答えを得るのに6時間かかることを発見しました(2008年のコンピューターを使用していますが)。広範な検索手順とより高速なコンピューターにより、この種のパズルは、最新のテクノロジーを使用して1秒未満で解決できます。

ランダム化に基づく確率的手法を使用して、数独を解くことができます。この戦略の1つの用途は次のとおりです。

グリッド上の空白を埋めるには、番号をランダムに割り当てる必要があります。

間違いの総数を決定します。

入力された数値は、エラーの数がゼロになるまで「シャッフル」する必要があります。

しばらくして、なぞなぞに対する答えが発見されます。シミュレーテッドアニーリング、遺伝的アルゴリズム、およびタブー検索は、数値を再配置する際に使用できる方法の一部です。確率的プロセスに基づくアルゴリズムは高速であることは周知の事実ですが、論理的な方法ほど迅速ではない可能性があります。ただし、最適化アルゴリズムは、論理的に解決可能であるために必ずしも問題を必要としないため、後者よりもさまざまな問題を処理する能力があります。グラフを着色するために開発されたアルゴリズムは、数独パズルにも使用すると見事に機能することはよく知られています。数独として知られているパズルは、そのように選択した場合、整数線形計画の問題として作り直すこともできます。これらの種類の手法は、非常に迅速にソリューションに非常に近づき、フィニッシュに向かって分岐を採用する場合があります。シンプレックス法は正しい数独を解くことができ、パズルを解くことができない(解決策がない)場合にエラーメッセージを表示します。複数の解が存在する可能性がある非適切な数独では、シンプレックス法は、多くの場合、いくつかの正方形に1桁を超える小数量の解を提供します。一方、正当な数独の解は、線形計画法のプリゾルブ法のみを使用して決定できます。この場合、シンプレックスの反復は必要ありません。人々が数独パズルを解くために使用する論理原則のコレクションは、LPの問題のサイズを縮小するためにpresolve approachが利用する論理ルールに含まれています。

制約充足の問題は、数独としてモデル化することもできます。「制約問題としての数独」というタイトルの彼の作品の範囲内で、数独というゲームに基づくパズルは、正確なカバー問題、より正確には正確なヒットセットの問題のいずれかに分類される場合があります。このため、問題の洗練された説明と効果的な解決策の両方が可能です。「数独パズルのすべての潜在的な解決策の迅速な発見(マイクロ秒単位で測定)に最適な方法」は、「数独を正確なカバー問題としてモデル化し、KnuthのアルゴリズムXや彼のダンシングリンク方法論などのアルゴリズムを採用するための選択方法」です。列と行のストライクと組み合わせてガウス除去を使用することは、代替として使用できる追加の戦略です。