検索アルゴリズム

コンピュータサイエンスにおいて、検索アルゴリズムは検索問題を解決するために設計されたアルゴリズムです。検索アルゴリズムは、特定のデータ構造内に格納されている情報、または問題ドメインの検索空間で計算された情報を、離散値または連続値で取得します。

検索エンジンは検索アルゴリズムを使用しますが、アルゴリズム学ではなく情報検索の研究に属します。

使用する適切な検索アルゴリズムは、検索対象のデータ構造によって決まることが多く、データに関する事前の知識も必要になる場合があります。検索アルゴリズムは、検索ツリー、ハッシュマップ、データベースインデックスなどの特別に構築されたデータベース構造によって、より高速または効率的にすることができます。^{[1] [2]}

検索アルゴリズムは、検索のメカニズムに基づいて、線形、バイナリ、ハッシュの 3 種類のアルゴリズムに分類できます。線形検索アルゴリズムは、すべてのレコードを線形方式でチェックして、ターゲット キーに関連付けられているレコードを探します。^[3] バイナリ、または半間隔検索は、検索構造の中心を繰り返しターゲットにし、検索空間を半分に分割します。比較検索アルゴリズムは、線形検索を改良したもので、キーの比較に基づいてレコードを連続的に削除してターゲット レコードが見つかるまで処理し、順序が定義されたデータ構造に適用できます。^[4]デジタル検索アルゴリズムは、数値キーを使用して、データ構造内の数字の特性に基づいて機能します。^[5]最後に、ハッシュは、ハッシュ関数に基づいてキーをレコードに直接マッピングします。^[6]

アルゴリズムは、多くの場合、計算の複雑さ、つまり理論上の最大実行時間によって評価されます。たとえば、バイナリ検索関数の最大複雑さはO (log n )、つまり対数時間です。簡単に言えば、検索対象を見つけるために必要な操作の最大数は、検索空間のサイズの対数関数です。

検索アルゴリズムの具体的な用途は次のとおりです。

• 組み合わせ最適化における問題:
  • 最短経路問題の一種である車両経路問題
  • ナップサック問題: それぞれに重量と価値があるアイテムのセットが与えられた場合、合計重量が指定された制限以下になり、合計価値が最大になるように、コレクションに含める各アイテムの数を決定します。
  • 看護師のスケジュール問題
• 制約充足における問題:
  • 地図の色分け問題
  • 数独やクロスワードパズルを解く
• ゲーム理論、特に組み合わせゲーム理論では、次に行う最善の動きを選択する（ミニマックスアルゴリズムなど）
• あらゆる可能性の中から組み合わせやパスワードを見つける
• 整数の因数分解（暗号学における重要な問題）
• 検索エンジン最適化 (SEO) と Web クローラー向けのコンテンツ最適化
• プロセスのパラメータ（温度、圧力、pHなど）を変更して、化学反応などの工業プロセスを最適化する
• データベースからレコードを取得する
• リストまたは配列内の最大値または最小値を見つける
• 指定された値が値セット内に存在するかどうかを確認する

仮想空間を探索するアルゴリズムは、制約充足問題で使用されます。制約充足問題の目的は、特定の変数への一連の値割り当てを見つけることです。この割り当ては、特定の数式や不等式/等式を満たします。また、これらの変数の特定の関数を最大化または最小化する変数割り当てを見つけることが目的の場合にも使用されます。これらの問題のアルゴリズムには、基本的なブルートフォース探索(「ナイーブ」または「非情報」探索とも呼ばれます) や、線形緩和、制約生成、制約伝播など、この空間の構造に関する部分的な知識を活用しようとするさまざまなヒューリスティックが含まれます。

重要なサブクラスは、局所探索法である。これは、探索空間の要素をグラフの頂点とみなし、エッジはケースに適用可能な一連のヒューリスティックによって定義される。そして、最急降下法や最良優先基準、あるいは確率的探索などに従って、エッジに沿って項目から項目へと移動することで空間をスキャンする。このカテゴリには、シミュレーテッドアニーリング、タブー探索、Aチーム、遺伝的プログラミングなど、任意のヒューリスティックを特定の方法で組み合わせるさまざまな一般的なメタヒューリスティック手法が含まれる。局所探索の反対は、グローバル探索法である。この方法は、探索空間が制限されておらず、特定のネットワークのすべての側面が探索アルゴリズムを実行するエンティティに利用できる場合に適用できる。^[7]

このクラスには、要素をツリーの頂点と見なし、そのツリーを特別な順序でトラバースするさまざまなツリー検索アルゴリズムも含まれます。後者の例には、深さ優先探索や幅優先探索などの網羅的な方法や、バックトラッキングや分枝限定法などのさまざまなヒューリスティックベースの検索ツリー刈り込み方法が含まれます。一般的なメタヒューリスティックはせいぜい確率的な意味でしか機能しませんが、これらのツリー検索方法の多くは、十分な時間を与えられれば、正確な解決策または最適な解決策を見つけることが保証されています。これを「完全性」と呼びます。

もう 1 つの重要なサブクラスは、チェスやバックギャモンなどの複数プレイヤー ゲームのゲーム ツリーを探索するアルゴリズムです。ゲーム ツリーのノードは、現在の状況から生じる可能性のあるすべてのゲーム状況で構成されます。これらの問題の目標は、対戦相手の可能性のあるすべての動きを考慮して、勝つ可能性が最も高い動きを見つけることです。同様の問題は、ロボットの誘導やマーケティング、金融、軍事戦略の計画など、人間または機械が結果を完全に制御できない連続した決定を下す必要がある場合にも発生します。この種の問題 (組み合わせ探索) は、人工知能の分野で広範に研究されてきました。このクラスのアルゴリズムの例には、ミニマックス アルゴリズム、アルファ–ベータ プルーニング、A* アルゴリズムとそのバリエーション があります。

「組み合わせ探索」という名前は、一般に、グラフ、文字列、有限群などの特定の離散構造の特定のサブ構造を探すアルゴリズムに使用されます。組み合わせ最適化という用語は、通常、あるパラメータの最大値 (または最小値) を持つサブ構造を見つけることが目的である場合に使用されます。(サブ構造は通常、制約のある整数変数のセットによってコンピュータ内で表現されるため、これらの問題は制約充足または離散最適化の特殊なケースと見なすことができますが、通常は、内部表現が明示的に示されない、より抽象的な設定で定式化され、解決されます。)

重要かつ広く研究されているサブクラスはグラフアルゴリズム、特にグラフトラバーサルアルゴリズムであり、これは特定のグラフ内のサブ構造（サブグラフ、パス、回路など）を見つけるためのものです。例としては、ダイクストラのアルゴリズム、クラスカルのアルゴリズム、最近傍アルゴリズム、プリムのアルゴリズムなどがあります。

このカテゴリのもう 1 つの重要なサブクラスは、文字列内のパターンを検索する文字列検索アルゴリズムです。2 つの有名な例としては、 Boyer-Moore アルゴリズムとKnuth-Morris-Pratt アルゴリズム、およびサフィックス ツリーデータ構造に基づくいくつかのアルゴリズムがあります。

1953 年、アメリカの統計学者 ジャック・キーファーは、単峰関数の最大値を見つけるために使用できる フィボナッチ探索を考案し、コンピューター サイエンスの分野でさまざまな用途に使用されています。

また、グローバーのアルゴリズムのような量子コンピュータ用に設計された検索方法もあり、データ構造やヒューリスティックスの助けがなくても、理論的には線形検索や総当たり検索よりも高速です。量子コンピュータの背後にあるアイデアとアプリケーションはまだ完全に理論的なものです。しかし、グローバーのようなアルゴリズムを使用して、量子コンピューティングシステムの仮想的な物理バージョンを正確に再現する研究が行われてきました。^[8]

• 逆方向帰納法 – 順序に従って逆方向に推論するプロセス
• コンテンツアドレス可能メモリ – 特定の超高速検索アプリケーションハードウェアで使用される特殊なタイプのコンピュータメモリ
• 二段階進化 – 複雑適応システム内で自己組織化を促進するプロセス
• 線形探索問題 – 計算探索問題
• 検索と最適化には無料のランチはありません – 平均ソリューションコストはどの方法でも同じです
• レコメンデーションシステム – ユーザーの好みを予測するシステム。また、統計的手法を使用して非常に大規模なデータセットの結果をランク付けする。
• 検索エンジン（コンピューティング）  – 情報の検索を支援するシステム
• 検索ゲーム – 2人ゼロサムゲーム
• 選択アルゴリズム – k番目に小さい値を見つける方法
• ソルバー – 数学の問題を扱うソフトウェア
• ソートアルゴリズム – リストを順序どおりに並べるアルゴリズム。特定の検索アルゴリズムを実行するために必要なもの。
• ウェブ検索エンジン – ウェブ上で関連情報を検索するためのソフトウェア システムリダイレクト先の簡単な説明を表示するページ

カテゴリー:

• カテゴリ:検索アルゴリズム

• Knuth, Donald (1998)。『ソートと検索。コンピュータプログラミングの芸術。第 3 巻 (第 2 版)。マサチューセッツ州レディング: Addison-Wesley Professional。

• Beame, Paul; Fich, Faith (2002年8 月)。「先行問題および関連問題の最適境界」。Journal of Computer and System Sciences。65 ( 1): 38–72。doi : 10.1006/ jcss.2002.1822。S2CID  1991980 。
• Schmittou, Thomas; Schmittou, Faith E. (2002-08-01). 「先行問題および関連問題の最適境界」. Journal of Computer and System Sciences . 65 (1): 38–72. doi : 10.1006/jcss.2002.1822 .