講演抄録/キーワード |
講演名 |
2018-12-21 16:00
対称巡回セールスマン問題に対するHeld-Karpアルゴリズムの高速化 ○木村和郎・比嘉慎哉・置田真生・伊野文彦(阪大) CAS2018-84 ICD2018-68 CPSY2018-50 エレソ技報アーカイブへのリンク:ICD2018-68 |
抄録 |
(和) |
本論文は,対称巡回セールスマン問題に対するHeld-Karpアルゴリズムの高速化手法を提案する.提案手法は,2 つの工夫により高速化を果たす.まず,データ依存に関して独立な部分問題を特定し,それらを並列に解く.次に,最適経路を 2 つに分割することで,解くべき部分問題の数を削減する.評価実験では,マルチコア CPU 上の提案手法とシングルコア CPU 上の既存手法を比較した.結果,約 9.5~10.5 倍の速度向上率を得た.また,GPU(Graphics Processing Unit)上の提案手法は,シングルコア CPU 上の既存手法よりも約 300~400 倍高速であった.さらに,副次的な効果として,提案手法はメモリ使用量を約 48 % 削減できた. |
(英) |
In this paper, we propose an acceleration method for the Held-Karp algorithm that solves the symmetric traveling salesman problem. The proposed method achieves acceleration with two techniques. First, we locate data-independent subproblems so that the subproblems can be solved in parallel. Second, we reduce the number of subproblems to be solved by separating the optimal path into two parts. In experiments, we compared an existing method running on a single-core CPU with the proposed method running on a multi-core CPU. Experimental results show that the proposed method on a multi-core CPU was 9.5-10.5 times faster than the existing method on a single-core CPU. Moreover, the proposed method on a graphics processing unit (GPU) was 300-400 times faster than the existing method on a single-core CPU. As a side effect, the proposed method reduced the memory usage by 48 %. |
キーワード |
(和) |
対称巡回セールスマン問題 / Held-Karp アルゴリズム / 並列化 / meet in the middle / GPU / / / |
(英) |
symmetric traveling salesman problem / Held-Karp algorithm / parallelization / meet in the middle / GPU / / / |
文献情報 |
信学技報, vol. 118, no. 375, CPSY2018-50, pp. 31-36, 2018年12月. |
資料番号 |
CPSY2018-50 |
発行日 |
2018-12-14 (CAS, ICD, CPSY) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CAS2018-84 ICD2018-68 CPSY2018-50 エレソ技報アーカイブへのリンク:ICD2018-68 |