| Item type |
SIG Technical Reports(1) |
| 公開日 |
2019-11-06 |
| タイトル |
|
|
タイトル |
グリッド分割を用いたイジングモデルによる巡回セールスマン問題の解法 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Solving Traveling Salesman Problem Using Grid Partitioning via Ising-Model based Solver |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
京都大学大学院情報学研究科 |
| 著者所属 |
|
|
|
京都大学大学院情報学研究科 |
| 著者所属 |
|
|
|
京都大学大学院情報学研究科 |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Informatics, Kyoto University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Informatics, Kyoto University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Informatics, Kyoto University |
| 著者名 |
党, 璋
西川, 剛史
佐藤, 高史
|
| 著者名(英) |
Akira, Dan
Takeshi, Nishikawa
Takashi, Sato
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
組合せ最適化問題の近似解を効率的に求める手法として，イジングモデルを用いる解法が注目を集めている．代表的な組合せ最適化問題として巡回セールスマン問題が知られているが，イジングモデルを用いて巡回セールスマン問題を解こうとすると，制約条件を満たす解が得られにくく，制約条件を満たす解を得られたとしても解の品質が十分でないという課題が存在する．本稿では，制約条件を満たしやすく，かつ，高品質の解を求めることができるように，グリッド分割を併用する解法を提案し，巡回セールスマン問題のベンチマークを用いて評価する．提案手法によって，解の平均値が既存手法と比べて最大で 72.8% 改善されることを確認した． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Ising-model based solver is gaining increasing attention for its efficiency in finding approximate solutions for combinatorial optimization problems. The traveling salesman problem is known as a typical combinatorial optimization problem. However, when solving the traveling salesman problem using the Ising-model based solver, it is difficult to obtain a solution that satisfies the constraints. In addition, the quality of the solution tend to be insufficient even if the constraints could be met. In this paper, we propose a method that uses grid partitioning, with which a high-quality solution that satisfies constraints are obtained. Through the evaluation using benchmark problems, the quality of the solution with the proposed method has been improved up to 72.8%. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA12149313 |
| 書誌情報 |
研究報告組込みシステム（EMB）
巻 2019-EMB-52,
号 20,
p. 1-6,
発行日 2019-11-06
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-868X |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-EMB19052020.pdf (1.1 MB)
