| No | 95578 |
|---|---|
| 標題（和） | 複数経由点指定を伴う経路探索に関する考察 |
| 標題（英） | A Note on Searching the Shortest Route through Several Designated Points |
| 研究会名（和） | 通信方式; 画像工学 |
| 研究会名（英） | Communication Systems; Image Engineering |
| 開催年月日 | 1997-12-11 |
| 終了年月日 | 1997-12-12 |
| 会議種別コード | 2 |
| 共催団体名（和） | 映像情報メディア学会 |
| 資料番号 | CS97-129,IE97-110 |
| 抄録（和） | 本稿は、遺伝的アルゴリズム(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. |
| 収録資料名（和） | 電子情報通信学会技術研究報告 |
| 収録資料の巻号 | Vol.97 No.427,428 |
| ページ開始 | 69 |
| ページ終了 | 74 |
| キーワード（和） | 経由点 |
| キーワード（英） | designated points |
| 本文の言語 | JPN |
| 著者（和） | 北島秀夫 |
| 著者（ヨミ） | キタジマヒデオ |
| 著者（英） | Kitajima Hideo |
| 所属機関（和） | 北海道大学大学院工学研究科 |
| 所属機関（英） | Graduate School of Engineering, Hokkaido University |
| 著者（和） | 長谷山美紀 |
| 著者（ヨミ） | ハセヤマミキ |
| 著者（英） | Haseyama Miki |
| 所属機関（和） | 北海道大学大学院工学研究科 |
| 所属機関（英） | Graduate School of Engineering, Hokkaido University |
| 著者（和） | 稲垣潤 |
| 著者（ヨミ） | イナガキジュン |
| 著者（英） | Inagaki Jun |
| 所属機関（和） | 北海道大学大学院工学研究科 |
| 所属機関（英） | Graduate School of Engineering, Hokkaido University |