| 講演名 | 2018-12-21 対称巡回セールスマン問題に対するHeld-Karpアルゴリズムの高速化 木村 和郎(阪大), 比嘉 慎哉(阪大), 置田 真生(阪大), 伊野 文彦(阪大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本論文は，対称巡回セールスマン問題に対する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 |
| 資料番号 | CAS2018-84,ICD2018-68,CPSY2018-50 |
| 発行日 | 2018-12-14 (CAS, ICD, CPSY) |
| 研究会情報 | |
| 研究会 | ICD / CPSY / CAS |
|---|---|
| 開催期間 | 2018/12/21(から3日開催) |
| 開催地（和） | ホテルアトールエメラルド宮古島 |
| 開催地（英） | |
| テーマ（和） | 学生・若手研究会 |
| テーマ（英） | |
| 委員長氏名（和） | 日高 秀人(ルネサス エレクトロニクス) / 中野 浩嗣(広島大) / 岡崎 秀晃(湘南工科大) |
| 委員長氏名（英） | Hideto Hidaka(Renesas) / Koji Nakano(Hiroshima Univ.) / Hideaki Okazaki(Shonan Inst. of Tech.) |
| 副委員長氏名（和） | 永田 真(神戸大) / 入江 英嗣(東大) / 三吉 貴史(富士通研) / 山脇 大造(日立) |
| 副委員長氏名（英） | Makoto Nagata(Kobe Univ.) / Hidetsugu Irie(Univ. of Tokyo) / Takashi Miyoshi(Fujitsu) / Taizo Yamawaki(Hitachi) |
| 幹事氏名（和） | 橋本 隆(パナソニック) / 夏井 雅典(東北大) / 大川 猛(宇都宮大) / 高前田 伸也(北大) / 橘 俊宏(湘南工科大) / 中村 洋平(日立) |
| 幹事氏名（英） | Takashi Hashimoto(Panasonic) / Masanori Natsui(Tohoku Univ.) / Takeshi Ohkawa(Utsunomiya Univ.) / Shinya Takameda(Hokkaido Univ.) / Toshihiro Tachibana(Shonan Inst. of Tech.) / Yohei Nakamura(Hitachi) |
| 幹事補佐氏名（和） | 伊藤 浩之(東工大) / 柘植 政利(ソシオネクスト) / 廣瀬 哲也(神戸大) / 伊藤 靖朗(広島大) / 津邑 公暁(名工大) / 山口 基(ルネサスエレクトロニクス) |
| 幹事補佐氏名（英） | Hiroyuki Ito(Tokyo Inst. of Tech.) / Masatoshi Tsuge(Socionext) / Tetsuya Hirose(Kobe Univ.) / Yasuaki Ito(Hiroshima Univ.) / Tomoaki Tsumura(Nagoya Inst. of Tech.) / Motoi Yamaguchi(Renesas Electronics) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Integrated Circuits and Devices / Technical Committee on Computer Systems / Technical Committee on Circuits and Systems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 対称巡回セールスマン問題に対するHeld-Karpアルゴリズムの高速化 |
| サブタイトル（和） | |
| タイトル（英） | Accelerating the Held-Karp Algorithm for the symmetric traveling salesman problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 対称巡回セールスマン問題 / symmetric traveling salesman problem |
| キーワード(2)（和/英） | Held-Karp アルゴリズム / Held-Karp algorithm |
| キーワード(3)（和/英） | 並列化 / parallelization |
| キーワード(4)（和/英） | meet in the middle / meet in the middle |
| キーワード(5)（和/英） | GPU / GPU |
| 第 1 著者 氏名（和/英） | 木村 和郎 / Kazuro Kimura |
| 第 1 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 第 2 著者 氏名（和/英） | 比嘉 慎哉 / Shinya Higa |
| 第 2 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 第 3 著者 氏名（和/英） | 置田 真生 / Masao Okita |
| 第 3 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 第 4 著者 氏名（和/英） | 伊野 文彦 / Fumihiko Ino |
| 第 4 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 発表年月日 | 2018-12-21 |
| 資料番号 | CAS2018-84,ICD2018-68,CPSY2018-50 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | CAS-373,ICD-374,CPSY-375 |
| ページ範囲 | pp.31-36(CAS), pp.31-36(ICD), pp.31-36(CPSY), |
| ページ数 | 6 |
| 発行日 | 2018-12-14 (CAS, ICD, CPSY) |