複数経由点指定を伴う経路探索に関する考察

• 稲垣 潤

  北海道大学 工学研究科

• 長谷山 美紀

  北海道大学 工学研究科

• 北島 秀夫

  北海道大学 工学研究科

書誌事項

タイトル別名

• A Note on Searching the Shortest Route through Several Designated Points

抄録

本稿は, 遺伝的アルゴリズム(GA)を用いた複数経由点指定を伴う経路探索手法を提案する. 本手法は, 最短経路を選択するだけでなく, 指定された複数のノードを経由する最短経路を探索することが可能である. Dijkstra法をはじめとする従来法は, 最短経路のみを求めるアルゴリズムであり, 経由点を通る経路を求めるには, すべての経由点の通過する順序を考慮に入れて探索を行う必要がある. それゆえ, 最短経路を決定するためには, 経由点数の2乗のオーダの回数の経路探索を行わなければならない. 経由点の数が多くなると, これら全経由点を通過する最短経路の探索は多くの計算量を伴う. 本手法は, 一回の探索ですべての経由点を通る最短経路を求められる点で有効である.

収録刊行物

• 電子情報通信学会技術研究報告. IE, 画像工学

  電子情報通信学会技術研究報告. IE, 画像工学 97 (429), 69-74, 1997-12-11

  一般社団法人電子情報通信学会

キーワード

• 遺伝的アルゴリズム
• 経路探索
• 経由点

詳細情報

• CRID: 1571417127329659136
• NII論文ID: 110003194616
• NII書誌ID: AN10013006
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles