英: exploration、search、probing、explore、search、probe、exploratory
関: 検索、探す、触針、審査、ゾンデ、探究、探索子、探索性、探触子、調査、プローブ、サーチ

WordNet

question or examine thoroughly and closely (同)examine
a flexible slender surgical instrument with a blunt end that is used to explore wounds or body cavities
an exploratory action or expedition
an investigation conducted using a flexible surgical instrument to explore an injury or a body cavity
an inquiry into unfamiliar or questionable activities; "there was a congressional probe into the scandal" (同)investigation
examine physically with or as if with a probe; "probe an anthill" (同)dig into, poke_into
travel to or penetrate into; "explore unknown territory in biology"
examine (organs) for diagnostic purposes
examine minutely
serving in or intended for exploration or discovery; "an exploratory operation"; "exploratory reconnaissance"; "digging an exploratory well in the Gulf of Mexico"; "exploratory talks between diplomats" (同)explorative
subject to a search; "The police searched the suspect"; "We searched the whole house for the missing keys"
an operation that determines whether one or more of a set of items has a specified property; "they wrote a program to do a table lookup" (同)lookup
the activity of looking thoroughly in order to find something or someone (同)hunt, hunting
an investigation seeking answers; "a thorough search of the ledgers revealed nothing"; "the outcome justified the search"
boarding and inspecting a ship on the high seas; "right of search"
the examination of alternative hypotheses; "his search for a move that would avoid checkmate was unsuccessful"
search or seek; "We looked all day and finally found the child in the forest"; "Look elsewhere for the perfect gift!" (同)look
try to locate or discover, or try to establish the existence of; "The police are searching for clues"; "They are searching for the missing man in the entire county" (同)seek, look for
to travel for the purpose of discovery (同)geographic expedition
a careful systematic search
a systematic consideration; "he called for a careful exploration of the consequences"

PrepTutorEJDIC

(傷の深さを調べる)さぐり針 / (…を)厳密に調べること,精査《+『into』(『for』,『at』)+『名』》 / (また『space probe』)(ロケットの)宇宙探測機 / …‘を'厳密に調べる / 〈傷〉‘を'さぐり針で調べる / (…を)厳密に調べる《+『into』(『for』,『at』)+『名』》
〈未知・未調査の場所〉‘を'『探検する』,実地調査する / …‘を'『詳しく調べる』,調査する / 探検する
探検の;調査の
(…を求めて)〈ある場所・人の体など〉‘を'『くまなく捜す』,撤底的に捜す《+『名』+『for』+『名』》 / …‘を'『綿密に調査する』(probe) / (…を)綿密に調査する《+『into』+『名』》 / (…を求めて…を)『くまなく捜す』《+『through』+『名』+『for』+『名』》 / 『捜索』;調査;(を)捜すこと《+『for』(『of』)+『名』》
(未知・未調査の場所の)『探検』,『実地調査』《+『of』+『名』》 / (問題の)探索,調査《+『of』+『名』》

Wikipedia preview

出典(authority):フリー百科事典『ウィキペディア（Wikipedia）』「2014/01/16 01:03:52」(JST)

wiki ja

探索（たんさく）とは、何か問題を解くに当たって、有効な解析的な解法を用いることのできない、あるいは用いないときに、実際に試行錯誤することによって解を得ようとする行動のことである。表における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
MTD(f)
レコメンダシステム

外部リンク[編集]

Self-Guided Lesson on Uninformed Search ウィキバーシティ

Japanese Journal

多発性硬化症の動物モデル : 横断的アプローチによる病態解明と治療標的の探索 (特集多発性硬化症と視神経脊髄炎 : 基礎・臨床研究の最新知見) -- (基礎研究の進歩)

大木伸司,山村隆
日本臨床 72(11), 1935-1940, 2014-11
NAID 40020241344

分枝限定法における新たな探索法の提案 (特集知識情報処理技術の最新動向および一般)

山口一章,斎藤寿樹,増田澄男
人工知能基本問題研究会 95, 1-5, 2014-10-10
NAID 40020236976

領域ベースのステレオ対応点探索のための「標準化係数フィルタ」

西卓郎,高瀬竜一,吉見隆 [他]
計測自動制御学会論文集 50(10), 693-702, 2014-10
NAID 40020241138

Related Pictures

★リンクテーブル★

リンク元	「医療面接」「調査」「exploration」「probing」「search」
拡張検索	「探索行動」「探索子」「探索医療」「探索反射」
関連記事	「索」