最短路 Online Solver だが、現在はユーザが始点、終点を指定して最短路を求める度に、ダイクストラ法のプログラム(ヒープ)を呼び出して、DIMACS データ(グラフや座標)を読み込んでから、最短路を求めるという手順にしている。そのため大規模な地図(全米 USA) などでは、実行に1分ぐらいの時間を要する。この時間の中では、ダイクストラ法そのものの実行時間よりも、巨大なデータを読み込んで、専用のデータ構造に変換する時間が多くを占めている。実は query 自体の時間は少ないので、様々な工夫によって高速化できる余地がたくさんある。いろいろと試して段階的に高速化されていくことになろう。
このブログの人気記事
最新の画像[もっと見る]
- 新サーバ室構築中 2年前
- 新サーバ室構築中 2年前
- 新サーバ室構築中 2年前
- フロー補完問題と線形計画問題 3年前
- 研究室紹介ビデオ 3年前
- 格子暗号の安全性を検証する最短ベクトル問題に対する解読 3年前
- 今年(2020年)の主な成果 4年前
- 今年(2020年)の主な成果 4年前
- 今年(2020年)の主な成果 4年前
- Graph500 情報更新:2020年11月 4年前
「Weblog」カテゴリの最新記事
- 自己紹介と重要リンク
- Metaの大規模言語モデル「Llama」の累計ダウンロード数が3億5000万回に迫る
- 液晶工場を半導体後工程へ大転換、シャープやインテルにTSMCも
- 三菱電機、新デジタル基盤「Serendie」を発表--データ関連ビジネスを拡大へ
- 国内企業のGPUクラウドサービス利用率は5.4%、うち約9割は海外サービスを利用~GM...
- IOWN、日台間3000kmで17msecの超低遅延通信を実現
- ゲーム「DOOM」のプレイ画面をリアルタイムに生成するAI プレイも可能 米Google...
- NHR Center@ZIB
- なぜネコは閉じているドアを嫌うのか?
- 後継者不足の“COBOL言語”を生成AIに引き継ぎ 政府や銀行の“いにしえのプログラム”...