WEKO3
アイテム
サムラインのNP完全性の証明と量子アニーリングを用いた解法について
https://ipsj.ixsq.nii.ac.jp/records/231463
https://ipsj.ixsq.nii.ac.jp/records/231463e4397d62-d632-4652-a28a-e879adb13e9c
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-MPS23146009.pdf (1.1 MB)
|
Copyright (c) 2023 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-12-04 | |||||||||
| タイトル | ||||||||||
| タイトル | サムラインのNP完全性の証明と量子アニーリングを用いた解法について | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| 現在，静岡県立大学大学院経営情報イノベーション研究科 | ||||||||||
| 著者所属 | ||||||||||
| 現在，静岡県立大学大学院経営情報イノベーション研究科 | ||||||||||
| 著者名 |
福永, 智渉
× 福永, 智渉
× 大久保, 誠也
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 本研究では，組合せパズルゲームの 1 つであるサムラインが，NP 完全であることを証明する．また，量子アニーリングを用いた解法を提案する．具体的にはまず，サムラインの NP 完全性について，カックロからの多項式時間帰着を示すことによって証明する．次に，サムラインをイジングモデルの基底状態探索問題として表現することにより，量子アニーリングによる解法を提案する．最後に，計算機実験により，提案手法の妥当性を示す． | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN10505667 | |||||||||
| 書誌情報 |
研究報告数理モデル化と問題解決（MPS） 巻 2023-MPS-146, 号 9, p. 1-6, 発行日 2023-12-04 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2188-8833 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
