最短路問題: 双方向探索(bidirectional search) - 3

さて前回の記事ではそこそこうまくいった例を示したが、それにしてももう少し性能が出てもいいのでは？という疑問が残る。思い当たる原因はいくつかあるのだが、まずはグラフの規模を疑い、今回は全米グラフを用いる。各クエリに対応した forward-search(F-time), backward-search(B-time), bidirectional-search(D-time) の実行時間をまとめる。

Graph : USA-road-d.USA.gr (23,947,347 nodes 58,333,344 arcs)
Query : P2P x 10
CPU   : Intel(R) Xeon(R) CPU X5460 @ 3.16GHz

Query[0] (17261435, 8424294) のように近い場合では、どれも同程度の実行時間で終了する。

Query[8] (18549540, 3230879) のようにうまく探索範囲を狭ませることのできる場合では、forward-search に比べて bidirectional-search の方が効率的ではある。冷静に考えると backward-search の方が良いが。

Query[9] (957498, 10453327) のように遠い場合では、探索範囲自体は狭まっているのだが、実行時間はむしろ増えてしまっている。