様々なデータ構造が発表されているが、大きく分けると「枝長に依存してしまう」バケット系か、「安定している」ヒープ系のどちらかの特徴を持っている。そのため、短所を補うために、複数組み合わせたデータ構造も多く存在する。しかしながら、1レベルバケット法、2分ヒープ法はいづれもシンプルであるために最適化しやすく、そういった組み合わせのデータ構造に引けを取らない。
よって以下のような場合それぞれを適宜選択すべきであるといえる。
バケット系
・用いるグラフが道路ネットワークのような特性を持っている場合。
ヒープ系
・用いるグラフの特性が分からない場合。
・メモリ使用量を小さくしたい場合。
つまり、複数のデータ構造を組み合わせた新しいデータ構造を作成するというよりも、グラフの特性を読み取り適宜自動的に選択できるようなアルゴリズムが望ましいといえる。しかしグラフ読み込みの段階では、現在以下の情報しか取得していないが、自動選択機能の為に新たに取得しなければならない情報があるとすれば、そのコストがボトルネックになるという本末転倒になってしまいかねない。
■現在の実装で取得しているもの
・点数
・枝数
・最短枝数
・最長枝数
■比較的に容易に追加できるもの
・最大枝数(1点から出てくる最も多い枝の数)
こちらも考えていかなければならない。
よって以下のような場合それぞれを適宜選択すべきであるといえる。
バケット系
・用いるグラフが道路ネットワークのような特性を持っている場合。
ヒープ系
・用いるグラフの特性が分からない場合。
・メモリ使用量を小さくしたい場合。
つまり、複数のデータ構造を組み合わせた新しいデータ構造を作成するというよりも、グラフの特性を読み取り適宜自動的に選択できるようなアルゴリズムが望ましいといえる。しかしグラフ読み込みの段階では、現在以下の情報しか取得していないが、自動選択機能の為に新たに取得しなければならない情報があるとすれば、そのコストがボトルネックになるという本末転倒になってしまいかねない。
■現在の実装で取得しているもの
・点数
・枝数
・最短枝数
・最長枝数
■比較的に容易に追加できるもの
・最大枝数(1点から出てくる最も多い枝の数)
こちらも考えていかなければならない。
※コメント投稿者のブログIDはブログ作成者のみに通知されます