前回の深さ優先探索に続いて今回は幅優先探索を紹介します。
幅優先探索 (Breadth First Search) はノードの子孫の中から世代が近い者を優先して探索していくアルゴリズムで、最短経路探索などに使われます。
このアルゴリズムの手順は以下のようになります。
1.探索中のノードを格納するキューを用意する
2.探索のルートとなるノードをキューに格納する
3.キューが空なら終了する
4.キューからノードを一つ取り出す (さらに…)
2010年6月8日 | カテゴリー：アルゴリズム
前回まではリスト探索を行ないましたが、今回からはツリー探索を行ないます。
今回紹介するのは深さ優先探索 (DFS, Depth-First Search) です。
深さ優先探索とはその名のとおり、ツリー構造の深さの方向を優先して探索を行なうアルゴリズムです。深さ優先探索は再帰処理と相性がよく、次のように手順を再帰的に繰り返すだけで実装することができます。 (さらに…)
2010年5月11日 | カテゴリー：アルゴリズム
前回に引き続き、今回もリスト探索のアルゴリズム 2分探索 を紹介します。
このアルゴリズムではリスト内から探索対象を探すのに O(log n) の計算量しかかかりません。
ただし、前提条件として、リストがランダムアクセス可能で、かつソート済である必要があります。
アルゴリズムの内容は至って単純で、探索対象とリストの探索範囲の中央にある要素を比較します。このとき (さらに…)
2010年4月21日 | カテゴリー：アルゴリズム
