N-クイーン問題とは 導入 5 × 5マスのチェス盤に5個のクイーンをどのように置いたら、お互いの効きが当たらないか考えてみよう。クイーンは、縦横斜めに他の駒によって遮られない限り進める。 これを一般化した問題はN-クイ […]

本記事では、Karpの21のNP完全問題の一つである 充足可能性問題 (SAT; satisfiability problem)に関して、最大独立集合問題 (MIS; maximum independent set)に帰 […]

T-Wave開設以来、いくつかの先行研究や導入事例に関する記事が出ている中で、どのように具体的な問題をD-Waveマシンで解くのかということは皆さん気になっていると思います。本記事では グラフ分割問題 を例に、サポートツ […]

Karpの21のNP完全問題の一つである クリーク被覆問題 (Clique Cover Problem)を、D-Wave 2000Qを用いて解いた。クリーク被覆問題のQUBO表現による定式化を解説したのち、Python […]

本記事ではKarpの21のNP完全問題の一つである グラフ彩色問題 (Graph Coloring)とそのQUBO表現について解説し、具体的な応用例として宮城県における市区町村の塗り分けをとりあげ、D-Wave 2000 […]