(57)【特許請求の範囲】
【請求項１】
集合Ｍを分割する集合分割問題における部分集合の候補の情報である候補情報として、複数の部分集合Ｓ1、Ｓ2、・・・の情報を取得する取得手段と、
前記取得手段により取得された前記候補情報に基づいて、集合Ｍの各要素ｋについて、ｋを含む部分集合Ｓjの番号ｊの集合Ｄkを取得し、取得したＤkの要素数であるｄkを取得し、Ｄkの要素のペアの集合であるＰkを取得し、Ｐkの要素に対応する相互作用係数Ｊijを−１と決定し、Ｄkの要素に対応する外部磁場係数ｈjを−（ｄk−２）と決定し、ＤkとＰkとＪijとｈjとを、ｋに関するローカルなハミルトニアンの式として予め定められた式１に当てはめることで、ｋに関するローカルなハミルトニアンの式Ｈkであって、イジングモデルにおけるスピンの向きを表す変数σ以外の変数の値が決定された式Ｈｋを求めて、集合Ｍの各要素ｋについて求めたＨkを、予め定められた式２を用いてＭの全ての要素について足し合わせることで、前記集合分割問題に対応するイジングモデルにおけるハミルトニアンの式を示す情報を生成する生成手段と、
を有する情報処理装置。
【数１】
0006760739.tif 000015
【数２】
0006760739.tif 000016
【請求項２】
前記生成手段により生成された前記集合分割問題に対応するイジングモデルにおけるハミルトニアンの式を示す情報をイジングモデル計算デバイスに送信し、前記イジングモデル計算デバイスに前記式の値を最小とするスピンの状態の計算を指示する指示手段と、
前記指示手段による指示に応じた計算結果の情報を、前記イジングモデル計算デバイスから受信し、受信した前記計算結果の情報に基づいて、前記集合分割問題の分割結果を決定する決定手段と、
を更に有する請求項１に記載の情報処理装置。
【請求項３】
前記決定手段により決定された前記集合分割問題の分割結果を出力する出力手段を更に有する請求項２に記載の情報処理装置。
【請求項４】
前記イジングモデル計算デバイスを更に有する請求項２又は３に記載の情報処理装置。
【請求項５】
情報処理装置が実行する情報処理方法であって、
集合Ｍを分割する集合分割問題における部分集合の候補の情報である候補情報として、複数の部分集合Ｓ1、Ｓ2、・・・の情報を取得する取得ステップと、
前記取得ステップで取得された前記候補情報に基づいて、集合Ｍの各要素ｋについて、ｋを含む部分集合Ｓjの番号ｊの集合Ｄkを取得し、取得したＤkの要素数であるｄkを取得し、Ｄkの要素のペアの集合であるＰkを取得し、Ｐkの要素に対応する相互作用係数Ｊijを−１と決定し、Ｄkの要素に対応する外部磁場係数ｈjを−（ｄk−２）と決定し、ＤkとＰkとＪijとｈjとを、ｋに関するローカルなハミルトニアンの式として予め定められた式１に当てはめることで、ｋに関するローカルなハミルトニアンの式Ｈkであって、イジングモデルにおけるスピンの向きを表す変数σ以外の変数の値が決定された式Ｈｋを求めて、集合Ｍの各要素ｋについて求めたＨkを、予め定められた式２を用いてＭの全ての要素について足し合わせることで、前記集合分割問題に対応するイジングモデルにおけるハミルトニアンの式を示す情報を生成する生成ステップと、
を含む情報処理方法。
【数３】
0006760739.tif 000017
【数４】
0006760739.tif 000018
【請求項６】
コンピュータを、請求項１乃至４の何れか１項に記載の情報処理装置の各手段として、機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法及びプログラムに関する。
【背景技術】
【０００２】
組合せ最適化問題には、乗務員のスケジューリング決定処理、配送計画決定処理等のように、与えられた集合の各要素を１回ずつ含む部分集合の組み合わせの中で、コストの総和が最小となる組み合わせを求める集合分割問題がある。
しかし、集合分割問題では、部分集合の候補の数が多い程、計算量が非常に増加し、求められる時間内に解を計算することが困難となる。
集合分割問題等の組み合わせ最適化問題の解を計算する方法には、特許文献１の方法がある。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００１−１８８９８４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、特許文献１でも、問題の規模が大きくなると計算に時間がかかり、求められる時間内で精度の高い解を求めることが困難であった。
一方、イジングモデルにおけるハミルトニアンを最小化するスピンの状態を効率的に計算することができるイジングモデル計算デバイスが開発されている。
イジングモデルとは、結晶を構成する原子のスピンの向きを計算する簡易的なモデルである。格子上の格子点に原子があり、それぞれの原子は、上向きか下向きかのどちらかのみをとるスピンを有するものとする。隣り合った原子のスピンの向きがそろいたがるという現象を利用し、イジングモデルのハミルトニアンは、定義される。
組み合わせ最適化問題をイジングモデルとして表すことで、イジングモデル計算デバイスを用いて効率的に組み合わせ最適化問題を解くことができる。
しかし、集合分割問題を表す式とイジングモデルのハミルトニアンの式とは、形式が異なり、集合分割問題をイジングモデルとして表すことができなかった。
本発明は、効率的に集合分割問題の解を求めることを可能とすることを目的とする。
【課題を解決するための手段】
【０００５】
本発明の情報処理装置は、集合Ｍを分割する集合分割問題における部分集合の候補の情報である候補情報として、複数の部分集合Ｓ1、Ｓ2、・・・の情報を取得する取得手段と、前記取得手段により取得された前記候補情報に基づいて、集合Ｍの各要素ｋについて、ｋを含む部分集合Ｓjの番号ｊの集合Ｄkを取得し、取得したＤkの要素数であるｄkを取得し、Ｄkの要素のペアの集合であるＰkを取得し、Ｐkの要素に対応する相互作用係数Ｊijを−１と決定し、Ｄkの要素に対応する外部磁場係数ｈjを−（ｄk−２）と決定し、ＤkとＰkとＪijとｈjとを、ｋに関するローカルなハミルトニアンの式として予め定められた式に当てはめることで、ｋに関するローカルなハミルトニアンの式Ｈkであって、イジングモデルにおけるスピンの向きを表す変数σ以外の変数の値が決定された式Ｈｋを求めて、集合Ｍの各要素ｋについて求めたＨkを、予め定められた式を用いてＭの全ての要素について足し合わせることで、前記集合分割問題に対応するイジングモデルにおけるハミルトニアンの式を示す情報を生成する生成手段と、を有する。
係る構成を有することで、集合分割問題を表すイジングモデルのハミルトニアンの式を示す情報を生成することができるため、イジングモデル計算デバイスを適用して効率的に集合分割問題の解を求めることを可能にすることができる。
【発明の効果】
【０００６】
本発明によれば、効率的に集合分割問題の解を求めることを可能とすることができる。
【図面の簡単な説明】
【０００７】
【図１】図１は、計算システムのシステム構成の一例を示す図である。
【図２】図２は、情報処理装置のハードウェア構成の一例を示す図である。
【図３】図３は、情報処理装置の機能構成の一例を示す図である。
【図４】図４は、情報処理装置の処理の一例を示すフローチャートである。
【図５】図５は、集合分割問題の概要を説明する図である。
【図６】図６は、制約条件とハミルトニアンとの関係を示す図である。
【図７】図７は、変換処理の一例を示すフローチャートである。
【図８】図８は、イジングモデル計算デバイスの実装の一例を説明する図である。
【図９】図９は、イジングモデル計算デバイスの実装の一例を説明する図である。
【発明を実施するための形態】
【０００８】
＜実施形態１＞
以下、本発明の実施形態について図面に基づいて説明する。
図１は、本実施形態の集合分割問題を計算する処理を行う計算システムのシステム構成の一例を示す図である。計算システムは、情報処理装置１００、イジングモデル計算デバイス１０１を含む。
情報処理装置１００は、集合分割問題の部分集合の候補の情報を取得し、集合分割問題をイジングモデルのハミルトニアンの形式に変換するパーソナルコンピュータ（ＰＣ）、サーバ装置等の情報処理装置である。
【０００９】
イジングモデル計算デバイス１０１は、指定されたイジングモデルについて、ハミルトニアンを最小化するスピンの状態を計算するデバイスである。イジングモデル計算デバイス１０１は、例えば、イジングモデルにおけるスピン毎にスピン回路を有する装置である。各スピン回路は、各スピンの状態（上向き又は下向き、＋１又は−１）を記憶するメモリ素子、自己のスピンに隣接するスピンとの間の相互作用係数を記憶するメモリ素子、イジングモデルのハミルトニアンにおける外部磁場の影響の大きさを示す外部磁場係数に相当する係数の値（以下では、説明の簡略化のため単に外部磁場係数という）を記憶するメモリ素子を有する。
また、各スピン回路は、各スピンの次世代のスピン状態を決定するために利用される論理回路を有する。世代とは、初期の状態を第１世代として、初期の状態からどれくらいの期間が経過したかを示すための指標であり、設定されたクロックが経過する毎に一つずつ増加する。例えば、第Ａ世代から設定されたクロックが経過した状態は、第Ａ＋１世代となる。
イジングモデル計算デバイス１０１は、現世代のスピンの状態に基づいて、次世代のスピンの状態を決定する。各スピン回路は、隣接するスピンのスピン回路に対して、自己のスピン状態を通知し、隣接するスピンのスピン回路から隣接するスピンのスピン状態を取得する。また、各スピン回路は、メモリ素子から隣接するスピンとの間の相互作用係数、外部磁場係数を取得する。各スピン回路は、取得した隣接するスピンの状態、相互作用係数、外部磁場係数に基づいて、自己のスピンの状態を更新する。
各スピン回路は、正の相互作用係数を持つ隣接スピンと同じ向きへ、負の相互作用係数を持つ隣接スピンと反対の向きへ、自己のスピンの状態を更新しようとする。各スピン回路は、隣接するスピンからの影響の多数決によって、自己の新しいスピンの状態を決定する。その結果、イジングモデル計算デバイス１０１は、イジングモデルが持つエネルギーが低下する方向に、イジングモデルにおける各スピンを変化させることになる。
情報処理装置１００は、集合分割問題の部分集合の候補を取得し、取得した候補の情報に基づいて、集合分割問題をイジングモデルのハミルトニアンの形式に変換した式を取得する。そして、情報処理装置１００は、取得したハミルトニアンの式の情報を、イジングモデル計算デバイス１０１に送信する。イジングモデル計算デバイス１０１は、送信されたハミルトニアンの式を最小化する各スピンの向きを計算し、計算した各スピンの向きを情報処理装置１００に送信する。情報処理装置１００は、送信された各スピンの向きに基づいて、取得した部分集合の候補の中から最終的な分割結果となる部分集合を決定する。
【００１０】
図２は、情報処理装置１００のハードウェア構成の一例を示す図である。情報処理装置１００は、ＣＰＵ２０１、主記憶装置２０２、補助記憶装置２０３、入出力Ｉ／Ｆ２０４、デバイスＩ／Ｆ２０５、を含む。ＣＰＵ２０１、主記憶装置２０２、補助記憶装置２０３、入出力Ｉ／Ｆ２０４、デバイスＩ／Ｆ２０５は、システムバス２０６を介して、相互に接続されている。
ＣＰＵ２０１は、情報処理装置１００の処理を制御する中央演算処理装置である。主記憶装置２０２は、ＣＰＵ２０１の主メモリ、ワークエリア等として機能する記憶装置である。補助記憶装置２０３は、各種プログラム、各種設定情報等を記憶する記憶装置である。入出力Ｉ／Ｆ２０４は、マウス、キーボード、タッチパネル等の入力装置からの入力を受け付けたり、計算結果等をモニタ、タッチパネル等の出力装置へ出力したりする際に利用されるインターフェースである。デバイスＩ／Ｆ２０５は、イジングモデル計算デバイス等の外部のデバイスと接続する際に利用されるインターフェースである。
ＣＰＵ２０１が、補助記憶装置２０３等に記憶されたプログラムに基づき処理を実行することによって、図３で後述する情報処理装置１００の機能及び図４、図７で後述するフローチャートの処理が実現される。
【００１１】
図３は、情報処理装置１００の機能構成の一例を示す図である。情報処理装置１００は、候補情報取得部３０１、変換部３０２、デバイス制御部３０３、決定部３０４を含む。
候補情報取得部３０１は、集合分割問題における部分集合の候補情報を取得する。例えば、候補情報取得部３０１は、補助記憶装置２０３に予め記憶されている計算対象である集合分割問題における部分集合の候補情報を、補助記憶装置２０３から取得する。また、候補情報取得部３０１は、計算対象である集合分割問題における部分集合の候補情報を、外付けＨＤＤや外付けＵＳＢメモリ等の外付けの記憶装置から取得することとしてもよい。
また、候補情報取得部３０１は、表示装置等に表示された入力データ選択画面や入力装置を介したユーザの操作に基づいて選択された候補情報を、補助記憶装置２０３等から取得することとしてもよい。また、候補情報取得部３０１は、表示装置等に表示された入力画面や入力装置を介したユーザの操作に基づいて、計算対象である集合分割問題における部分集合の候補情報を取得することとしてもよい。また、候補情報取得部３０１は、計算対象である集合分割問題における部分集合の候補情報を、ネットワークを介して接続される外部のサーバ等から取得することとしてもよい。候補情報取得部３０１は、取得した候補情報を変換部３０２に渡す。
【００１２】
変換部３０２は、候補情報取得部３０１から取得した候補情報に基づいて、計算対象の集合分割問題をイジングモデルに変換する。集合分割問題には、分割対象の集合の要素ｋを含む部分集合が１つのみ存在するという制約条件のもとに、分割対象の集合を分割する問題である。変換部３０２は、最小値をとる場合に集合分割問題の制約条件を満たすことになるイジングモデルのハミルトニアンの式を生成することで、集合分割問題をイジングモデルに変換する。
デバイス制御部３０３は、変換部３０２により生成されたイジングモデルのハミルトニアンの式の情報を、イジングモデル計算デバイス１０１に送信することで、イジングモデル計算デバイス１０１に対して、送信した式が最小値となるスピンの状態を計算するように指示する。イジングモデル計算デバイス１０１は、受信したハミルトニアンの式の値が最小値となるスピンの状態を計算し、計算結果をデバイス制御部３０３に送信する。デバイス制御部３０３は、イジングモデル計算デバイス１０１から受信した計算結果を、決定部３０４に渡す。
決定部３０４は、デバイス制御部３０３から渡されたハミルトニアンの式の値が最小値となるスピンの状態に基づいて、候補情報取得部３０１により取得された分割結果の候補のうちから、最終的な分割結果となる部分集合を決定する。
【００１３】
図４は、情報処理装置１００の処理の一例を示すフローチャートである。本実施形態では、ｍ個の要素からなる集合Ｍ＝｛１、２、・・・、ｍ｝を分割する集合分割問題を計算対象とする。
Ｓ４０１において、候補情報取得部３０１は、補助記憶装置２０３に予め記憶されている集合分割問題における部分集合の候補情報を、補助記憶装置２０３から取得する。
補助記憶装置２０３は、例えば、集合分割問題における部分集合の候補の情報である候補情報として、分割対象である集合の要素数と同じ値の要素数を持つ配列（以下では、候補配列）の情報を予め記憶しているものとする。候補配列は、集合分割問題における部分集合の１つの候補を示す配列であり、分割対象である集合Ｍの要素数がｍ個である場合、ｍ個の要素を持つ１次元の配列となる。候補配列のｋ（１≦ｋ≦ｍ）番目の要素は、分割対象の集合Ｍのｋ番目の要素に対応している。候補配列の各要素は、０又は１の何れかの値をとり、候補配列のｋ番目の要素の値が１であることは、候補配列が示す部分集合に集合Ｍのｋ番目の要素が含まれることを示す。また、候補配列のｋ番目の要素の値が０であることは、候補配列が示す部分集合に集合Ｍのｋ番目の要素が含まれないことを示す。また、候補情報は、分割対象である集合の要素のうち、どの要素を含む部分集合であるかを示す情報であれば、配列に限定されず、例えば、分割対象の集合のうち、どの要素を含むかを示すテキストデータ等でもよい。
候補情報取得部３０１は、例えば、ｎ個のそれぞれ異なる部分集合Ｓj（１≦ｊ≦ｎ）に対応するｎ個の候補配列を補助記憶装置２０３から取得する。取得されるｎ個の候補配列のそれぞれは、要素数ｍの１次元配列である。また、情報処理装置１００は、取得した候補配列の要素数を取得することで、計算対象の集合分割問題における分割対象の集合の要素数を把握することができる。
【００１４】
Ｓ４０２において、変換部３０２は、Ｓ４０１で取得された候補情報に基づいて、計算対象の集合分割問題を示すイジングモデルにおけるハミルトニアンを生成する。これにより、変換部３０２は、計算対象の集合分割問題を、イジングモデルにおけるハミルトニアンが最小値となる場合のスピンの状態を求める問題に変換することができる。Ｓ４０２の処理の詳細は、図７で後述する。
以下では、集合分割問題をイジングモデルに変換する仕組みについて説明する。集合分割問題とは、次のような問題である。ｍ個の要素からなる集合Ｍ＝｛１、２、・・・、ｍ｝、ｎ個の部分集合Ｓjとそれらのコストｃjが与えられたとき、集合Ｍの全ての要素ｋ∈Ｍをちょうど一回ずつ含む部分集合の組合せの中で、コストの総和が最小になるものを求める問題である。集合Ｍの要素ｋがＳjに含まれていれば１となり、ｋがＳjに含まれていなければ０となるような係数ａkjを定義する。そして、部分集合Ｓjが選択された場合に１となり、部分集合Ｓjが選択されない場合に０となる変数をｘjとすると、集合分割問題は、以下の式１で定式化できる。変数ｘjは、部分集合Ｓjが分割対象の集合Ｍの分割結果として選択されたか否かを示す変数とみなすことができる。式１の最上部の式は、集合分割問題における目的関数である。
【００１５】
【数１】
0006760739.tif 000002
【００１６】
図５は、集合分割問題の概要を説明する図である。図５は、Ｓ４０１で、分割対象の集合｛１、２、３、・・・、７｝の部分集合の候補として９個の部分集合Ｓj（１≦ｊ≦９）、つまりＳ1、Ｓ2、・・・、Ｓ9の候補情報が取得された場合の係数ａkjの例を示す図である。
図５の表のｋ行は、分割対象の集合の要素ｋを示す。そして、図５の表のｊ列は、各部分集合Ｓjを示す。図５の表の各列の斜線模様の要素は、その列に対応する部分集合が対応する集合の要素を含んでいることを示している。図５における集合分割問題とは、集合｛１、２、３、・・・、７｝の各要素が丁度、１回ずつ現れるように、部分集合をＳjの中から選択する問題ということができる。図５の例では、正解は、Ｓ1とＳ7とＳ9との組み、又は、Ｓ4とＳ8との組みである。
【００１７】
本実施形態では、情報処理装置１００は、集合分割問題をイジングモデルのハミルトニアンの式に変換する。そして、イジングモデル計算デバイス１０１は、変換されたハミルトニアンを最小化するスピンの状態を計算する。即ち、イジングモデル計算デバイス１０１は、ハミルトニアンを最小化するスピンの状態を計算する。計算対象の集合分割問題に目的関数がある場合、イジングモデル計算デバイス１０１は、ハミルトニアンに加え、他の目的関数をも最小化するスピンの状態を計算しなければならないこととなる。この場合、イジングモデル計算デバイス１０１は、ハミルトニアンを最小化するスピンの状態を計算する場合に比べて、より多くのハードウェア資源（例えば、各スピン回路内のメモリ素子等）を必要とする。そのため、イジングモデル計算デバイス１０１は、ハードウェア資源が不足するため、ハミルトニアンに加え、他の目的関数をも最小化するスピンの状態を計算することができない場合がある。
また、集合分割問題において、目的関数を満たす最適解でなくとも、局所的な解が求まれば、それで十分である場合がある。そこで、本実施形態では、計算システムは、目的関数なしの集合分割問題を計算することとする。それにより、計算システムは、イジングモデル計算デバイス１０１内のハードウェア資源等のリソースを節約することができる。
目的関数なしの集合分割問題は、以下の式２のように定式化できる。
【００１８】
【数２】
0006760739.tif 000003
【００１９】
式２の形式は、式５で後述するイジングモデルのハミルトニアンの形式と異なる。そのため、イジングモデル計算デバイス１０１は、式２で表される集合分割問題を計算することができない。
式２の中の変数ｘjを、以下の式３のように、原子のスピンの向きを表す変数σj（例えば、スピンが上向きの場合１、スピンが下向きの場合−１となる変数）に変更すると、以下の式４の式に変換できる。変数ｘjは、部分集合Ｓjが分割対象の集合Ｍの分割結果として選択されたか否かを示す変数であるため、変数σjも部分集合Ｓjが分割対象の集合Ｍの分割結果として選択されたか否かを示す変数とみなすことができる。即ち、σjが１であることは、ＳjがＭの分割結果として選択されたことを示し、σjが−１であることは、ＳjがＭの分割結果として選択されなかったことを示す変数である。
【００２０】
【数３】
0006760739.tif 000004
【００２１】
【数４】
0006760739.tif 000005
【００２２】
イジングモデルのハミルトニアンについて説明する。ハミルトニアンとは、エネルギーに対応する物理量である。イジングモデルのハミルトニアンは、以下の式５のように表すことができる。式５の右辺の第１項は、格子上で接続しているスピンの全ての組み合わせ（ｉ，ｊ）についての、ｉのスピンと、ｊのスピンと、ｉのスピンとｊのスピンとの間の相互作用の大きさを示す相互作用係数Ｊijと、の積の和である。式５の右辺の第２項は、外部磁場によるポテンシャルエネルギーである。外部磁場係数ｈjは、外部磁場による影響の大きさを示す係数である。
【００２３】
【数５】
0006760739.tif 000006
【００２４】
分割対象の集合Ｍの要素ｋについて、ａkj＝１となるｊの集合をＤkとすると、集合Ｄkは、以下の式６のように表すことができる。集合Ｄkは、要素ｋを含む部分集合Ｓjの番号ｊの集合であるとみなすことができる。
【００２５】
【数６】
0006760739.tif 000007
【００２６】
集合Ｄkの要素数をｄkとする。また、集合Ｄkの要素のペア（ｉ、ｊ）の集合をＰkとすると、集合Ｐkは、以下の式７のように表すことができる。
【００２７】
【数７】
0006760739.tif 000008
【００２８】
要素ｋに関するローカルなハミルトニアンの式をＨkとすると、式Ｈkを以下の式８のようにすることで、式Ｈkが最小値をとるときに、要素ｋを含む部分集合が１つのみ存在するという制約条件が満たされることになる。
【００２９】
【数８】
0006760739.tif 000009
【００３０】
イジングモデルのハミルトニアンにおける相互作用係数Ｊijを−１、外部磁場係数ｈjを−（ｄk−２）とおくと、式８のＨkは、以下の式９のように、イジングモデルのハミルトニアンの式となる。
【００３１】
【数９】
0006760739.tif 000010
【００３２】
式８に示す式Ｈkが最小値をとる場合に要素ｋを含む部分集合が１つのみ存在するという制約条件が満たされることになる理由を説明する。
ｄk個のσjのうち、値が１のものの個数をｅ個（０≦ｅ≦ｄk）とし、値が−１のものの個数を（ｄk−ｅ）個とすると、集合Ｄkについてのσjの合計は、以下の式１０のようになる。
【００３３】
【数１０】
0006760739.tif 000011
【００３４】
Ｄkに含まれる要素のペア（ｉ、ｊ）の集合であるＰkの要素の数は、ｄk（ｄk−１）／２である。Ｐkの要素のうちσiσj＝−１となるペア（ｉ、ｊ）の個数は、ｅ（ｄk−ｅ）である。Ｐkの要素のうちσiσj＝１となるペア（ｉ、ｊ）の個数は、ｄk（ｄk−１）／２−ｅ（ｄk−ｅ）である。
よって、Ｐkに含まれる全てのペア（ｉ、ｊ）について足し合わせた値は、以下の式１１のようになる。
【００３５】
【数１１】
0006760739.tif 000012
【００３６】
ここで、式８を、式１１＋式１０×（ｄk−２）のように変形し、展開することができる。この式変形及び展開を式１２に示す。
【００３７】
【数１２】
0006760739.tif 000013
【００３８】
式１２に示すように、式８は、２（ｅ−１）2−（ｄk2−３ｄk＋４）／２という式に変形できる。変形後の式の第１項は、実数の二乗であるため、必ず０以上になり、ｅ＝１の場合、値が０となる。また、変形後の式の第２項は、ｄkが定数なので定数とみなすことができる。よって、式８の値は、ｅが１の場合に最小値をとるということになる。ｅが１であることは、要素ｋを含む部分集合のうち、ちょうど１つの部分集合が集合Ｍの分割結果として選択されたことを意味している。即ち、Ｈkが最小値をとる場合、要素ｋを含む部分集合が１つのみ存在するという制約条件が満たされることになる。
図６は、制約条件とハミルトニアンとの関係を示す図である。図６の表は、ｄk＝４の場合を例に、スピンの状態σj（０≦ｊ≦４）（上向きまたは下向き、１又は−１）の全組合せ（１６通り）のそれぞれについての各種データを列挙した表である。項目６０１は、上向き（１）の値をとるスピンが１つだけ存在しているという制約条件を満たすか否かを示す項目である。例えば、図６の表の２行目のデータでは、σj（０≦ｊ≦４）のうち、σ4のみ１となり、制約条件を満たしており、項目６０１の値は、Ｔｒｕｅになっている。また、例えば、図６の表の１行目のデータでは、σj（０≦ｊ≦４）の全てが−１となり、制約条件を満たしておらず、項目６０１の値は、Ｆａｌｓｅになっている。
図６の表の項目６０２は、要素ｋに関するローカルなハミルトニアンの式である式８の値がいくつになるかを示している。図６の例では、式８の値は、−４で最小となる様子が示されている。ここで、項目６０１と項目６０２との値を見比べてみると、式８の値が最小となる場合、制約条件が満たされていることが分かる。即ち、ちょうど一つのスピンが上向きとなる解を求めるために、式８を最小化すればよいことが確認できる。
【００３９】
図７は、集合分割問題をイジングモデルに変換する変換処理の一例を示すフローチャートである。図７を用いて、Ｓ４０２の処理の詳細を説明する。
Ｓ７０１において、変換部３０２は、集合Ｍに含まれる要素ｋを示すためのパラメータｋｐを初期化する。より具体的には、変換部３０２は、主記憶装置２０２に記憶されるｋｐの値を１に決定する。値が１であるｋｐは、集合Ｍに含まれる要素１（＝ｋ）を示すこととなる。
Ｓ７０２において、変換部３０２は、ｋｐの値が集合Ｍの要素数であるｍ以下か否かを判定する。変換部３０２は、ｋｐの値がｍ以下であると判定した場合、Ｓ７０３の処理に進み、ｋｐの値が集合Ｍの要素数であるｍより大きいと判定した場合、Ｓ７０９の処理に進む。
Ｓ７０３において、変換部３０２は、Ｓ４０１で取得された候補情報に対応する部分集合Ｓjのうち、ｋｐが示す要素ｋを含む部分集合を特定し、特定した部分集合の番号（ｊ）の集合である集合Ｄkを取得する。例えば、変換部３０２は、Ｓ４０１で候補情報として候補配列が取得された場合、取得された候補配列のそれぞれについて、候補配列のｋｐの値番目の要素の値が１である場合、その候補配列に対応する部分集合を、要素ｋを含む部分集合として特定する。
Ｓ７０４において、変換部３０２は、Ｓ７０２で取得した集合Ｄkの要素数ｄkを取得する。例えば、変換部３０２は、Ｄkが配列構造のデータである場合、Ｓ７０３で取得されたＤkの要素数を取得することで、ｄkを取得する。
Ｓ７０５において、変換部３０２は、Ｓ７０２で取得した集合Ｄkに含まれる要素同士のペアの集合Ｐkを取得する。例えば、変換部３０２は、Ｄkから１つ目の要素を選択し、残った要素から２つ目の要素を選択し、選択した要素同士をペアとして決定する。更に、変換部３０２は、この処理を全てのペアを選択するまで繰り返すことで、集合Ｐkを取得する。
Ｓ７０６において、変換部３０２は、式５に示すようなイジングモデルのハミルトニアンの式における相互作用係数Ｊij、及び磁場係数ｈjを決定する。変換部３０２は、Ｊijの値を−１として決定する。また、変換部３０２は、Ｓ７０４で取得したｄkに基づいて、ｈjの値を−（ｄk−２）に決定する。
【００４０】
Ｓ７０７において、変換部３０２は、ｋｐが示すＭの要素ｋについてのハミルトニアンＨkを生成する。例えば、補助記憶装置２０３が予めＨkの形式である式９の情報を記憶しているとする。式９の右辺の第１項のΣは、集合Ｐkに含まれる全ての要素（Ｄkの要素同士のペア）について、Ｊijσiσjの合計をとることを意味する。また、式９の右辺の第２項のΣは、集合Ｄkに含まれる全ての要素について、ｈjσjの合計をとることを意味する。
式９のＨkは、イジングモデル計算デバイス１０１等により、Ｈkが最小値をとるσj（１≦ｊ≦ｄk）の値を計算するために利用される式である。そのため、式９のうち、σ以外の変数（Ｐk、Ｊij、ｈj、Ｄk）の値については、確定させる必要がある。本実施形態では、変換部３０２は、式９のうち、σ以外の変数（Ｐk、Ｊij、ｈj、Ｄk）の値を決定することで、要素ｋについてのハミルトニアンを生成することとする。
変換部３０２は、式９のＰkの値を、Ｓ７０５で取得した集合Ｐkとして決定する。変換部３０２は、式９のＤkの値を、Ｓ７０３で取得した集合Ｄkとして決定する。また、変換部３０２は、式９のＪijの値を、Ｓ７０６で決定したＪij（−１）として決定する。また、変換部３０２は、式９のｈjの値を、Ｓ７０６で決定したｈj（−（ｄk−２））として決定する。そして、変換部３０２は、決定した変数（Ｐk、Ｊij、ｈj、Ｄk）を式９に当てはめることで、要素ｋについてのローカルなハミルトニアンの式を生成する。変換部３０２は、生成したローカルなハミルトニアンの式の情報を主記憶装置２０２に記憶する。
【００４１】
Ｓ７０８において、変換部３０２は、ｋｐの値に１を加えた後、Ｓ７０２の処理に進む。
Ｓ７０９において、変換部３０２は、Ｓ７０７で生成した集合Ｍの各要素ｋに関するローカルなイジングモデルのハミルトニアンＨkを、式１３を用いて、分割対象の集合の各要素ｋについて足し合わせ、全体のイジングモデルのハミルトニアンＨの式の情報を生成する。このように、変換部３０２は、集合分割問題に対応するイジングモデルのハミルトニアンの式を生成することで、集合分割問題をイジングモデルに変換することができる。即ち、Ｈに対応するイジングモデルが、集合分割問題に対応するイジングモデルであるということになる。
【００４２】
【数１３】
0006760739.tif 000014
【００４３】
図４のフローチャートの説明に戻る。
Ｓ４０３において、デバイス制御部３０３は、Ｓ４０２で生成されたハミルトニアンＨの式の情報をイジングモデル計算デバイス１０１に送信する。デバイス制御部３０３は、Ｈの情報を送信することで、イジングモデル計算デバイスに対して、Ｈが最小値をとる場合の各スピンの状態（σ1〜σn）の計算を指示する。
イジングモデル計算デバイス１０１は、Ｓ４０３で送信されたＨの情報に基づいて、Ｈが最小値をとる場合のＨに対応するイジングモデルの各スピンの状態を算出する。例えば、イジングモデル計算デバイス１０１は、Ｈに対応するイジングモデルの各スピン（σ1〜σn）について、スピン回路を用意する。そして、イジングモデル計算デバイス１０１は、Ｈに対応するイジングモデルを表すように、各スピン回路に初期スピン状態値、相互作用係数、外部磁場係数を設定する。イジングモデル計算デバイス１０１は、各スピン回路の初期スピン状態値として、ランダムに１又は−１の値を設定する。例えば、イジングモデル計算デバイス１０１は、乱数を発生させ、発生させた乱数に基づいて、各スピン回路の初期スピン状態値を１又は−１の何れにするかをランダムに決定する。その後、各スピン回路は、Ｈの値を最小値とするように、各スピンの状態を変化させていく。イジングモデル計算デバイス１０１は、第１世代から設定された数の世代が経過した場合、その世代における各スピンの状態を示す情報を情報処理装置１００に送信する。
【００４４】
図８は、イジングモデル計算デバイス１０１の実装の一例を説明する図である。図８を用いて、イジングモデル計算デバイス１０１が各スピン回路を実装する例を説明する。図８は、集合Ｍ＝｛１｝、Ｄk＝｛１、２、３、４｝、ｄk＝４、Ｐk＝｛（１、２）、（１、３）、（１、４）、（２、３）、（２、４）、（３、４）｝である式１３のハミルトニアンに対応するイジングモデルの例を説明する図である。図８のイジングモデルは、格子状に配置されたスピンが２層重なっているイジングモデルである。イジングモデル計算デバイス１０１は、例えば、内部のスピン回路のメモリ素子に、イジングモデル内の各スピン（図８の各格子点）に対応する設定情報を記憶することで、イジングモデルを実装する。まず、イジングモデル計算デバイス１０１は、各スピンの相互作用係数及び外部磁場係数を全て０に決定する。この状態では、各スピンは、周囲のスピンの影響を受けないことになる。
図８のイジングモデルの下層の各行は、Ｄkに含まれる要素ｊに対応するスピンσjに対応する。イジングモデル計算デバイス１０１は、下層の同じ行で隣接しあう各スピンの相互作用係数を＋１に決定することで、下層の同じ行の全てのスピンの向きを同一とすることができる。これにより、下層の行ｉの全てのスピンは、同様に、σiのスピンの状態（部分集合Ｓiが分割結果として選択されているか否か）を示すものとみなすことができる。
【００４５】
イジングモデル計算デバイス１０１は、上層を利用することで、下層の各行同士を、接続する。イジングモデル計算デバイス１０１は、σ1とσ2とを接続する場合、下層１行目の左端のスピンと上層１行目の左端のスピンとの間の相互作用係数を１に決定し、下層２行目の左端のスピンと上層２行目の左端のスピンとの間の相互作用係数を１に決定する。そして、イジングモデル計算デバイス１０１は、上層１行目の左端のスピンと上層２行目の左端のスピンとの間の相互作用係数を−１に決定する。それにより、イジングモデル計算デバイス１０１は、σ1の行とσ2の行との接続を、相互作用係数−１で接続されたことと同様の接続とすることができる。イジングモデル計算デバイス１０１は、同様に、σ1の行とσ3の行とを、σ1の行とσ4の行とを、σ2の行とσ3の行とを、σ2の行とσ4の行とを、σ3の行とσ4の行とを、相互作用係数−１となるよう接続する。
図８の例では、ｄk＝４であるため、外部磁場係数ｈjは、−（ｄk−２）＝−（４−２）＝−２となる。そこで、イジングモデル計算デバイス１０１は、外部磁場係数−２を表すために、下層の各行について２つのスピンの外部磁場係数を−１に決定する。
以上の処理により、イジングモデル計算デバイス１０１は、指定されたハミルトニアンに対応するイジングモデルを実装する。そして、イジングモデル計算デバイス１０１は、ハミルトニアンの値を最小値とする各スピンの状態を計算する。イジングモデル計算デバイス１０１は、計算開始から設定された世代が経過した後、下層の各行のスピンの状態値を取得する。下層の各行のスピンの状態値は、各行に対応する部分集合が分割結果として選択されたか否かを示す。イジングモデル計算デバイス１０１は、取得したスピンの状態値の情報を情報処理装置１００に送信する。
また、情報処理装置１００は、以下のようにして、イジングモデル計算デバイス１０１による計算結果を取得してもよい。即ち、デバイス制御部３０３は、イジングモデル計算デバイス１０１に計算を指示した時刻から設定された期間が経過した場合、イジングモデル計算デバイス１０１に対して、イジングモデルの下層の各行のスピンの状態値を要求することとしてもよい。例えば、イジングモデル計算デバイス１０１は、ハミルトニアンの値を最小値とする各スピンの状態を、計算開始から設定された世代が経過するまで計算し続けるのではなく、情報処理装置１００からの要求を受信するまで計算し続ける。そして、イジングモデル計算デバイス１０１は、情報処理装置からの要求を受信した場合、イジングモデルの下層の各行のスピンの状態値を取得し、取得した状態値の情報を情報処理装置１００に送信する。また、イジングモデル計算デバイス１０１は、ハミルトニアンの値を最小値とする各スピンの状態を、情報処理装置１００からの要求を受信した後も、計算し続けることとしてもよい。その場合、イジングモデル計算デバイス１０１は、情報処理装置から改めて計算結果の要求を受信した場合、イジングモデルの下層の各行のスピンの状態値を取得し、取得した状態値の情報を情報処理装置１００に送信する。
【００４６】
図９は、集合Ｍ＝｛１、２、３、・・・、ｍ｝であり、部分集合の候補がｎ個存在し、Ｍの要素毎にｍ個の式９のローカルなハミルトニアンが存在する場合の式１３のハミルトニアンに対応するイジングモデルの概要を説明する図である。図９の例では、Ｍの要素１についてのローカルなハミルトニアンの式を図８におけるハミルトニアンの式と同様であるとする。
図９の例では、複数のローカルなハミルトニアンを含む全体のハミルトニアンに対応するイジングモデルは、図８同様に、格子状に配置されたスピンが２層重なっているイジングモデルであるとする。図９は、全体のハミルトニアンに対応する２層のイジングモデルを上部から俯瞰した様子を示す図である。
下層の各行は、図８と同様に、各スピンが相互作用係数１で接続されている。そのため、下層の各行の全てのスピンは、同じ状態値をとる。斜線で表した領域Ｈ1は、要素１についてのローカルなハミルトニアンＨ1に対応する部分が実装されている領域である。実装の内容は、図８と同様である。領域Ｈ2は、要素２についてのローカルなハミルトニアンＨ2に対応する部分が実装されている領域である。また、領域Ｈmは、要素ｍについてのローカルなハミルトニアンＨmに対応する部分が実装されている領域である。イジングモデル計算デバイス１０１は、各領域（Ｈ1、Ｈ2、・・・、Ｈm）が重ならないように実装する。領域Ｈ1以外の領域についての実装の方法は、領域Ｈ1と同様、即ち、図８と同様である。イジングモデル計算デバイス１０１は、全体のハミルトニアンに対応するイジングモデルを図９に示すようなイジングモデルであるとして実装し、全体のハミルトニアンが最小値となる各スピンの状態を計算する。イジングモデル計算デバイス１０１は、計算開始から設定された世代が経過した後、下層の各行のスピンの状態値を取得する。下層の各行のスピンの状態値は、各行に対応する部分集合が分割結果として選択されたか否かを示す。イジングモデル計算デバイス１０１は、取得したスピンの状態値の情報を情報処理装置１００に送信する。
【００４７】
Ｓ４０４において、デバイス制御部３０３は、イジングモデル計算デバイス１０１からＳ４０３で指示した計算結果であるイジングモデルの各スピンの状態を示す情報を受信する。Ｓ４０４で取得される情報は、部分集合Ｓjのそれぞれに対応するσjが１であるか−１であるかを示す情報となる。決定部３０４は、値が１であるσjに対応する部分集合Ｓjを、集合Ｍの分割結果として選択されたものとして決定する。また、決定部３０４は、値が−１であるσjに対応する部分集合Ｓjを、集合Ｍの分割結果として選択されなかったものとして決定する。
Ｓ４０５において、決定部３０４は、Ｓ４０４で集合Ｍの分割結果として決定した部分集合Ｓjの情報を出力する。例えば、決定部３０４は、集合Ｍの分割結果として決定した部分集合Ｓjを全て表示する確認画面を情報処理装置１００の表示部に表示する。ユーザは、表示された確認画面を視認することで、集合Ｍの分割結果が表示されている部分集合でよいか否かを判断することができる。また、決定部３０４は、集合Ｍの分割結果として決定した部分集合Ｓjの情報を、情報処理装置１００の記憶部に電子ファイルとして記憶することとしてもよい。補助記憶装置２０３は、情報処理装置１００の記憶部の一例である。また、決定部３０４は、集合Ｍの分割結果として決定した部分集合Ｓjの情報を、外部の装置に送信することで、出力することとしてもよい。
【００４８】
以上、本実施形態の処理により、計算システムは、集合分割問題に対応するイジングモデルにおけるハミルトニアンの式を生成することで、集合分割問題をイジングモデルの問題に変換することができる。これにより、計算システムは、イジングモデル計算デバイス１０１を介して、効率的に集合分割問題の解を求めることを可能とすることができる。
【００４９】
＜その他の実施形態＞
以上、本発明の好ましい実施形態について詳述したが、本発明は係る特定の実施形態に限定されるものではない。
例えば、上述した計算システムの機能構成の一部又は全てをハードウェアとして情報処理装置１００に実装してもよい。
【符号の説明】
【００５０】
１００  情報処理装置
１０１  イジングモデル計算デバイス
３０２  変換部
【図１】
0006760739.tif 000019
【図２】
0006760739.tif 000020
【図３】
0006760739.tif 000021
【図４】
0006760739.tif 000022
【図５】
0006760739.tif 000023
【図６】
0006760739.tif 000024
【図７】
0006760739.tif 000025
【図８】
0006760739.tif 000026
【図９】
0006760739.tif 000027