Moore, Breadth First Seach
Edward F. Moore の Breadth First Seach Algorithm。
[Original]Edward F. Moore, "The shortest path through a maze": Proceedings of the International Symposium on the Theory of Switching, pages 285-292 Harvard University Press, 1959.
Algorithm MOORE [G=(V, E), s, e] 開始Vertex sから終了Vertex eへの、 接続グラフ G =(V,E)の最短路を決定するAlgorithm。 入力: ・開始Vetexを s、終了Vertexを e 全てのEdge (i,j)で長さl(i,j)=1の接続グラフを、G=(V,E)とする。 ・最初は全てのVertexにラベルがない。 出力: ・G=(V,E)の中の最短路 s → e 手続き: 1.sにラベル0をつける 2.i=0 とする。 3.ラベル iが付いているVertexに隣接する、 全てのラベル付けされていないVertexを検索する 4.見つかったVertexにラベル i+1 をつける 5.if(終了端 eにラベルがつけられた) ラベルの逆探索により、最短路を導出: k(eのラベル)、k-1, ..., 0とラベルを探索していき、 各該当Vertexを出力する。 else i=i+1 と増やし、Step 3へ戻る
計算量、メモリ使用量のOrderはそれぞれ次。
・計算量Order ...O(Edge数)
(sから順にVertexを移動し、隣接Vertexを検索していく手続きが、"2×Vetex回"行われる。)
・メモリ使用量Order...O(Vertex数)
(Vertexにつけるラベルの成分数)
巡回セースルマン問題(Traveling Salesman Problem)で、全てのEdge(辺)の長さが 1 の場合の解法。(※巡回セールスマン問題:与えられたグラフの最短Hamilton経路(グラフの全てのVertex(頂点)を通る経路)を決定する問題)
[Reference]:
最適化とグラフ理論 (技術者のための高等数学)
Introduction to Algorithms, Second Edition
アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)