検索アルゴリズム
情報の高速検索を可能にするデータ構造であるハッシュテーブルの視覚的表現

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

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

適切な検索アルゴリズムは、検索対象となるデータ構造によって大きく異なり、データに関する事前知識も考慮されることがあります。検索アルゴリズムは、検索木、ハッシュマップ、データベースインデックスといった特別に構築されたデータベース構造によって、より高速化または効率化できます。[ 1 ] [ 2 ]

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

アルゴリズムは、計算複雑度、つまり理論上の最大実行時間によって評価されることが多い。例えば、二分探索関数の最大計算複雑度はO (log n )、つまり対数時間である。簡単に言えば、探索対象を見つけるために必要な演算の最大回数は、探索空間の大きさの対数関数である。

検索アルゴリズムの応用

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

クラス

仮想検索空間向け

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

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

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

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

特定の構造のサブ構造の場合

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

このカテゴリのもう一つの重要なサブクラスは、文字列内のパターンを検索する文字列検索アルゴリズムです。有名な例としては、ボイヤー・ムーアアルゴリズムとクヌース・モリス・プラットアルゴリズム、そしてサフィックスツリーデータ構造に基づくいくつかのアルゴリズムが挙げられます。

関数の最大値を求める

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

量子コンピュータの場合

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

参照

カテゴリー:

参考文献

引用

  1. ^ Beame & Fich 2002、39ページ。
  2. ^ Knuth 1998、§6.5（「二次キーによる検索」）。
  3. ^ Knuth 1998、§6.1（「順次検索」）。
  4. ^ Knuth 1998、§6.2（「キーの比較による検索」）。
  5. ^ Knuth 1998、§6.3（デジタル検索）。
  6. ^ Knuth 1998、§6.4、（ハッシュ）。
  7. ^ Talukdar, Sarosh; Baerentzen, Lars; Gove, Andrew; De Souza, Pedro (1998-12-01). 「非同期チーム：自律エージェントのための協力スキーム」. Journal of Heuristics . 4 (4): 295– 321. doi : 10.1023/A:1009669824615 . ISSN  1572-9397 .
  8. ^ Hunter, AH; Pippenger, Nicholas (2013年7月4日). 「チャネルグラフにおける局所探索と大域探索」.ネットワーク：国際的な旅. arXiv : 1004.2526 .
  9. ^ López, GV; Gorin, T; Lara, L (2008年2月26日). 「第一および第二近傍結合を持つイジング核スピン鎖量子コンピュータにおけるグローバーの量子探索アルゴリズムのシミュレーション」. Journal of Physics B: Atomic, Molecular and Optical Physics . 41 (5) 055504. arXiv : 0710.3196 . Bibcode : 2008JPhB...41e5504L . doi : 10.1088/0953-4075/41/5/055504 . S2CID 18796310 . 

参考文献

本

記事

「https://en.wikipedia.org/w/index.php?title=検索アルゴリズム&oldid =1326489569」より取得