ブルートフォース検索と徹底的な検索: 違いと比較

コンピューター サイエンスでは、異なる側面 (文字列、数値、パターン、解) を検索するために、さまざまな開発者によって多くの検索アルゴリズムが開発されてきました。

検索はさまざまな方法で実行されます。 ブルート フォース検索と枯渇検索は、コーダーが使用する XNUMX つの文字列検索アルゴリズムです。 これらの方法は、すべての実行可能なソリューションを検索するという原則に基づいて機能します。

主要な取り組み

1. ブルート フォース攻撃は、考えられるすべての組み合わせを体系的にテストして、パスワードや暗号化をクラックします。
2. 網羅的な検索アルゴリズムは、すべての潜在的なソリューションを評価して、最適なソリューションを見つけます。
3. どちらの方法もリソースを大量に消費する可能性がありますが、特定のヒューリスティックを使用せずに問題を効果的に解決できます。

ブルート フォース vs 網羅的検索

ブルートフォースとは、試行錯誤しながらログイン情報や暗号化キーを推測したり、隠されたウェブページを見つけたりする非均一な検索です。網羅的検索は、ブルートフォース検索の一種で、次のような問題を解決するために使用されます。 順列 と組み合わせ。 均一な検索であり、時間がかかりません。

ブルート フォース アルゴリズムは、文字列を取得するために開発者によってコード化された手法であり、XNUMX クイーン パズル (XNUMX x XNUMX のチェス盤に XNUMX つのクイーンを配置するパズル) を解く際にも使用されます。

ただし、これは問題を解決するために多くの比較を必要とする直感的な戦略です。

網羅的検索は、順列と組み合わせに関連する問題を解決するために使用される一種の残忍な検索です。

主な目的は、制約を満たすことによって最適な解を見つけるためにすべての解を探索することです。 巡回セールスマンやナップザックの問題など、他の問題も分類できます。

比較表

比較のパラメータ	総当たり検索	網羅的検索
検索の種類	ブルートフォースは不均一な検索です。	徹底的な検索は、フェッチがどの方向で行われるかを認識しているため、均一な検索です。
検索	Brute Force は文字列パターンを検索するためのものです。	網羅的検索アルゴリズムは、順列、組み合わせ、およびサブセットをフェッチするためのものです。
手順	ブルート フォース アルゴリズムは、指定されたテキスト内を右に向かって移動することにより、目的のパターンを検索します。	網羅的検索アルゴリズムは、最終ノードに到達するまで各ノードを調べます。
Time	ブルートフォースは時間のかかる方法です。	網羅的検索アルゴリズムは、比較して時間がかかりません。
アプリケーション	ブルート フォース検索アルゴリズムは、XNUMX x XNUMX のボードに XNUMX つのクイーンを配置する際に使用されます。	巡回セールスマン問題の解決には、網羅的探索アルゴリズムが使用されます。

ブルートフォースサーチとは？

ブルート フォース アルゴリズムは、コンピューター サイエンスにおける検索手法の 1 つです。直感的な方法であるため、予測のみに基づいた問題を解決するための非常に直接的なアプローチです。

この方法では、解を見つけるために複雑な手法は使用されません。

このプロセスは、文字列を検索するためにテキストを繰り返し処理することです。 文字列が一致しない場合は、XNUMX ステップ右に移動し、適切な一致が見つかるまでプロセスを繰り返します。

手続きが簡単になりました。 文字列 PLANT を検索する必要があるとします。

段落内の各単語のスペルを文字列 PLANT と一致させます。 行内のフレーズが一致しない場合は右に移動します。 文字列が一致する場合、検索は成功しています。 望ましい結果が得られました。

そのため、テキストが長い場合、非常に手間のかかる検索方法といえます。 比較回数を計算するトリックは、N x M の乗算です。ここで、N はテキストの長さ、M は文字列の長さです。

例えば、

テキスト = 10

文字列= PLANT なので、文字列のサイズ =5

組み合わせ = NXM = 10 x 5 = 50

実際の生活では、ブルートフォース検索を使用できます。 例として、8×8 のチェス盤に XNUMX つのクイーンを配置します。 ルールは、XNUMX つのクイーンが別のクイーンのルートをブロックしない程度にクイーンを配置することです。

網羅的検索とは

網羅的検索は、組み合わせと順列を検索するためのブルート フォース検索アルゴリズムのサブセットです。 このアルゴリズムは、すべての制約を満たすことによって、特定の問題に対する各ソリューションを見つけることに重点を置いています。

網羅的であるということは疲れることを意味するため、これらのタイプの検索は盲目的な検索ですが、均一な検索です。 この戦略は、問題を最大化または最小化することを目的としています。

巡回セールスマン問題やナップザック問題など、多くの問題は網羅的な検索を使用して解決できます。

巡回セールスマンの問題は、セールスマンが出発地に戻る前に、最短ルートを使用して N 都市を (XNUMX 回だけ) 訪問する必要があることです。

ここで、N は都市の数であり、この問題の制約は次のとおりです。

1. 都市から都市への最短経路をたどります。
2. 戻る前にすべての都市を訪れてください。
3. すべての都市を XNUMX 回だけ訪れます。

例えば、

A、B、C、D、E の XNUMX つの都市があります。開始都市は、組み合わせを適用して賢く選択されます。 したがって、すべての制約が満たされます。

適切なパスを選択しながら、疲れ果てて時間がかかるいくつかの組み合わせを試します。 つまり、目標を達成するために循環的な動きを形成する必要があります。

ブルートフォース検索と網羅的検索の主な違い

1. ブルート フォース検索アルゴリズムは、不均一な方法です。 一方、網羅的探索アルゴリズムは画一的な方法です。
2. ブルート フォース検索アルゴリズムは、テキスト内の文字列を検索する方法です。 反対に、網羅的検索アルゴリズムは、順列と組み合わせの解を検索します。
3. ブルート フォース テクニックは、文字列内のすべての文字を一致させることによって機能します。 ただし、制約が満たされるまで、フローチャートのすべてのノードを調べる手順に従います。
4. ブルート フォース方式は、より時間がかかるため、データが短い場合に適用できます。 一方、網羅的なアルゴリズムは、複雑なシナリオでも適用できます。
5. 全数検索手法ではブルート フォース手法が踏襲されているため、全数検索よりも一般的です。

参考情報

1. https://ieeexplore.ieee.org/abstract/document/4640789/
2. https://link.springer.com/chapter/10.1007/3-540-44411-4_2