探索のソースを表示

'''探索'''（たんさく）とは、何か問題を解くに当たって、有効な解析的な解法を用いることのできない、あるいは用いないときに、実際に試行錯誤することによって解を得ようとする行動のことである。
表における1次元配列の要素を調べることであり、そのための[[アルゴリズム]]は探索アルゴリズムと呼ばれ、様々なものが考えられている。

もともと[[機械学習]]と並んで[[人工知能]]の分野のアルゴリズムであるが、現在はその他の分野にも応用されている。

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

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

==考え方==
まず解くべき問題を'''状態'''と'''状態変化'''に分ける。

将棋ならば、盤面の駒の配置と指し手の持ち駒が状態であり、交互に駒を動かすことが状態変化に当たる。
最初に与えられる状態を初期状態といい、目的とする状態は最終状態と呼ばれる。
初期状態から最終状態に至る、状態及び状態変化の並びが解である。

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

== リスト探索 ==
* [[線形探索]]
* [[二分探索]]
* [[内挿探索]]

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

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

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

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

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

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

[[ハッシュテーブル]]もリスト探索に使われ、平均ケースで[[定数時間]]しかかからないが、必要とする領域は多く、最悪ケースでは O(''n'') もかかる。リスト探索のデータ構造については、[[ハッシュテーブル]]も参照されたい。

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

== 木探索 ==
* [[幅優先探索]]
* [[深さ優先探索]]
* [[反復深化深さ優先探索]]
* [[深さ制限探索]]
* [[双方向探索]]
* [[均一コスト探索]]

[[木構造 (データ構造)|木探索]]（tree search）アルゴリズムは、探索技法の中心である。[[木 (数学)|木]]のノードを探索するもので、最初から木が明示される場合と動的に木を生成する場合がある。基本原則は、[[データ構造]]から1つのノードを選び、その後者を調べてデータ構造に追加していく。このデータ構造の操作にあたっては、同じレベルのノードから順に見ていく[[幅優先探索]]と葉ノードまで見ていってバックトラックする[[深さ優先探索]]がある。木探索の他の例として、[[反復深化深さ優先探索]]、[[深さ制限探索]]、[[双方向探索]]、[[均一コスト探索]]などがある。

== グラフ探索 ==
* [[ダイクストラ法]]
* [[クラスカル法]]
* [[最近傍法]]
* [[プリム法]]
* [[最大隣接順序]]
* [[最小次数順序]]

[[グラフ理論]]の問題の多くは、グラフ探索アルゴリズムで解くことができる。例としては、[[ダイクストラ法]]、[[クラスカル法]]、[[最近傍法]]、[[プリム法]]などがある。これらは木探索アルゴリズムを拡張したものと見ることもできる。
また、連結度に関するアルゴリズムにおいて[[最大隣接順序]]や[[最小次数順序]]が用いられる。

== 知識を用いた探索 ==
* [[ハッシュテーブル]]
* [[最良優先探索]]
* [[A*]]

知識を用いた探索（informed search）では、問題に固有の[[ヒューリスティクス]]を補助として使う。よいヒューリスティックを使えば、探索は劇的に改善される。

知識を用いたリスト探索アルゴリズムとしてよく知られているものは数少ない。例えば、問題に関する知識に基づいてハッシュ関数を定義したハッシュテーブルがそうである。知識を用いた探索アルゴリズムの多くは木探索用である。[[最良優先探索]]や [[A*]] などがある。知識を用いない探索と同様、これらはグラフ向けにも拡張可能である。

== 敵対探索 ==
* [[ミニマックス法]]
* [[アルファ・ベータ法]]
* [[分枝限定法]]

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

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

==その他==
* [[文字列探索]] - [[文字列]]内のパターンを探索する。[[接尾辞木]]などのデータ構造で効率化することもある。
* [[遺伝的アルゴリズム]] - 探索空間を縮小させるヒューリスティクスとして[[進化]]の考え方を使う。
* [[ソート]] - 一部の探索アルゴリズムで必須となる。
* [[焼きなまし法]] - [[確率]]的探索アルゴリズムの一種
* [[タブーサーチ]] - 探索が局所解で停滞するのを防ぐ技法
*[[最小コスト探索]]
*[[山登り法]]
*[[Negascout|NegaScout]]
*[[MTD-f|MTD(f)]]
*[[レコメンダシステム]]


== 関連分野 ==
* [[人工知能]]

== 関連項目 ==
* [[検索]]
* [[選択アルゴリズム]]
* [[ノーフリーランチ定理]]
* [[秘書問題]] - 不完全な情報を伴う[[オンラインアルゴリズム|オンライン]]探索問題の一種であり、統計的な最適化戦略。
* [[捜索]]

== 外部リンク ==
* [http://en.wikiversity.org/wiki/Uninformed_Search_Project Self-Guided Lesson on Uninformed Search] ウィキバーシティ

[[Category:人工知能|たんさく]]
[[Category:検索アルゴリズム|*たんさく]]