A^*アルゴリズムを用いたn×m最短路問題の効率的解法
スポンサーリンク
概要
- 論文の詳細を見る
いろいろなネットワークにおいて、複数の始点集合と複数の終点集合がある場合に、すべての始点終点の組に対して最短路を求めることは、多くの問題を解く際に非常によく必要とされるものである。例えば、巡回セールス問題や車両配送問題などの多くの重要な問題において、そのような最短路問題を解くことが求められることが非常に多い。本論文では、そのようなn×m最短路問題を解くのに、A^*アルゴリズムの概念を用いてダイクストラ法を2通りの方法で効率化している。更に、実際の道路ネットワークを用いた実験によって、それらのアルゴリズムの性能と性質を検証している。
- 1998-05-20
著者
関連論文
- cDNAマッピングのためのマッチング連鎖アルゴリズム
- スプライスト・アライソメントに基づいたcDNAライブラリの正確なクラスタリング・アルゴリズム
- モチーフ検索アルゴリズムと遺伝子同定への応用
- アルファベットサイズの大きな木のSuffix Treeについて
- 生物学的配列の組換えの解析のための新しいアプローチ
- 電子マネーシステムにおける最適なオンラインアルゴリズム
- A^*アルゴリズムを用いたn×m最短路問題の効率的解法