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

始点から探索すると非常に大きな範囲を探索しなければならないことが、プロットした図から分かる。この例では終点から探索すると先ほどよりも多少狭くなり、両方向から探索するとさらに狭くなる。実行時間も「Forward > Backward > Bidirectional」となる。

bidirectional-search では forward-search と backward-search を交互に行うので、探索した点の数は同数、枝の数はほぼ同数となっている。この場合では backward の方に傾斜を付けた方が良さそうだが、事前に点の位置が分かっていないと難しいだろう。それよりも、Forward の半分程しか探索していないにも関わらず、これはちょっと遅すぎることが気になる。

Graph: USA-rowd-d.NY.gr (264,346 nodes 733,846 arcs)
Query: 始点 44721, 終点 4895
Queue: 2-ary heap

               scaned-nodes  scaned-arcs  execution-time
Forward             245,151      688,060        39 msec.
Backward            186,055      528,281        30 msec.
Bidirectional       131,858      364,756        29 msec.

[Bidirectional]
scaned-node     131,858 (= 65,929 + 65,929)
scaned-arcs     364,756 (= 185,430 + 179,326)
execution-time  29 msec.