イジングマシンによる制約付きグラフ彩色問題の彩色数最小化手法

• Item type: SIG Technical Reports(1)
• 公開日: 2022-03-17
• タイトル: イジングマシンによる制約付きグラフ彩色問題の彩色数最小化手法
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学基幹理工学部情報通信学科
• 著者所属: 早稲田大学大学院基幹理工学部研究科情報理工・情報通信専攻
• 著者所属: 早稲田大学大学院基幹理工学部研究科情報理工・情報通信専攻
• 著者所属: 日本電信電話株式会社NTTサービスイノベーション総合研究所
• 著者所属: 日本電信電話株式会社NTTサービスイノベーション総合研究所
• 著者所属: 日本電信電話株式会社NTTサービスイノベーション総合研究所
• 著者所属: 日本電信電話株式会社NTTサービスイノベーション総合研究所
• 著者所属: 早稲田大学大学院基幹理工学部研究科情報理工・情報通信専攻
• 著者名: 川上, 蒼馬; 武笠, 陽介; 鮑, 思雅; 巴, 徳瑪; 新井, 淳也; 八木, 哲志; 寺本, 純司; 戸川, 望
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: イジングマシンは，イジングモデルあるいは QUBO (Quadratic Unconstrained Binary Optimization) の基底状態を探索することで，効率的に組合せ最適化問題の準最適解を求めることができる．グラフ彩色問題は，組合せ最適化問題の一つで，辺で接続された任意の 2 頂点が同じ色にならないように，グラフのすべての頂点に色を割り当てる問題である．グラフ彩色問題をイジングモデルあるいは QUBO にマッピングする手法が提案されているが，彩色数の最小化は考慮されていない．また実問題に応用するための付加制約を含めた手法も知られていない．本稿では，彩色数の最小化および付加制約を考慮したグラフ彩色問題を QUBO にマッピングする手法を提案する．まずスピン数の増加を抑えた上で，彩色数を最小化する目的関数を導入する．さらに，付加制約として指定した頂点を指定した色で塗る制約および特定の色の使用回数を制限する制約を導入する．このとき，理論的に QUBO が基底状態をとると，制約を満足した上で目的関数が最小化される．イジングマシン実機を用いた実験の結果，付加制約を考慮しないとき，既存手法と比較して彩色数が平均で 75.1 %削減された．また，付加制約を考慮した場合，すべての制約を満たす解を得ることを確認した．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12894105
• 書誌情報: 量子ソフトウェア（QS）; 巻 2022-QS-5, 号 2, p. 1-8, 発行日 2022-03-17
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2435-6492
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会