【要約】QUBO++で数独を解く：1-hot符号化と変数固定で空きマスだけを探索する [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
組合せ最適化問題を解くエンジニアは、制約条件の増加に伴う探索空間の爆発という課題に直面する。数独のような問題では、全てのマスと数字の組み合わせを考慮すると、変数の数が膨大になる。具体的には以下の問題がある：
- ・制約の複雑化：行、列、ブロックといった多重の制約を全てペナルティ関数として扱うと、式が複雑化する。
- ・探索空間の肥大化：全てのマスに対して変数を割り当てると、計算コストが指数関数的に増大する。
- ・既知情報の扱い：ヒントとなる数字を単なるペナルティとして扱うと、ソルバの探索効率が低下する。
// Approach
開発者は、PyQBPPを活用して数独の制約を数学的に簡潔なQUBO式へと変換するアプローチを採用した。まず、各マスにどの数字が入るかをバイナリ変数で表現する。次に、以下のステップで最適化を行う：
- ・1-hot符号化の導入：各マスに一つの数字のみが入るよう、3次元バイナリ変数 $x_{i,j,k}$ を定義する。
- ・制約のペナルティ化：各行・列・ブロックの合計が1になるよう、二乗誤差を用いたペナルティ式を構築する。
- ・変数の直接置換：
qbpp.replaceを用い、既知のヒントに対応する変数を定数に置き換えて式から削除する。 - ・スライス記法の活用：NumPy風の記法を用いて、制約式を直感的に記述する。
// Result
本手法を適用した結果、計算リソースを極めて効率的に利用できることが示された。特に、ヒント情報を変数固定として扱うことで、探索対象となる変数の数を劇的に減らすことに成功している。具体的な成果は以下の通りである：
- ・探索空間の削減：729個の変数のうち、Hardレベルのパズルでは570個を固定し、159変数まで削減した。
- ・計算時間の短縮：Hardレベルのパズルであっても、EasySolverを用いて1秒未満で解に到達した。
- ・実装コストの低減：スライス記法とライブラリの機能を活用し、数式に近い簡潔なコードでの実装を実現した。
Senior Engineer Insight
> 実戦的な最適化エンジンの設計において、本記事の「ペナルティではなく変数の削除」という思想は極めて重要である。制約をペナルティとして追加するだけでは、ソルバは依然として無関係な領域を探索し続ける。既知情報を利用して探索空間そのものを削ぎ落とす設計は、レイテンシ低減と計算コスト抑制に直結する。ただし、変数の数が増える大規模な実務問題では、QUBOの特性上、解の精度や収束性が課題となる。スケーラビリティを確保するには、問題の分解や階層的な最適化との組み合わせを検討すべきである。