幅優先探索におけるTop Down方式とBottom Up方式について (original) (raw)

グラフアルゴリズムにおける幅優先探索(Breadth Width Search: BFS)というのは、グラフのスタート・ノードから始まって、ノードに隣接するノードを探索してから、さらにそのノードに隣接するノードを探索するというアルゴリズムだ。 グラフアルゴリズムの授業において、最も基本的なアルゴリズムであるものの、その最適化にはいろんな方法があって勉強になる。

例えば、グラフアルゴリズムのベンチマークであるGAPでは、ベンチマークの1種としてBFSが用いられている。

github.com

BFSのアルゴリズムの説明について、以下の文献が詳細を説明してくれている：

https://arxiv.org/pdf/1508.03619

P.11あたりに、BFSのアルゴリズムの説明がなされている。機械翻訳でそのまま翻訳してみる：

幅優先探索（Breadth-First Search: BFS）は、現在最先端の方向最適化アルゴリズム[4]を実装している。

つまり、このGAPを開発した本人が開発したBFSの最適化がそのまま実装されているという訳だ。

[4] : Scott Beamer, Krste Asanovi´c, and David A. Patterson. Direction-optimizing breadth-first search. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2012.

これは、グラフの探索におけるTop DownのアプローチとBottom Upのアプローチを組み合わせたものになっている。

BFSにおけるTop Downのアプローチというのは非常に一般的なアプローチで、これはいろんな教科書に出てくる手法だ：

一方で、このTop Downアルゴリズムは並列化が行いにくいという弱点がある。 というよりは、Top Downアルゴリズムの特徴として、Top Downは探索済みの頂点から次の頂点を探索するが、複数の探索済みの頂点が同じ未探索の頂点を探すような状態になると効率が悪い。このような状況が発生しうる可能性がある。

そこで、Bottom Upという手法がある。Bottom UpはTop Downの逆で、未探索なノードから逆方向(ノードの親の方向)に探索していき、親がすでに探索済みであればその親の子供として探索済みとする。

https://scottbeamer.net/pubs/beamer-sc2012.pdf より引用

具体的には、以下の論文の図が分かりやすい。

https://mnakao.net/data/2020/HPC175.pdf

図は本論文より引用

つまり、Top DownとBottom Upを使い分けるのが良いということになり、実際の実用アルゴリズムでもこの2つを状況に応じて使い分けるのが一般的なようだ。