検索アルゴリズムとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > ウィキペディア小見出し辞書 > 検索アルゴリズムの意味・解説 

探索

(検索アルゴリズム から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/01/15 02:36 UTC 版)

探索(たんさく、: search)とは、特定の制約条件を満たす物を見つけ出す行動のこと。

何か問題を解くに当たって、有効な解析的な解法を用いることのできない場合は、試行錯誤によって解を得る場合もある。

一部のアルゴリズムは、元々、機械学習と並んで人工知能の分野のアルゴリズムであるが、現在はその他の分野にも応用されている。類義語として検索: search)も参照。

概要

探索アルゴリズムとは、大まかに言えば、問題を入力として、考えられるいくつもの解を評価した後、解を返すアルゴリズムである。

まず解くべき問題を状態: state)と状態変化(行動、: action)に分ける。 最初に与えられる状態を初期状態: initial state)といい、目的とする状態は最終状態(ゴール、: final state, goal)と呼ばれる。 初期状態から最終状態に至る、状態及び状態変化の並びが解である。 将棋ならば、盤面の駒の配置と指し手の持ち駒が状態であり、交互に駒を動かすことが状態変化に当たる。

問題を解く類として研究されているアルゴリズムの多くは探索アルゴリズムである。ある問題の考えられるあらゆる解の集合を探索空間と呼ぶ。力まかせ探索や素朴な(知識を用いない)探索アルゴリズムは、探索空間を探索する手法としては最も単純で直観的である。一方、知識を用いた探索アルゴリズムはヒューリスティクスを使って探索空間の構造に関する知識を利用し、探索にかかる時間を削減しようとする。

知識を用いない探索

知識を用いない探索(: uninformed search)アルゴリズムは、その問題の性質を考慮しない手法である。そのため汎用的に実装可能であり、抽象化のおかげで幅広い問題に同じ実装を適用可能である。問題は、探索空間が一般に非常に大きいため、問題が小さいものでもそれなりの時間がかかる点である。処理を高速化するため、知識を用いた探索だけを行う場合がある。

リスト探索

リスト探索(: list search)アルゴリズムは、おそらく最も基本的な探索アルゴリズムである。その目的は、リストから何らかのキーを持つ要素を探すことである。計算機科学では最もよく研究されている分野であり、それらのアルゴリズムの計算量もよく研究されている。

その中でも最も単純なアルゴリズムが線型探索であり、単純にリスト上の各要素を調べていく。その実行時間は O(n) であり、n はリスト上のアイテムの数だが、どんなリストでも適用可能である。

より洗練されたリスト探索アルゴリズムとして二分探索があり、実行時間は O(log n) である。データが多ければ多いほど線型探索よりも性能がよくなるが、探索の前にソートしておく必要があり、またランダムアクセスが可能でなければならない。

特別なデータ構造を使った別の探索法として、平衡2分探索木を使った探索があり、実行時間は二分探索と同様にO(log n) である。これは、二分探索の考え方を拡張して、挿入と削除を高速化できるようにしたものである。

内挿探索は分布が偏っていないソートされた大きなリストでは二分探索よりも性能が良いが、最悪ケースでは O(n) となる。

グローバーのアルゴリズム量子コンピュータ用アルゴリズムで、ソートされていないリストでの線型探索に対して二乗の性能向上をもたらす。しかし、量子コンピュータはまだ実用化されていない。

ハッシュテーブルもリスト探索に使われ、実行時間は平均ケースでO(1)であるが、必要とする領域は他のデータ構造よりも多く、最悪ケースでは O(n) もかかる。リスト探索のデータ構造については、ハッシュテーブルも参照されたい。

なお、線型探索、二分探索、平衡2分探索木といったリスト探索アルゴリズムの多くは、若干のコスト追加で、与えられたキー以下(あるいは以上)の全ての値を探すことができる。このような探索を「範囲探索(: range search)」と呼ぶ。例外はハッシュテーブルであり、そのような探索を効率的には行えない。

文字列探索

文字列内のパターンを探索する。接尾辞木などのデータ構造で効率化することもある。

複数のファイルにまたがる物を全文検索という。

木探索・グラフ探索

木探索・グラフ探索共通

グラフ探索固有

木探索: tree search)アルゴリズムは、探索技法の中心である。のノードを探索するもので、最初から木が明示される場合と動的に木を生成する場合がある。基本原則は、データ構造から1つのノードを選び、その後者を調べてデータ構造に追加していく。このデータ構造の操作にあたっては、同じレベルのノードから順に見ていく幅優先探索と葉ノードまで見ていってバックトラックする深さ優先探索がある。

グラフ理論の問題の多くは、グラフ探索アルゴリズムで解くことができる。いくつかの物は木探索アルゴリズムを拡張したものと見ることもできる。

知識を用いた探索

知識を用いた探索(: informed search)では、問題に固有のヒューリスティクス(評価関数)を補助として使う。良いヒューリスティックを使えば、探索は劇的に改善される。 知識を用いた探索アルゴリズムの多くは木探索である。最良優先探索A* などがある。知識を用いない探索と同様、これらはグラフ向けにも拡張可能である。

メタヒューリスティクス

汎用的に使えるヒューリスティクスをメタヒューリスティクスという。

連想配列

問題に関する知識に基づいてハッシュ関数を定義したハッシュテーブルは知識を用いたリスト探索アルゴリズムである。

敵対探索

チェスのようなゲームでは、考えられる全ての「手」で構成されるゲーム木があり、この木を使って最良の手を捜すことができる。この種の問題は、相手も自分にとって最良の手を選択すると想定するという興味深い特徴がある。そのため、ゲームを行う人工知能などでは、ミニマックス法、探索木の刈り込み、アルファ・ベータ法といった特徴的な探索アルゴリズムを使う。

制約充足

制約充足問題を解くアルゴリズムも探索アルゴリズムの一種である。この場合、経路を探し出すのではなく、一連の変数群の値の組合せを探す。変数の処理は任意の順序で可能であるため、木探索アルゴリズムでは効率的ではない。解法には問題の自由度を利用した組合せ最適化バックトラッキングが使われる。バックトラッキングでの一般的な技法として制約伝播(: constraint propagation)がある。他にも競合を最小化する局所探索アルゴリズムもある。

関連分野

関連項目

関連図書

  • 宝崎隆祐, 飯田耕司:「捜索理論における確率モデル」、コロナ社、ISBN 978-4339028331(2019年3月)。※ORの意味での探索理論である。
  • 今野紀雄:「量子探索 ―量子ウォークが拓く最先端アルゴリズム- 」、近代科学社、ISBN 978-4764906303(2021年3月2日)。
  • 阪田義隆:「クリギング入門 - 空間データ推定の確率論的アプローチ -」、コロナ社、ISBN 978-4339052756(2021年4月5日)。※ORの意味での探索理論である。

外部リンク


検索アルゴリズム

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/03/18 00:16 UTC 版)

Archive-Box (PortableApps)」の記事における「検索アルゴリズム」の解説

クライアント (コンピュータ)アプリケーションは、ファイル検索重視した設計思われユーザインタフェース (user interface)も通常状態では、ファイル検索バーのみの表示となり、ファイル名及び、ファイル内のテキスト文字列検索する使用となっている。検索結果徹底的に見つけたファイル絞り込むために、スペース区切りでAND検索実行するバイナリファイル中に含まれる文字列検索実施されない

※この「検索アルゴリズム」の解説は、「Archive-Box (PortableApps)」の解説の一部です。
「検索アルゴリズム」を含む「Archive-Box (PortableApps)」の記事については、「Archive-Box (PortableApps)」の概要を参照ください。

ウィキペディア小見出し辞書の「検索アルゴリズム」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「検索アルゴリズム」の関連用語

検索アルゴリズムのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



検索アルゴリズムのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの探索 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、WikipediaのArchive-Box (PortableApps) (改訂履歴)、情報検索 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS