講演抄録/キーワード |
講演名 |
2020-12-10 13:00
[ポスター講演]アニーリングを用いた制約充足問題ソルバ ○小津泰生(名大) |
抄録 |
(和) |
世の中の多くの問題は制約充足問題 (CSP) として与えられるが、これらは連言標準形 (CNF) の形に変換され、 SAT ソルバを用いて解かれる。現在用いられている実用的な SAT ソルバは古典コンピュータ上に実装され、古くから研究が進んでいる。一方、アニーリングという新しい技術により論理的な問題を解く試みも行われている。本研究ではこのような取り組みをさらに伸展し、与えられた CNF 問題に対して行う新たな最適化手法を提案する。また、これを用いて実装した新しいアニーリングマシン上の SAT ソルバの実装 [1] について報告する。本研究は独立行政法人情報処理推進機構による未踏ターゲット事業に係る業務委託によって行われるものである。 |
(英) |
Many problems in the world are given by formulation of Constraint Satisfaction Problem (CSP), and typically it is converted to Conjunctive Normal Form (CNF) problems to be solved by SAT solver. SAT solvers are implemented on classical computers and studied for decades. On the other hand, they are some attemptions
to solve CNF problems using annealing technology. In this research, we extend past studies and propose a new way to optimize given CNF problems. Then, we repote a new SAT solver implementation on annealing machine [1].
This research project is supported by Mitou-Target program of INFORMATION-TECHNOLOGY PROMOTION AGENCY, JAPAN |
キーワード |
(和) |
アニーリング / 量子アニーリング / SAT問題 / CSP問題 / SATソルバ / / / |
(英) |
annealing / quantum annealing / SAT problem / CSP problem / SAT Solver / / / |
文献情報 |
信学技報 |
資料番号 |
|
発行日 |
|
ISSN |
|
PDFダウンロード |
|