2026-03-14T09:57:34Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00195244 2025-01-19T23:09:37Z 1164:2822:9758:9759

実イジング計算機による制約付きスロット配置問題の解法 金丸, 翔 川村, 一志 田中, 宗 戸川, 望 計算手法 イジング計算機は組合せ最適化問題を物理システムにマッピングすることで，組合せ最適化問題の準最適解を高速に得ることができるとして注目されている．スロット配置問題は論理ブロックの最適配置や最適配送決定において重要な役割を果たす組合せ最適化問題である．本研究では，スロット配置問題に制約条件を付加した問題をイジング計算機によって効率よく解法する手法を提案する．イジング計算機でこの問題を解法するため，この問題をイジングモデルで表現する．まず，スロット配置問題をイジングモデルの状態空間で表現する際に満足すべき制約条件が満たされているとき，イジングモデルのエネルギーが最小となる制約項を導入する．この制約をスロット配置制約と呼ぶ．また，今回は付加する制約条件として，特定の部品が一定の距離以内に置かれなければならない，というものを考える．この制約を違反したときにエネルギーが大きくなる付加制約項を導入する．この制約を付加制約と呼ぶ．更に，配置された部品間の配線数とマンハッタン距離の加重和である目的関数項をイジングモデルで表現する．また，イジング計算機によって得られた解に対し，解釈処理なるアイデアを導入することで，スロット配置制約を満たさない解が得られたとしても，スロット配置制約を満たす解に解釈し直す手法を提案する．デジタルアニーラを利用し，単純な SA 手法とデジタルアニーラで比較した結果，制約付きスロット配置問題において，SA と同程度の精度の準最適解を得るのに必要なデジタルアニーラの時間が最大で約 1/50 に圧縮することができた． technical report 情報処理学会 2019-03-10 application/pdf 研究報告組込みシステム（EMB） 52 2019-EMB-50 1 6 2188-868X AA12149313 https://ipsj.ixsq.nii.ac.jp/record/195244/files/IPSJ-EMB19050052.pdf jpn