N-クイーン問題とは 導入 5 × 5マスのチェス盤に5個のクイーンをどのように置いたら、お互いの効きが当たらないか考えてみよう。クイーンは、縦横斜めに他の駒によって遮られない限り進める。 これを一般化した問題はN-クイ […]
readクリーク被覆問題 をD-Waveマシンで解く
Karpの21のNP完全問題の一つである クリーク被覆問題 (Clique Cover Problem)を、D-Wave 2000Qを用いて解いた。クリーク被覆問題のQUBO表現による定式化を解説したのち、Python […]
read宮城県の市区町村を塗り分けろ – グラフ彩色問題 をD-Waveマシンで解く
本記事ではKarpの21のNP完全問題の一つである グラフ彩色問題 (Graph Coloring)とそのQUBO表現について解説し、具体的な応用例として宮城県における市区町村の塗り分けをとりあげ、D-Wave 2000 […]
read