イジングモデルによる類似誘導部分グラフ同型問題の解法

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