時間依存最短路問題に対するA^*アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
時間依存最短路問題は,有向グラフG,各辺e=(v,w)における非負な通過時間関数c_e(t)(但しtはvの出る時刻),始点s,終点dと出発時刻t_0が与えられたときに,時刻t_0にsから出発しdに到着するまでの最も速い経路を計算することで定式化され,古典的な最短路問題(c_e定数)の一般化となっている.この問題に対し,Dijkstra法の拡張版(Dreyfus'69)が提案されて以来,約40年間にわたる研究にも関わらず目覚ましい方法が知られなかったが,本論文は新たに一般化A^*アルゴリズムを提案し,さらにその応用として,前処理を用いるALTアルゴリズム(Goldberg and Harrelson'05)の一般化も与える.
- 2008-05-20
著者
関連論文
- MAX-2-SATに対する分枝限定法
- 矩形パッキング問題に対する厳密解法
- MAX-2-SATに対する分枝限定法
- グラフの極大成分を用いた生物ネットワークの解析(遺伝子発現・ネットワーク)
- 根付き三角化平面的グラフの列挙
- ビーコン配置問題と対偶問題に対する効率的近似アルゴリズム
- 最小費用枝架設問題に対する近似解法
- P2Pシステムのための深さ最小木の構築について
- P2Pシステムのための深さ最小木の構築について(マルチメディア(システム/通信/ネットワーク),放送通信連携サービスとその品質,一般)
- P2Pシステムのための深さ最小木の構築について(マルチメディア(システム/通信/ネットワーク),放送通信連携サービスとその品質,一般)
- P2Pシステムのための深さ最小木の構築について(マルチメディア(システム/通信/ネットワーク),放送通信連携サービスとその品質,一般)
- 容量付木状経路問題に対する近似解法
- 反復構成特徴に基づいた分類器の実データへの拡張
- 特徴ベクトルに基づく木状の化学分子の列挙アルゴリズム(セッション5)
- 特徴ベクトルに基づく木状の化学分子の列挙アルゴリズム(セッション5)
- 光バースト交換網における専用波長を用いた全域木形成による衝突回避法
- ビーコン配置問題と対偶問題に対する効率的近似アルゴリズム
- パス構造グラフにおける納期違反コスト最小化選択的配達スケジューリング(機械要素,潤滑,工作,生産管理など)
- 食品の袋詰め最適化問題に対する動的計画法(機械要素,潤滑,工作,生産管理など)
- 時間依存最短路問題に対するA^*アルゴリズム
- 組合せの効率的な生成法 (計算機科学とアルゴリズムの数理的基礎とその応用)
- A*アルゴリズムのための実用的高速化手法
- k-辺連結性を保存する疎なグラフを求める効率の良いNCアルゴリズム
- 平面無向グラフで2番目に短い経路を求めるアルゴリズム
- サイクル上の忌避型施設配置ゲームにおける,3-候補地もしくは4-候補地の戦略耐性メカニズム (最適化の基礎理論と応用)