文献

J-GLOBAL ID：202002230677377481   整理番号：20A0323259

対称巡回セールスマン問題のためのHeld-Karpアルゴリズムの加速

Accelerating the Held-Karp Algorithm for the Symmetric Traveling Salesman Problem

著者 (4件)： KIMURA Kazuro (School of Engineering Science, Osaka University) ,  HIGA Shinya (School of Engineering Science, Osaka University) ,  OKITA Masao (Graduate School of Information Science and Technology, Osaka University) ,  INO Fumihiko (Graduate School of Information Science and Technology, Osaka University)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E102.D  号： 12  ページ： 2329-2340(J-STAGE)  発行年： 2019年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文では,動的計画法により対称巡回セールスマン問題を解くHeld-Karpアルゴリズムのための加速法を提案した。提案方法は,2つの技術によって加速を達成した。第一に,サブ問題を並列に解くことができるように,データに依存しないサブ問題を位置決めする。第二に,著者らは,時計回りおよび反時計方向の両方から最適経路を計算する中間(MITM)技術における適合によってサブ問題の数を減少させる。時間と空間の複雑さに関するMITMの影響に関する理論解析を示した。実験では,提案した方法を単一コアCPU上で実行する以前の方法と比較した。実験結果は,8コアCPUに関する提案方法が,単一コアCPUに関する以前の方法より9.5~10.5倍速いことを示した。さらに,グラフィックス処理ユニット(GPU)上の提案方法は,8コアCPU上のものより30~40倍速かった。意外な結果として,提案した方法はメモリ使用を48%削減した。(翻訳著者抄録)

シソーラス用語： *対称性 ,  *巡回セールスマン問題 ,  *アルゴリズム ,  動的計画法 ,  最適航路 ,  計算 ,  マイクロプロセッサ ,  専用プロセッサ ,  GPU【プロセッサ】 ,  マルチコアプロセッサ
準シソーラス用語： *Held-Karpアルゴリズム ,  経路計算 ,  マルチコアCPU

著者キーワード (5件)： 対称巡回セールスマン問題 ,  Held-Karpアルゴリズム ,  並列化 ,  中間に適合 ,  GPU

分類 (2件)： 数理計画法  (KA03030M) ,  ネットワーク法  (KA03040X)

引用文献 (20件)：

• [1] X. Wang, B. Tang, Y. Yan, and X. Gu, “Time-optimal path planning for dual-welding robots based on intelligent optimization strategy,” Trans. Intelligent Welding Manufacturing, vol.1, no.2, pp.47-59, Dec. 2017. 10.1007/978-981-10-7043-3_3
• [2] M. Held and R.M. Karp, “A dynamic programming approach to sequencing problems,” J. Society for Industrial and Applied Mathematics, vol.10, no.1, pp.196-210, March 1962. 10.1137/0110015
• [3] W. Cook, “Concorde home,” 2016. http://www.math.uwaterloo.ca/tsp/concorde.html.
• [4] N. Christofides, “Worst-case analysis of a new heuristic for the travelling salesman problem,” Tech. Rep., Carnegie-Mellon University Pittsburgh Pa Management Sciences Research Group, Feb. 1976.
• [5] S. Lin and B.W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,” Operations Research, vol.21, no.2, pp.498-516, April 1973. 10.1287/opre.21.2.498

タイトルに関連する用語 (4件)： 対称 ,  巡回セールスマン問題 ,  アルゴリズム ,  加速