2019年11月13日~11月15日に愛媛県男女共同参画センターで開催された電子情報通信学会デザインガイア2019にて,M2の党が発表を行いました(発表日は14日).
組合せ最適化問題の近似解を効率的に求める手法としてイジングモデルを用いる解法が注目を集めています.一方で,代表的な組合せ最適化問題として巡回セールスマン問題が知られていますが,イジングモデルを用いて巡回セールスマン問題を解こうとすると制約条件を満たす解が得られにくく,制約条件を満たす解を得られたとしても解の品質が十分でないという課題が存在します.本発表では,制約条件を満たしやすく,かつ,高品質の解を求めることができるように,グリッド分割を併用する解法を提案しました.巡回セールスマン問題のベンチマークを用いて計算機シミュレーションを行い,提案手法によってイジングモデルを用いた既存解法と比べて解の平均値が最大で72.8%改善されることを確認しました.
- 党 璋, 西川 剛史, 佐藤 高史: “グリッド分割を用いたイジングモデルによる巡回セールスマン問題の解法”, 電子情報通信学会技術研究報告(デザインガイア2019 -VLSI設計の新しい大地-)(於 愛媛県男女共同参画センター), Vol.119, No.282, VLD2019-40, pp.97-102, 2019年11月.