| 講演名 | 1997/12/11 複数経由点指定を伴う経路探索に関する考察 稲垣 潤, 長谷山 美紀, 北島 秀夫, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿は, 遺伝的アルゴリズム(GA)を用いた複数経由点指定を伴う経路探索手法を提案する. 本手法は, 最短経路を選択するだけでなく, 指定された複数のノードを経由する最短経路を探索することが可能である. Dijkstra法をはじめとする従来法は, 最短経路のみを求めるアルゴリズムであり, 経由点を通る経路を求めるには, すべての経由点の通過する順序を考慮に入れて探索を行う必要がある. それゆえ, 最短経路を決定するためには, 経由点数の2乗のオーダの回数の経路探索を行わなければならない. 経由点の数が多くなると, これら全経由点を通過する最短経路の探索は多くの計算量を伴う. 本手法は, 一回の探索ですべての経由点を通る最短経路を求められる点で有効である. |
| 抄録(英) | This paper proposes a method of searching the shortest route through several designated points using a genetic algorithm. The proposed method not only searches the shortest route but also selects the, shortest route through several designated points. Current methods, such as the Dijkstra's method, are the algorithms only for routing the shortest route. If the shortest route through several designated points is searched by these methods, its computational cost is O (N^2) where N is the number of the designated points. Therefore, the more the designated points increase, the more the routing demands computational cost. The proposed algorithm can obtain the shortest route through the points by an only search, and is more useful for this kind of routing than the other methods. |
| キーワード(和) | 遺伝的アルゴリズム / 経路探索 / 経由点 |
| キーワード(英) | genetic algorithm / routing / designated points |
| 資料番号 | IE97-110 |
| 発行日 |
| 研究会情報 | |
| 研究会 | IE |
|---|---|
| 開催期間 | 1997/12/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Image Engineering (IE) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 複数経由点指定を伴う経路探索に関する考察 |
| サブタイトル（和） | |
| タイトル（英） | A Note on Searching the Shortest Route through Several Designated Points |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 遺伝的アルゴリズム / genetic algorithm |
| キーワード(2)（和/英） | 経路探索 / routing |
| キーワード(3)（和/英） | 経由点 / designated points |
| 第 1 著者 氏名（和/英） | 稲垣 潤 / Jun Inagaki |
| 第 1 著者 所属（和/英） | 北海道大学工学研究科 Faculty of Engineering, Hokkaido University |
| 第 2 著者 氏名（和/英） | 長谷山 美紀 / Miki Haseyama |
| 第 2 著者 所属（和/英） | 北海道大学工学研究科 Faculty of Engineering, Hokkaido University |
| 第 3 著者 氏名（和/英） | 北島 秀夫 / Hideo Kitajima |
| 第 3 著者 所属（和/英） | 北海道大学工学研究科 Faculty of Engineering, Hokkaido University |
| 発表年月日 | 1997/12/11 |
| 資料番号 | IE97-110 |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 429 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |