最短路 FAQ

我々の最短路研究に関する FAQ 集を公開した。２ページ目のデモ画面とは最短路 Online Solver のことになる。

http://sdpa.indsys.chuo-u.ac.jp/~fujisawa/ss-faq.pdf

大規模最短路問題に対する高速&高性能計算システム

技術の概要
大規模なネットワーク上で二点間の最短路を求める最短路問題は非常に幅広い応用が存在する。例えば実社会における様々な大規模な交通データ（特に道路）に対する経路検索、特にカーナビゲーションシステムや GoogleMaps 上での経路検索などが有名である。最短路問題に対してはダイクストラ法というアルゴリズムが用いられるが、データ構造やメモリ階層構造を考慮した実装上の工夫により世界最高速レベルの速度、安定性、低メモリ消費などの特性を備えたソフトウェアの作成に成功した。またクラウドコンピューティングの技術を用いてユーザからの負荷に応じて自動的に計算サーバを増減する最短路計算システムの開発にも成功した。

従来技術に対する新規性・優位性
1: 世界最高レベルの性能を持った最短路計算エンジン
2: 拡張性の高いアルゴリズムとデータ構造により様々な条件を追加することが可能
3: クラウドコンピューティングの技術による計算サーバの自働増減