| 講演名 | 2001/4/9 類似検索手法による無向グラフの最短経路探索法 山口 一章, 岩見 洋平, 増田 澄男, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では始点と終点が与えられるような最短経路問題を扱う.この問題は,各点について,終点までのおおよその距離が分かれば,人工知能分野で用いられている経路探索法のA^*アルゴリズムを用いて効率よく解くことができる.一方,LAESAという類似検索手法は,効率良く検索を行うために近似距離というものを用いる.本稿では近似距離をA^*アルゴリズムに用い得ること,及びその方法により高速に最短経路を求められることを示す. |
| 抄録(英) | We deal with the problem to find a shortest path between two specified vertices. This problem can be efficiently solved with A^* algorithm, used in AI field, if we roughly know the distance from each vertex to the goal vertex. On the other hand, LAESA, one of nearest neighbor search algorithms, uses "approximate distance" to solve NNS problem efficiently. In this paper, we show that approximate disntace can be applied to A^* algorithm, and that we can efficiently obtain shortest paths with this method. |
| キーワード(和) | 無向グラフ / 最短経路 / アルゴリズム / 類似検索 / ナビゲーション |
| キーワード(英) | undirected graph / shortest path / algorithm / nearest neighbor search / navigation |
| 資料番号 | COMP2001-3 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2001/4/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 類似検索手法による無向グラフの最短経路探索法 |
| サブタイトル（和） | |
| タイトル（英） | An algorithm for finding shortest paths in undirected graphs with using the nearest neighbor search technique |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 無向グラフ / undirected graph |
| キーワード(2)（和/英） | 最短経路 / shortest path |
| キーワード(3)（和/英） | アルゴリズム / algorithm |
| キーワード(4)（和/英） | 類似検索 / nearest neighbor search |
| キーワード(5)（和/英） | ナビゲーション / navigation |
| 第 1 著者 氏名（和/英） | 山口 一章 / Kazuaki YAMAGUCHI |
| 第 1 著者 所属（和/英） | 神戸大学工学部 Faculty of Engineering, Kobe University |
| 第 2 著者 氏名（和/英） | 岩見 洋平 / Yohei IWAMI |
| 第 2 著者 所属（和/英） | 神戸大学工学部:(現)奈良先端技術大学院大学 Faculty of Engineering, Kobe University:(Present address) Nara Institute of Science and Technology |
| 第 3 著者 氏名（和/英） | 増田 澄男 / Sumio MASUDA |
| 第 3 著者 所属（和/英） | 神戸大学工学部 Faculty of Engineering, Kobe University |
| 発表年月日 | 2001/4/9 |
| 資料番号 | COMP2001-3 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 5 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |