Beam Searchの基礎知識-広さ優先および深さ優先検索

概要
深さ優先と広さ優先の探索方法を紹介した.
基本概念
Openテーブルは、未アクセスのパスcloseテーブルを保存し、アクセスしたパスを保存し、デッドサイクルに入ることを防止します.
具体的なアルゴリズム
ある開始ノードからすべての到達可能な頂点にアクセスすることは、次の図ではH点からC点までどのように遍歴したいかなど、多くのシーンで非常に役立ちます.
具体的な手順

HからHの直接後継{B,D,L}を見つけて3つの候補経路{H−>B,H−>D,H−>L}を構成し,このとき{B,D,L}はopen vertices

となる.

open vertices(およびそれらが属するパス)をopenテーブルに入れます.

openテーブルからvertexを選択してopenテーブルを除去し、このvertexの後続を生成する

例えばLを選択し,{M,F,H},

に続く

Hは既にアクセスされているので、openテーブルに入れないとデッドサイクルになるので、このときopenテーブルに{B,D,M,F}がデッドサイクルを防止するために1つのcloseテーブルがあり、すでにアクセスされたポイントが記録され、1つのポイントがcloseテーブルに入ると、2回目の

にはアクセスされない

は、ターゲット頂点が見つかるか、ターゲット頂点が見つからない

に戻るかを引き続き知る.
注意:広さ優先か深さ優先かはopenテーブルからのデータアクセスによって完全に決定されます*openテーブルが先進的であれば後出であれば深さ優先*openテーブルが先進的であれば後出であれば広さ優先です
サンプルおよびダミーコード
深度優先サンプル(Depth Priority Samples)
Vertex visited (and hence closed)
Open list (stack top at left)
H
B D L
B
D D L
D
G J D L
G
J J D L
J
E I M J D L
E
K I M J D L
K
I M J D L
I
F M J D L
F
A L M J D L
A
L M J D L
L
M M J D L
M
C M J D L
C
M J D L
デプス優先疑似コード

/* initialization */
queue openList = { startVertex }

/* loop */
while ( closedNodes != numberOfNodes && !openList.empty())
{
  closingVertex = openList.dequeue();
  increment number of closedNodes;

  for each non-closed vertex not in the openList
     and with an edge to it from closingVertex
  {
    openList.enqueue( vertex );
  }

}

広さ優先類似
参考資料
http://jhave.org/algorithms/graphs/depthbreadth/depth-breadth.shtml