枝長による実行時間の変化 その３。

前回の続きでもあるが、他のグラフで同じような実験をしてみた。

用いたグラフは USA-road-d.FLA.gr で、点数 1,070,376 、枝数 2,712,798 となっている。
今回の heap 法と bucket法の切り替えは n = 2 付近である。前回の結果も踏まえてみると、n = 2～3 とも言えるのだが、各時点でのバケットサイズ（最大枝長）も踏まえながら見ていくと、実は点数とバケットサイズが等しくなる地点ではないかと気づいた。

まだ NY.gr と FLA.gr の２つしか試していないのだが、道路ネットワークにおいては、「heap 法と bucket 法の切り替えポイント」は、「bucket サイズと点数が等しくなる」付近であるかもしれない。用いているグラフは実際の道路ネットワークを DIMACS フォーマットに変換したものなので、特性の似ているグラフ(特に USA-road-d.XXX.gr)であれば、同様の結果を得られるかもしれないため、より大きな全米グラフ等で、試していこうと思う。

ちなみに、この点はメモリ要求量の点からも切り替えポイントになっており、ここでデータ構造を切り替えることで、速度とメモリ要求量の両方の面で有効である。