イジング計算機による誘導部分グラフ同型問題の解法

• Item type: SIG Technical Reports(1)
• 公開日: 2019-03-10
• タイトル: イジング計算機による誘導部分グラフ同型問題の解法
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 計算手法
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学基幹理工学部情報通信学科
• 著者所属: 早稲田大学基幹理工学部情報通信学科
• 著者所属: 早稲田大学グリーン・コンピューティング・システム研究機構／科学技術振興機構さきがけ
• 著者所属: NTTソフトウェアイノベーションセンタ
• 著者所属: NTTソフトウェアイノベーションセンタ
• 著者所属: NTTソフトウェアイノベーションセンタ
• 著者所属: 早稲田大学基幹理工学部情報通信学科
• 著者名: 吉村, 夏一; 多和田, 雅師; 田中, 宗; 新井, 淳也; 八木, 哲志; 内山, 寛之; 戸川, 望
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年，組合せ最適化問題をイジングモデルにマッピングすることで準最適解を高速に得ることができるアーキテクチャとして，イジング計算機が注目されている．ネットワークや木，系列などの構造を持つ多くの現実問題は，その構造を頂点集合と辺集合からなるグラフで表すことができる．特に誘導部分グラフ同型問題は，大きなグラフ構造の中に特定の構造を持つグラフがあるか否かを判定する問題であり，巨大な集積回路から不正回路を探索する際や化学物質中における特定の化学結合ネットワークを探索する際などに出現する．本稿では，誘導部分グラフ同型問題をイジング計算機によって解く手法を提案する．提案手法ではイジングモデルのエネルギー関数として，2 つのグラフに対し一方のグラフが他方のグラフの誘導部分グラフとなるときイジングモデルのエネルギーが最小となるよう設計する．この設計により，提案したエネルギー関数を最小化することで，誘導部分グラフ同型問題をイジング計算機を用いて解くことを可能にする．提案手法ではイジングモデルで使用するスピン数は 2 つのグラフの頂点数の積に抑えられる．誘導部分グラフ同型問題を実際にイジングモデル上で求解した結果を報告する．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12149313
• 書誌情報: 研究報告組込みシステム（EMB）; 巻 2019-EMB-50, 号 54, p. 1-6, 発行日 2019-03-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-868X
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会