1 0 0 0 OA 双対変数を用いたA*両方向探索アルゴリズムと経路誘導における最短路問題
- 著者
- 池田 崇博 今井 浩 西村 茂樹 下浦 弘 橋本 武夫 天目 健二 三藤 邦彦
- 雑誌
- 情報処理学会研究報告アルゴリズム(AL)
- 巻号頁・発行日
- vol.1994, no.69(1994-AL-040), pp.89-96, 1994-07-22
最短路問題は、あらゆる分野での応用が考えられる最も基本的な問題の1つであり、近年急速に普及しつつある経路誘導システムとも深いつながりを持っている。本研究では、2点間の最短路問題に関して、ダイクストラ法・A^*・アルゴリズム・両方向探索といった従来のアルゴリズムを概観し、新しい手法に基づくA両方向探索アルゴリズムを提案する。また、実際の道路網のデータにこのアルゴリズムを適用した結果を基に、実際の効率及び特徴について論じる。