WEKO3
アイテム
双対変数を用いたA*両方向探索アルゴリズムと経路誘導における最短路問題
https://ipsj.ixsq.nii.ac.jp/records/32414
https://ipsj.ixsq.nii.ac.jp/records/324143d9b54c8-eb43-49b1-a6c3-018914afbca3
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 1994 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 1994-07-22 | |||||||
タイトル | ||||||||
タイトル | 双対変数を用いたA*両方向探索アルゴリズムと経路誘導における最短路問題 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | Bidirectional A* Algorithm for the Shortest Path Problem in Route Navigation Systems | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
東京大学理学部情報科学科 | ||||||||
著者所属 | ||||||||
東京大学理学部情報科学科 | ||||||||
著者所属 | ||||||||
住友電気工業 | ||||||||
著者所属 | ||||||||
住友電気工業 | ||||||||
著者所属 | ||||||||
住友電気工業 | ||||||||
著者所属 | ||||||||
住友電気工業 | ||||||||
著者所属 | ||||||||
住友電気工業 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Information Science, Faculty of Science, University of Tokyo | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Information Science, Faculty of Science, University of Tokyo | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Sumitomo Electric Industries, Ltd. | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Sumitomo Electric Industries, Ltd. | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Sumitomo Electric Industries, Ltd. | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Sumitomo Electric Industries, Ltd. | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Sumitomo Electric Industries, Ltd. | ||||||||
著者名 |
池田, 崇博
× 池田, 崇博
|
|||||||
著者名(英) |
Takahiro, Ikeda
× Takahiro, Ikeda
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 最短路問題は、あらゆる分野での応用が考えられる最も基本的な問題の1つであり、近年急速に普及しつつある経路誘導システムとも深いつながりを持っている。本研究では、2点間の最短路問題に関して、ダイクストラ法・A^*・アルゴリズム・両方向探索といった従来のアルゴリズムを概観し、新しい手法に基づくA両方向探索アルゴリズムを提案する。また、実際の道路網のデータにこのアルゴリズムを適用した結果を基に、実際の効率及び特徴について論じる。 | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | The shortest path problem is one of the most fundamental problems applicable in various fields, and has close relation to route navigation systems. This paper surveys algorithms for the two-terminal shortest path problem such as the Dijkstra method, the A^* algorithm, and the bidirectional Dijkstra method and proposes bidirectional A^* algorithm based on a new approach. The efficiency and the property of these algorithms are discussed through experiments applying them to an actual road network. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 1994, 号 69(1994-AL-040), p. 89-96, 発行日 1994-07-22 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |