深さ優先探索

読み方、または別称:ふかさゆうせんたんさく

深さ優先探索(depth-first search)、略して DFSはバックトラック法とも言うが、ノードのツリーやグラフを徹底的に探索するためのアルゴリズムである。なお、このアルゴリズムはツリーのルートから始まり、上から下へバックトラックするまで可能な限り探索を行うので、縦型探索とも呼ばれる。

深さ優先探索は、探索対象のツリーの最初のノードから、目的のノードが見つかるか、もしくは子がないノードに行き着くまで続けて行く探索である。その後はバックトラックで探索の終わっていない一番近いノードまで戻る。

ただし、メモリからはみ出すような大規模なグラフを探索する場合、深さ優先探索は探索ツリーのパスの長さが長くなりすぎて結果的に探索が終わらない場合がある。つまり、辿りついたノードを記憶する方法が十分なメモリ量がない場合には使えない。

しかし、このような場合は、ツリーの深さを段階的に増やして探索する反復深化深さ優先探索(iterative deepening depth-first search)と呼ばれるアルゴリズムを使うことで解決することができる。

ページトップへ戻る

話題の用語~今ホットな用語をご紹介

ITと社会用語辞典

ワークロード

ワークロードとは、システムのパフォーマンスを適正な状態に保つための指標のこと。

インターネット用語辞典

ライフログ

ライフログとは、人間の活動の記録(行動履歴)をデジタルデータとして記録すること、およびその記録のことである。

ページトップへ戻る