読者です 読者をやめる 読者になる 読者になる

Partition Problem

研究で11月からずっと解決できない問題がある.

この問題というのはある条件を満たす唯一の◯◯◯を求めるという問題で,上手く式を変形していくと,Partition Problem (or Number Partitioning) と呼ばれる最適化問題と等価になることが示せている(厳密に言うと完全に等価ではない).しかし,定式化した最適化問題に近似解法を適用しても,どうしても真の解が得られないのである.

そこで,備忘録を兼ねて(そして,あわよくば誰かからヒントを貰えることに期待を込めて)Partition Problemについてまとめてみようと思う.

 

まず,Partition Problemとは,N個の正整数の集合 S=\{n_{1},n_{2},\dots,n_{N}\}を2つの集合R,\,S-Rに分割するとき,R,\,S-Rの要素和が等しくなるように分割するNP完全問題である.

例として,集合S=\{3,1,1,2,2,1\}を要素和が等しくなるよう2つの集合に分割する問題を考えてみる.これは簡単に解けてR=\{1,1,1,2\},\,S-R=\{2,3\}またはR=\{2,3\},\,S-R=\{1,1,1,2\}が得られる.

上記例のように,元の集合の要素数Nが少なければヒューリスティックに解を得られるが,Nが大きくなるにつれて解を求めるのは困難になる.実際,Partition Problemにおける可能な解の組み合わせは2^{N}存在するため,全数探索で求めるのは非現実的である.

 

では解けないのかというと勿論そんなことはなく,イジングモデルを利用する方法により近似的に解くことが可能であるとされている(他にも様々な方法があるようだが,私はよく知らない).イジングモデルとは,統計力学において強磁性体を解析するために提案されたモデルであり,格子点上に並んだ自由度2(上向き or 下向き)のスピン(棒磁石みたいなもの)で構成される.

イジングモデルについての詳細な説明は他記事の解説や教科書に譲るとして,とりあえず系のハミルトニアン(全エネルギー)を考えてみる.Partition Problemにおいて,ハミルトニアンHは,スピンs_{i}\in\{-1,1\}~(i=1,2,\dots,N)n_{i}を用いて以下のように書ける.

H=A\left( \sum_{i=1}^{N}n_{i}s_{i} \right)^{2}

このHを最小化するスピン配位\textbf{s}=(s_{1},s_{2},\dots,s_{N})を求めることは,集合Sを要素和が等しくなるように2分割することに等しいということが直ちにわかる.ゆえに,最適なスピン配位を焼きなまし法 (Simulated Annealing; SA) などを利用して探索すれば現実的な時間内でPartition Problemを解くことが可能となる.

 

以上でPartition Problemの解説は終わりである.ここからは私の研究の話.

序文?で,私が定式化した問題はPartition Problemに等価ではあるが,厳密には完全に等価ではないなどと不明瞭なことを述べていた.少し具体的に説明すると,ハミルトニアンの形式は同じだが,元の集合の要素が非整数なのである.すなわち,

H=A\left( \sum_{i=1}^{N}r_{i}s_{i} \right)^{2}, ~~~ r_{i} \in \textbf{R}

ということである.上式はn_{i}r_{i}になっただけであり,またH=0となるスピン配位の組み合わせが唯一つ存在することは事前知識としてわかっている.しかしなぜか解けないのである.こまった.