双対変数を用いたA^*両方向探索アルゴリズムと経路誘導における最短路問題
スポンサーリンク
概要
- 論文の詳細を見る
最短路問題は,あらゆる分野での応用が考えられる最も基本的な問題の1つであり,近年急速に普及しつつある経路誘導システムとも深いつながりを持っている.本研究では,2点間の最短路問題に関して,ダイクストラ法・A^*アルゴリズム・両方向探索といった従来のアルゴリズムを概観し,新しい手法に基づくA^*両方向探索アルゴリズムを提案する.また,実際の道路網のデータにこのアルゴリズムを適用した結果を基に,実際の効率及び特徴について論じる.
- 社団法人情報処理学会の論文
- 1994-07-22
著者
-
下浦 弘
住友電気工業
-
西村 茂樹
住友電気工業
-
天目 健二
住友電気工業
-
池田 崇博
東京大学理学部情報科学科
-
今井 浩
東京大学理学部情報科学科
-
橋本 武夫
住友電気工業
-
三藤 邦彦
住友電気工業
-
今井 浩
東京大学理学系研究科情報科学専攻 Erato今井量子計算機構プロジェクト 科学技術振興事業団
関連論文
- 難読化コンパイラのユーザによる保護強度調整機構(コンピュータシステム技術,2009年並列/分散/協調処理に関する『仙台』サマー・ワークショップ(SWoPP仙台2009))
- FPGA基板を用いたモンテカルロ碁の高速化(アクセラレーションと回路設計,2009年並列/分散/協調処理に関する『仙台』サマー・ワークショップ(SWoPP仙台2009))
- 状態方程式に基づく市街地幹線道路の旅行時間予測
- 動的逆アセンブル手法の高速化(ハードウェアアクセラレーション,SWoPP佐賀2008-2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ)
- 高信頼性マルチホーミング通信方式(ネットワーク,SWoPP佐賀2008-2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ)
- 光ビーコンで収集した交通情報の解析とその応用の検討--交通の円滑化による経済的損失の低減を目指して
- 通過順序に基づく車群マッチングと旅行時間推定
- 2地点車両観測情報からの全域的交通流解析アルゴリズム
- 車両特徴量を用いた車群マッチングと旅行時間推定
- サイクル長の異なるサブエリア間の交通流の評価
- 車両配送問題のタブー探索による解法の実験的解析
- 地点相関手法による交通情報予測
- 双対変数を用いたA^*両方向探索アルゴリズムと経路誘導における最短路問題
- 経路誘導における最短路問題の解法について
- 簡潔データ構造による全文検索のハードウェアを用いた高速化(ハードウェアアクセラレーション,SWoPP佐賀2008-2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ)
- 分散共有メモリアクセスの優先度制御(ARC-9:並列処理2,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- トランザクショナルメモリのための性能評価手法(ARC-9:並列処理2,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- 連載：理学のキーワード : 第29回
- プログラミング言語MLのCUDA向け拡張
- SIMD型計算機向けループ自動並列化手法
- 動的推定によるプリフェッチ量最適化
- Webブラウザを用いた長距離データ転送の高速化
- 自動分散制御による動的な信号機制御パラメータ制御モデルの提案
- コヒーレントでないメモリシステムへのアーキテクチャ支援
- Ruby用仮想マシンにおけるAOTコンパイラ
- メニーコアプロセッサ向き共有キャッシュ配分方式
- マップ型履歴を用いたプリフェッチ方式とキャッシュ置換方式の協調動作
- 線形マトロイド・グラフアレンジメント・半順序での数え上げ問題に対する組合せ的・幾何的アプローチ
- 二分決定グラフのトップダウン構成法と並列化
- 超並列準汎用計算機GRAPE-DRによる重力多体問題シミュレーションおよびLU分解
- オフライン環境における多様性の高い実行時自己改変ソフトウェア(2010年並列/分散/協調処理に関する『金沢』サマー・ワークショップSWoPP2010)
- マルチエージェントモデルによる信号機オフセット制御法の提案
- 自動分散制御による動的な信号機制御パラメータ制御モデルの提案
- 日米間QoSによるLFN高速化実験と分散KVSの構築(研究発表,ネットワーク研究開発テストベッド運用・利用,一般)
- TCPによる長距離ディスク間データ転送の高速化
- Computational Geometry on Statistical Manifolds for Clustering : Extended Abstract (Models of Computation and Algorithms)
- 省ハードウェア資源のフィードバックつきハイブリッドプリフェッチ方式
- 省ハードウェア資源のフィードバックつきハイブリッドプリフェッチ方式
- 部分的試行に基づく動的共有キャッシュ分割方式
- GeForce GTX 280 vs. Cell
- 置換データの性質に着目した動的キャッシュパーティショニング
- 追い出しラインに着目したプリフェッチスロットリング手法
- フィードバックを用いたハイブリッド・プリフェッチ方式
- 量子計算の科学
- 量子計算の科学
- 量子計算の科学
- 量子計算の科学
- 量子計算の科学
- 量子計算の科学
- 量子エントロピーの離散構造
- 三角形分割の最適性と整数計画による定式化
- Optimality and Integer Programming Formulations of Triangulations in General Dimension
- 三角形分割の最適性と整数計画による定式化
- パケット喪失履歴に基づいたTCP幅輳制御方式(2010年並列/分散/協調処理に関する『金沢』サマー・ワークショップSWoPP2010)
- 複数の生物学的配列の準最適アラインメントについて
- 地理情報システムの標準化動向と参照モデル
- "Peter Shor : Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM Journal on Computing,Vol.26,No.5, pp.1484-1509, 1997 (20世紀の名著名論)
- 線形計画問題に対する乗法的罰金関数法の拡張
- バケット手法,Peano曲線を用いた平面マッチング,巡回セールスマン問題に対する近似算法の理論的評価
- 足切り横断ポリマトロイドに対するネットワーク算法
- 最大流算法の実際的評価
- 5.量子計算と最適化(量子情報処理パラダイム)
- 量子情報処理パラダイム : 1.量子計算の基礎
- 最短路算法の実際的評価と新バケット法
- ナビゲーションシステム
- 通過順序に基づく車群マッチングと旅行時間推定
- 通過順序に基づく車群マッチングと旅行時間推定
- RL-001 FPGAを用いた広帯域高遅延ネットワーク向けの利用可能帯域推定(L分野:ネットワーク・セキュリティ,査読付き論文)
- Euclid距離による凸多角形の多角形領域内へのmaximin配置問題とそれに関連した動的Voronoi図
- 4.先端グローバルR&D網の構築と国際協調アプリケーションの展開 : JGN2の国際連携活動(オープンリサーチ型次世代ネットワーク技術への挑戦-National Project JGN2 4年間のFact Sheets-)
- 高速道路の最適流入制御への進化計算手法の適用
- 交通流データによる突発事象検出アルゴリズム
- トラカンデータを用いた高速道路突発事象検出アルゴリズム
- 自動車 二次計画法を用いた高速道路流入制御アルゴリズムの開発
- 円弧接続コース上のロバスト自動操舵 -非線形低次元化スライディングモード制御器-
- 動的ランプ流入制御方式の高度化
- スライディングモードによる自動車の縦方向制御
- 低次元化スライディングモードと特異注視点による自動車の操舵制御
- 上空からの交通情報収集システムの開発
- 動的経路誘導に必要な旅行時間精度の検討と計測方法の評価
- 交通流シミュレ-ションを用いた動的経路誘導の評価
- 交通流シミュレーションを用いた動的経路誘導の評価
- ナビゲーションシステムの評価における3次元CGの応用 : 来るべき経路誘導システムの完全実用化を目指して
- 1方向確率的可逆および1方向量子1カウンタオートマトン (代数系,形式言語および計算理論)
- ランダマイズドクラスタリングアルゴリズムに関する実験結果について
- 点集合を分散の総和が最小となるようにk個のクラスターに分割するアルゴリズム
- Polytopes of linear programming relaxation for triangulations
- サブエリア間の交通流の評価
- Grobner Bases of Acyclic Tournament Graphs and Hypergeometric Systems on the Group of Unipotent Matrices (Algorithms for D-modules)
- Complexity of Grobner Bases for Toric Ideals of Acyclic Tournament Graphs (Foundations of Computer Science)
- 道路網の動的経路誘導システム
- BDDを用いたデータマイニング
- バタフライネットワークによる確率的な選択ネットワーク
- 量子計算機シミュレーションシステム (新しいパラダイムとしてのアルゴリズム工学)
- 高性能な8倍精度浮動小数点演算機構の実現
- ナビゲーションシステムと経路探索 (次世代道路交通システム : ITS)
- 前輪操舵と直接ヨーモーメントの2入力スライディングモード操舵制御
- ストカスティック経路探索アルゴリズムの開発
- カ-ナビゲ-ションと地図情報 (地図情報システム)
- 自動車の経路誘導システム (自動車情報通信システム特集号)