(57)【要約】【課題】量子アニーリングマシンやイジングマシンを用いて、二つのグラフの類似性もしくは同型性を判定することを可能にする。【解決手段】処理装置１０は、二つのグラフの類似性もしくは同型性を判定する処理装置であって、二つのグラフの入力を受け付けるグラフ入力部１１と、二つのグラフに基づいて、二つのグラフから構成される部分グラフの類似性判定問題もしくは同型性判定問題を解く場合に用いる目的関数を作成する問題変換部１２と、を有する。【選択図】図１
2020149664.tif 000002
【特許請求の範囲】
【請求項１】
二つのグラフの類似性もしくは同型性を判定する処理装置であって、
二つのグラフの入力を受け付けるグラフ入力部と、
前記二つのグラフに基づいて、前記二つのグラフから構成される部分グラフの類似性判定問題もしくは同型性判定問題を解く場合に用いる目的関数を作成する問題変換部と、
を有することを特徴とする処理装置。
【請求項２】
前記目的関数が下限値を取る解が存在する場合には、前記二つのグラフの一方のグラフが他方の部分グラフとして含まれると判定し、前記目的関数が下限値を取る解が存在しない場合には、前記二つのグラフの一方のグラフが他方の誘導部分グラフとして含まれないと判定する判定部
をさらに有することを特徴とする請求項１に記載の処理装置。
【請求項３】
前記目的関数の解に対応する目的関数の値が小さいほど類似度が高くなるように、前記二つのグラフの類似度を計算する計算部
をさらに有することを特徴とする請求項１に記載の処理装置。
【請求項４】
前記目的関数は、０または１を取る変数ｘに関するＱＵＢＯの目的関数であり、
前記目的関数は、前記二つのグラフの一方の頂点集合から他方のグラフの頂点集合への写像が全単射となる場合に最も値が小さくなるよう定義された第１の関数と、前記二つのグラフの一方における頂点の接続関係と他方のグラフの対応する頂点間の接続関係の一致度が高いほど値が小さくなるよう定義された第２の関数と、の重みづけ和に基づく関数である
ことを特徴とする請求項１〜３のいずれか一つに記載の処理装置。
【請求項５】
前記目的関数は、−１または１を取る変数ｓに関するイジングハミルトニアンであり、
前記目的関数は、前記二つのグラフの一方の頂点集合から他方のグラフの頂点集合への写像が全単射となる場合に最も値が小さくなるよう定義された第１の関数と、前記二つのグラフの一方における頂点の接続関係と他方のグラフの対応する頂点間の接続関係の一致度が高いほど値が小さくなるよう定義された第２の関数との重みづけ和に基づく関数である
ことを特徴とする請求項１〜３のいずれか一つに記載の処理装置。
【請求項６】
前記目的関数の第１の関数の重みは、前記目的関数の第２の関数の重みよりも大きく設定されることを特徴とする請求項４または請求項５に記載の処理装置。
【請求項７】
二つのグラフの類似性もしくは同型性を判定する処理装置が実行する処理方法であって、
二つのグラフの入力を受け付けるステップと、
前記二つのグラフに基づいて、前記二つのグラフから構成される部分グラフの類似性もしくは同型性判定問題を解く場合に用いる目的関数を生成するステップと、
を含んだことを特徴とする処理方法。
【請求項８】
コンピュータを、請求項１〜６のいずれか一つに記載の処理装置として機能させるための処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、処理装置、処理方法及び処理プログラムに関する。
【背景技術】
【０００２】
グラフ同型判定問題を量子アニーリングマシンやイジングマシンを用いて解くためのＱＵＢＯへの変換やイジング問題への変換が知られている（非特許文献１〜４参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】J.R.Ullmann,  “An  Algorithm  for  Subgraph  Isomorphism”，J.ACM,  Vol.23,  No.1,  pp.31-42（1976）.
【非特許文献２】A.  Lucas,  “Ising  formulations  of  many  NP  problems”,  frontiers  in  Physics（2014）,  ［online］，［平成３１年３月４日検索］，インターネット＜ＵＲＬ：https://www.frontiersin.org/articles/10.3389/fphy.2014.00005/full＞
【非特許文献３】D-Wave  Systems  Inc,  “The  D-Wave  2000QTM  Quantum  Computer  Technology  Overview”，［online］，［平成３１年２月４日検索］，インターネット＜ＵＲＬ：https://www.dwavesys.com/sites/default/files/D-Wave  2000Q  Tech  Collateral_1029F.pdf.＞
【非特許文献４】Takahiro  Inagaki  et  al.,  “A  coherent  Ising  machine  for  2000-node  optimization  problems”,  Science,  vol.  354,  Issue  6312,  pp.  603-606（2016）.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ここで、グラフ同型問題からさらに発展させた誘導部分グラフ同型判定問題および部分グラフ同型判定問題の解法は、大きなグラフ構造を持つ回路から与えられた不正回路を検出するといった用途や、化学構造式で示される物質中に特定の化学結合に類似する化学結合が存在するか否かの判定、パターン認識等に応用が可能である。しかしながら、誘導部分グラフ同型判定問題及び部分グラフ同型判定問題では、グラフのどの部分に他方のグラフが含まれるかは不明であるため、グラフ同型問題よりもさらに困難な問題である。また、このような実問題への応用では、２つのグラフが同型であるか否かではなく、２つのグラフが類似するか否かを判定したいという要望もある。
【０００５】
本発明は、上記に鑑みてなされたものであって、量子アニーリングマシンやイジングマシンを用いて、二つのグラフの類似性もしくは同型性を判定することを可能にする処理装置、処理方法及び処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上述した課題を解決し、目的を達成するために、本発明に係る処理装置は、二つのグラフの類似性もしくは同型性を判定する処理装置であって、二つのグラフの入力を受け付けるグラフ入力部と、二つのグラフに基づいて、二つのグラフから構成される部分グラフの類似性判定問題もしくは同型性判定問題を解く場合に用いる目的関数を作成する問題変換部と、有することを特徴とする。
【０００７】
また、本発明に係る処理方法は、二つのグラフの類似性もしくは同型性を判定する処理装置が実行する処理方法であって、二つのグラフの入力を受け付けるステップと、二つのグラフに基づいて、二つのグラフから構成される部分グラフの類似性もしくは同型性判定問題を解く場合に用いる目的関数を生成するステップと、を含んだことを特徴とする。
【発明の効果】
【０００８】
本発明によれば、量子アニーリングマシンやイジングマシンを用いて、二つのグラフの類似性もしくは同型性を判定することを可能にする。
【図面の簡単な説明】
【０００９】
【図１】図１は、実施の形態１に係る処理装置の概略構成を示す図である。
【図２】図２は、図１に示すグラフ入力部による入力処理の処理手順を示すフローチャートである。
【図３】図３は、図１に示す問題変換部による問題変換処理の処理手順を示すフローチャートである。
【図４】図４は、図１に示す判定部による判定処理の処理手順を示すフローチャートである。
【図５】図５は、実施の形態２に係る処理装置の概略構成を示す図である。
【図６】図６は、図５に示す判定部による判定処理の処理手順を示すフローチャートである。
【図７】図７は、処理対象のグラフの一例を示す図である。
【図８】図８は、処理対象のグラフの一例を示す図である。
【図９】図９は、処理対象のグラフの一例を示す図である。
【図１０】図１０は、処理対象のグラフの一例を示す図である。
【図１１】図１１は、実施の形態３に係る処理装置の概略構成を示す図である。
【図１２】図１２は、図１１に示す判定部による判定処理の処理手順を示すフローチャートである。
【図１３】図１３は、処理対象のグラフの一例を示す図である。
【図１４】図１４は、処理対象のグラフの一例を示す図である。
【図１５】図１５は、図１３に示すグラフに類似するグラフの一例を示す図である。
【図１６】図１６は、処理対象のグラフの一例を示す図である。
【図１７】図１７は、処理対象のグラフの一例を示す図である。
【図１８】図１８は、図１６に示すグラフに類似するグラフの一例を示す図である。
【図１９】図１９は、プログラムが実行されることにより、処理装置が実現されるコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１０】
以下、図面を参照して、本発明の一実施形態を詳細に説明する。なお、この実施の形態により本発明が限定されるものではない。また、図面の記載において、同一部分には同一の符号を付して示している。
【００１１】
［従来の数理的背景］
グラフ同型判定問題の量子アニーリングマシンまたはイジングマシンによる解法を説明する。
【００１２】
グラフ同型判定問題は、グラフＧ１＝（Ｖ１，Ｅ１）と、グラフＧ２＝（Ｖ２，Ｅ２）が与えられたときに、Ｇ１とＧ２とが同型か否かを判定する問題である。ただし、Ｖ１とＶ２は頂点の集合、Ｅ１とＥ２はエッジの集合である。Ｇ１とＧ２とが同型であるとは、∀ｕ，ｖ∈Ｖ１，ｕｖ∈Ｅ１⇔ｆ（ｕ）ｆ（ｖ）∈Ｅ２を満たすような全単射写像ｆ：Ｖ１→Ｖ２が存在することと定義される。
【００１３】
グラフ同型判定問題は、計算量が現時点で明確に示されていないものの、困難な問題であるとして知られている。このため、量子アニーリングマシン（非特許文献３参照）やイジングマシン（非特許文献４参照）を用いて高速に解くための手法が提案されている（非特許文献２参照）。量子アニーリングマシンやイジングマシンは、ＱＵＢＯ（Quadratic  Unconstrained  Binary  Optimization）と呼ばれる問題と、Ising  Hamiltonian（イジングハミルトニアン）の最小化を行うイジング問題とを短時間で解くことができる。また同時に、可能な計算がこれらの最適化問題を解くことに限られる。したがって、これらの計算機を使用するためには、問題を適切に最適化問題へと変換する必要がある。なお、ＱＵＢＯとイジングハミルトニアンの最小化問題とは、変数変換を行なうことによって相互に変換可能であるため、ここでは、グラフ同型判定問題をＱＵＢＯに変換する手法を述べる。
【００１４】
ＱＵＢＯは、正整数ｎ、行列Ｑ∈Ｒｎ×ｎ、ベクトルｘ∈｛０，１｝ｎに対して（１）式のように２次多項式を最小化する問題である。
【００１５】
【数１】
2020149664.tif 000003
【００１６】
ｑｉｊをＱのｉ行ｊ列の要素、ｘｉをベクトルｘの第ｉ要素とすると、（２）式のように表すことができる。
【００１７】
【数２】
2020149664.tif 000004
【００１８】
つまりｑｉｊ＋ｑｊｉの値で係数が決まるので、Ｑとしては、ｉ＞ｊについて、ｑｉｊ＝０であるような行列、すなわち、上三角行列のみを考えてもよい。
【００１９】
ＱＵＢＯで、ｉ∈Ｖ１とｖ∈Ｖ２とを対応付ける写像ｆ：Ｖ１→Ｖ２を得るため、グラフ同型判定問題においては、次の（３），（４）式のように二値ベクトルｘを定義する。ただし、ｎ＝｜Ｖ１｜（＝｜Ｖ２｜）とする。
【００２０】
【数３】
2020149664.tif 000005
【００２１】
【数４】
2020149664.tif 000006
【００２２】
さらに、Ｇ１とＧ２とがグラフ同型であることを最小化問題として表現するため、グラフ同型の制約条件を４つに分解し、それぞれについて次の（５）式〜（８）式のように最小化すべき値（制約項）ＨＡ，ＨＢ，ＨＣ，ＨＤを定める。
【００２３】
【数５】
2020149664.tif 000007
【００２４】
【数６】
2020149664.tif 000008
【００２５】
【数７】
2020149664.tif 000009
【００２６】
【数８】
2020149664.tif 000010
【００２７】
ＨＡとＨＢとは、写像ｆ：Ｖ１→Ｖ２が全単射であることを表現する。すなわち、ＨＡは、各ｉ∈Ｖ１において、ただ一つの変数ｘｉｖが１をとり、それ以外では０を取るときに最小値を取る制約である。ＨＢは、各ｖ∈Ｖ２において、ただ一つの変数ｘｉｖが１をとり、それ以外では０を取るときに最小値を取る制約である。
【００２８】
ＨＣとＨＤとは、頂点の接続関係が一致していることを表現する。すなわち、ＨＣは、グラフＧ１で接続していない頂点が、グラフＧ２で接続することを禁止する制約である。ＨＤは、グラフＧ２で接続していない頂点が、グラフＧ１で接続することを禁止する制約である。
【００２９】
実際に、量子アニーリングマシンやイジングマシンが最小化可能であるのは、（１）式が示すように１つの式の値に限られる。そこで上記の制約項にスカラー値による重み付けを行いつつ和をとった以下のような（９）式を、ＱＵＢＯの目的関数とする。
【００３０】
【数９】
2020149664.tif 000011
【００３１】
ここで、α，β，γ，δ∈Ｒは、ハイパーパラメータであり、量子アニーリングマシンやイジングマシンで解くにあたり、正の値を設定する。
【００３２】
グラフ同型の制約を全て満たすようなｘｉｖの値の割り当てにおいて、またその時に限り、ＨＡ＝ＨＢ＝ＨＣ＝ＨＤ＝０となる。したがって、Ｇ１とＧ２がグラフ同型であるならば、Ｈの下限値（基底状態）は０である。つまり、Ｈを目的関数とするＱＵＢＯを解くことによって、Ｈ＝０となるベクトルｘを得られた場合には、同型であり、そうでない場合には、同型でない、としてグラフ同型判定問題を解くことができる。
【００３３】
［実施の形態１］
このように、従来、グラフ同型判定問題を量子アニーリングマシンやイジングマシンを用いて解を得るためのＱＵＢＯへの変換やイジングハミルトニアンへの変換は、既に知られている。これに対し、本実施の形態１では、誘導部分グラフ同型判定問題及び部分グラフ同型判定問題への変換を提案する。
【００３４】
Ｇ１とＧ２とが誘導部分グラフ同型であるとは、∀ｕ，ｖ∈Ｖ１，ｕｖ∈Ｅ１⇔ｆ（ｕ）ｆ（ｖ）∈Ｅ２を満たすような単射写像ｆが存在することである。また、Ｇ１とＧ２とが部分グラフ同型であるとは、∀ｕ，ｖ∈Ｖ１，ｕｖ∈Ｅ１⇒ｆ（ｕ）ｆ（ｖ）∈Ｅ２を満たすような単射写像ｆが存在することである。これらの定義は、Ｇ２の一部がＧ１と同型であることを示す。Ｇ２のどの部分にＧ１が含まれるかは不明であるため、これらは、グラフ同型問題に比べてさらに困難な問題である。
【００３５】
まず、実施の形態１では、誘導部分グラフ同型判定問題を処理する処理装置について説明する。図１は、実施の形態１に係る処理装置の概略構成を示す図である。図１に示す処理装置１０は、二つのグラフが与えられたとき、一方が他方の誘導部分グラフとして含まれるか否かを判定する誘導部分グラフ同型判定問題を解くための処理装置である。処理装置１０は、グラフ入力部１１、問題変換部１２及び判定部１３を有する。なお、処理装置１０は、例えば、ＲＯＭ（Read  Only  Memory）、ＲＡＭ（Random  Access  Memory）、ＣＰＵ（Central  Processing  Unit）等を含むコンピュータ等に所定のプログラムが読み込まれて、ＣＰＵが所定のプログラムを実行することで実現される。
【００３６】
グラフ入力部１１は、二つのグラフの入力を受け付ける。図２は、図１に示すグラフ入力部１１による入力処理の処理手順を示すフローチャートである。図２に示すように、グラフ入力部１１は、グラフＧ１とグラフＧ２との入力を受け付けると（ステップＳ１）、グラフＧ１とグラフＧ２とをメモリ上に格納する（ステップＳ２）。
【００３７】
問題変換部１２は、二つのグラフに基づいて、二つのグラフから構成される誘導部分グラフ同型判定問題を解く場合に用いるＱＵＢＯの目的関数を作成する。または、問題変換部１２は、二つのグラフから構成される誘導部分グラフ同型判定問題を解く場合に用いるイジングハミルトニアンを作成する。例えば、問題変換部１２は、二つのグラフに基づいて作成したＱＵＢＯの目的関数を変数変換し、イジングハミルトニアンを作成する。問題変換部１２は、入力されたグラフＧ１，Ｇ２を、ＱＵＢＯ、または、イジングハミルトニアンに変換して出力する。
【００３８】
図３は、図１に示す問題変換部１２による問題変換処理の処理手順を示すフローチャートである。問題変換部１２は、グラフ入力部１１が入力を受け付けたグラフＧ１とグラフＧ２、及び、変換後の問題種別（ＱＵＢＯまたはイジング問題を選択）を入力とする（ステップＳ１１）。ここで、Ｇ１＝（Ｖ１，Ｅ１），Ｇ２＝（Ｖ２，Ｅ２）の頂点数は、等しくなく、｜Ｖ１｜＝ｎ＜ｍ＝｜Ｖ２｜とする。なお、以降において、目的関数は、ＱＵＢＯの目的関数とイジングハミルトニアンとの双方を包含するものとする。
【００３９】
そして、問題変換部１２は、グラフＧ１とＧ２から、ＱＵＢＯの目的関数Ｈ´を、以降の処理を行って作成する（ステップＳ１２）。
【００４０】
まず、問題変換部１２では、制約項ＨＡ´，ＨＢ´，ＨＣ，ＨＤを以下の（１０）式〜（１３）式のように定義する。
【００４１】
【数１０】
2020149664.tif 000012
【００４２】
【数１１】
2020149664.tif 000013
【００４３】
【数１２】
2020149664.tif 000014
【００４４】
【数１３】
2020149664.tif 000015
【００４５】
そして、問題変換部１２では、上記のＨＡ´，ＨＢ´，ＨＣ，ＨＤを用いて、（１４）式のようにＨ´を定義する。
【００４６】
【数１４】
2020149664.tif 000016
【００４７】
ＨＡ´とＨＢ´とは、二つグラフの一方の頂点集合から他方のグラフの頂点集合への写像が単射となる場合に最も値が小さくなるよう定義された第１の関数である。すなわち、ＨＡ´とＨＢ´とは、二つのグラフの頂点の一致性を評価する関数である。ＨＣとＨＤとは、二つグラフの一方における頂点の接続関係と他方のグラフの対応する頂点間の接続関係の一致度が高いほど値が小さくなるよう定義された第２の関数である。すなわち、ＨＣとＨＤとは、二つのグラフの辺の接続の一致性を評価する関数である。目的関数であるＨ´は、第１の関数と第２の関数との重み付け和である。なお、α，β，γ，δ∈Ｒは、ハイパーパラメータであり、量子アニーリングマシンやイジングマシンで解くにあたり、正の値を設定する。例えば、α，β，γ，δは、α＝１，β＝１，γ＝３，δ＝３である。ＨＡとＨＢとが写像ｆが全単射であることを表現するのに対し、ＨＡ´とＨＢ´とは、ｆが単射であることを表現する。
【００４８】
｜Ｖ２｜＝ｍとなったことから、総和の添え字ｖの範囲が１からｍまでとなっている。さらに、ＨＢ´では、括弧内の定数部分が１から１／２へ変更されている。これは、各ｖ∈Ｖ２に対して対応付けられるｉ∈Ｖ１が１つだけ存在するか、または、１つも存在しないことを強制するための制約である。つまり、これは、（１５）式に示す和が０または１であることを強制するための制約である。
【００４９】
【数１５】
2020149664.tif 000017
【００５０】
（１１）式の括弧内の定数部分を１／２とすることによって（１５）式に示す和が、０か、１のときに、最小の値を取ることが保証される。なお、ＨＣ，ＨＤに関しては、グラフ同型判定問題から変更はない。
【００５１】
誘導部分グラフ同型の制約を全て満たすようなｘｉｖの値の割り当てにおいて、また、その時に限り、Ｈ´Ａ＝ＨＣ＝ＨＤ＝０、Ｈ´Ｂ＝βｍ／４となる。したがって、Ｇ１とＧ２が誘導部分グラフ同型であるならば、Ｈ´の下限値（基底状態）は、βｍ／４である。つまり、Ｈ´を目的関数とするＱＵＢＯを解くことによって、Ｈ´＝βｍ／４となるベクトルｘを得られた場合には、同型であり、そうでない場合には、同型でない、として誘導部分グラフ同型判定問題を解くことができる。
【００５２】
そして、問題変換部１２は、変換後の問題種別がＱＵＢＯであるか否かを判定する（ステップＳ１３）。問題変換部１２は、変換後の問題種別がＱＵＢＯであると判定した場合（ステップＳ１３：Ｙｅｓ）、ＱＵＢＯの目的関数としてＨ´を出力する。
【００５３】
一方、問題変換部１２は、変換後の問題種別がＱＵＢＯではなくイジング問題であると判定した場合（ステップＳ１３：Ｎｏ）、ＱＵＢＯの目的関数を変数変換し、イジングハミルトニアンを作成し（ステップＳ１４）、イジングハミルトニアンを出力する。
【００５４】
ステップＳ１４の処理について説明する。問題変換部１２は、Ｈ´を（１６）式のように変換する。
【００５５】
【数１６】
2020149664.tif 000018
【００５６】
問題変換部１２は、Ｈ´に含まれるすべての変数ｘに対して、（１６）式の右辺を代入して、変数ｘを変数ｓの式として変換した式をイジングハミルトニアンとする。そして、問題変換部１２は、変換後の問題種別がイジング問題である場合、このイジングハミルトニアンを出力する。
【００５７】
判定部１３は、問題変換部１２から出力されたＱＵＢＯの目的関数Ｈ´またはイジングハミルトニアンを基に、二つのグラフの一方のグラフが他方の誘導部分グラフとして含まれるか否かを判定する。
【００５８】
図４は、図１に示す判定部１３による判定処理の処理手順を示すフローチャートである。まず、判定部１３は、変換後の問題種別がＱＵＢＯであるかを判定する（ステップＳ２１）。
【００５９】
判定部１３が、変換後の問題種別がＱＵＢＯであると判定した場合について説明する（ステップＳ２１：Ｙｅｓ）。この場合、判定部１３は、問題変換部１２からＱＵＢＯの目的関数Ｈ´が入力されるため、Ｈ´を目的関数とするＱＵＢＯを解く（ステップＳ２２）。そして、判定部１３は、ＱＵＢＯの目的関数が下限値を取る解が存在するか否かを判定する（ステップＳ２３）。
【００６０】
判定部１３は、ＱＵＢＯの目的関数が下限値を取る解が存在すると判定した場合には（ステップＳ２３：Ｙｅｓ）、Ｇ１がＧ２の誘導部分グラフとして含まれると判定する（ステップＳ２４）。言い換えると、判定部１３は、二つのグラフの一方のグラフが他方の誘導部分グラフとして含まれると判定する。
【００６１】
これに対し、判定部１３は、ＱＵＢＯの目的関数が下限値を取る解が存在しないと判定した場合には（ステップＳ２３：Ｎｏ）、Ｇ１がＧ２の誘導部分グラフとして含まれないと判定する（ステップＳ２５）。言い換えると、判定部１３は、二つのグラフの一方のグラフが他方の誘導部分グラフとして含まれないと判定する。
【００６２】
また、判定部１３が、変換後の問題種別がイジング問題であると判定した場合について説明する（ステップＳ２１：Ｎｏ）。この場合、判定部１３は、問題変換部１２からイジングハミルトニアンが入力されるため、イジング問題を解く（ステップＳ２６）。そして、判定部１３は、イジングハミルトニアンが下限値を取る解が存在するか否かを判定する（ステップＳ２７）。
【００６３】
判定部１３は、イジングハミルトニアンが下限値を取る解が存在すると判定した場合には（ステップＳ２７：Ｙｅｓ）、Ｇ１がＧ２の誘導部分グラフとして含まれると判定する（ステップＳ２８）。言い換えると、判定部１３は、二つのグラフの一方のグラフが他方の誘導部分グラフとして含まれると判定する。これに対し、判定部１３は、イジングハミルトニアンが下限値を取る解が存在しないと判定した場合には（ステップＳ２７：Ｎｏ）、Ｇ１がＧ２の誘導部分グラフとして含まれないと判定する（ステップＳ２９）。言い換えると、判定部１３は、二つのグラフの一方のグラフが他方の誘導部分グラフとして含まれないと判定する。
【００６４】
［実施の形態１の効果］
このような処理を行うことによって、実施の形態１では、二つのグラフから構成される誘導部分グラフ同型判定問題を解くためのＱＵＢＯの目的関数を作成する。また、このような処理を行うことによって、実施の形態１では、二つのグラフから構成される誘導部分グラフ同型判定問題を解く場合に用いるイジングハミルトニアンを作成する。実施の形態１では、これらに基づくＱＵＢＯまたはイジング問題を解くことによって、二つのグラフが与えられたとき、一方が他方の誘導部分グラフとして含まれるか否かを判定することができる。
【００６５】
また、本実施の形態１では、部分グラフ同型判定問題をＱＵＢＯの目的関数またはイジングハミルトニアンに変換することによって、量子アニーリングマシンまたはイジングマシンを用いて、誘導部分グラフ同型判定問題を高速に解くことが可能となる。
【００６６】
この実施の形態１に示す誘導部分グラフ同型判定問題の解法は、大きなグラフ構造を持つ回路からの与えられた不正回路の検出、化学構造式で示される化学物質中に特定の化学結合が存在するか否かの判定、シーン解析といったパターン認識等に応用が可能である。
【００６７】
［実施の形態２］
次に、実施の形態２について説明する。実施の形態２では、部分グラフ同型判定問題を処理する処理装置について説明する。図５は、実施の形態２に係る処理装置の概略構成を示す図である。図５に示す処理装置２０は、二つのグラフが与えられたとき、一方が他方の部分グラフとして含まれるか否かを判定する部分グラフ同型判定問題を解くための処理装置である。処理装置２０は、グラフ入力部１１、問題変換部２２及び判定部２３を有する。なお、処理装置２０は、例えば、ＲＯＭ、ＲＡＭ、ＣＰＵ等を含むコンピュータ等に所定のプログラムが読み込まれて、ＣＰＵが所定のプログラムを実行することで実現される。
【００６８】
問題変換部２２は、二つのグラフに基づいて、二つのグラフから構成される部分グラフ同型判定問題を解くためのＱＵＢＯの目的関数を作成する。または、問題変換部２２は、二つのグラフから構成される部分グラフ同型判定問題を解く場合に用いるイジングハミルトニアンを作成する。例えば、問題変換部２２は、二つのグラフに基づいて作成したＱＵＢＯの目的関数を変数変換し、イジングハミルトニアンを作成する。問題変換部２２は、入力されたグラフＧ１，Ｇ２とを、ＱＵＢＯ、または、イジングハミルトニアンに変換して出力する。
【００６９】
問題変換部２２は、図３に示す処理手順にしたがって、部分グラフ同型判定問題への変換を行なう。ここで、問題変換部２２は、問題変換部１２と異なり、ＱＵＢＯにおける目的関数を、（１７）式のように定義する。
【００７０】
【数１７】
2020149664.tif 000019
【００７１】
制約項Ｈ´Ａ，Ｈ´Ｂ，ＨＤの定義は、実施の形態１における誘導部分グラフ同型判定問題と同一である。
【００７２】
グラフ同型問題及び誘導部分グラフ同型判定問題では、制約項ＨＣによって、Ｇ１で接続していない頂点がＧ２で接続することを禁止していた。これに対し、部分グラフ同型問題においては、Ｇ１で接続していない頂点がＧ２で接続されていても同型と定義する。このため、処理装置２０は、制約項ＨＣを除外することによって、部分グラフ同型判定問題
を解くことができる。
【００７３】
判定部２３は、問題変換部２２から出力されたＱＵＢＯの目的関数Ｈ″またはイジングハミルトニアンを基に、二つのグラフの一方のグラフが他方の部分グラフとして含まれるか否かを判定する。
【００７４】
部分グラフ同型の制約を全て満たすようなｘｉｖの値の割り当てにおいて、また、その時に限り、Ｈ´Ａ＝ＨＤ＝０、Ｈ´Ｂ＝ｍ／４となる。したがって、Ｇ１とＧ２が部分グラフ同型であるならば、Ｈ″の下限値（基底状態）は、βｍ／４である。つまり、Ｈ″を目的関数とするＱＵＢＯを解くことによって、Ｈ″＝βｍ／４となるベクトルｘを得られた場合には、同型であり、そうでない場合には、同型でない、として部分グラフ同型判定問題を解くことができる。さらに、判定部２３は、（１）式にＱを代入した最小化問題を解く。その結果、ｘＴＱｘ＝βｍ／４となったならば、同型、そうでなければ同型でないと判定する。
【００７５】
図６は、図５に示す判定部２３による判定処理の処理手順を示すフローチャートである。図６に示すステップＳ３１は、図４に示すステップＳ２１と同じ処理である。
【００７６】
判定部２３が、変換後の問題種別がＱＵＢＯであると判定した場合について説明する（ステップＳ３１：Ｙｅｓ）。この場合、判定部２３は、問題変換部２２からＱＵＢＯの目的関数Ｈ″が入力されると、Ｈ″を目的関数とするＱＵＢＯを解く（ステップＳ３２）。図６に示すステップＳ３３は、図４に示すステップＳ２３と同じ処理である。
【００７７】
判定部２３は、ＱＵＢＯの目的関数が下限値を取る解が存在すると判定した場合には（ステップＳ３３：Ｙｅｓ）、Ｇ１がＧ２の部分グラフとして含まれると判定する（ステップＳ３４）。言い換えると、判定部２３は、二つのグラフの一方のグラフが他方の部分グラフとして含まれると判定する。
【００７８】
これに対し、判定部２３は、ＱＵＢＯの目的関数が下限値を取る解が存在しないと判定した場合には（ステップＳ３３：Ｎｏ）、Ｇ１がＧ２の部分グラフとして含まれないと判定する（ステップＳ３５）。言い換えると、判定部２３は、二つのグラフの一方のグラフが他方の部分グラフとして含まれないと判定する。
【００７９】
また、判定部２３が、変換後の問題種別がイジング問題であると判定した場合について説明する（ステップＳ３１：Ｎｏ）。図６に示すステップＳ３６，Ｓ３７は、図４に示すステップＳ２６，Ｓ２７である。
【００８０】
判定部２３は、イジングハミルトニアンが下限値を取る解が存在すると判定した場合には（ステップＳ３７：Ｙｅｓ）、Ｇ１がＧ２の部分グラフとして含まれると判定する（ステップＳ３８）。言い換えると、判定部３３は、二つのグラフの一方のグラフが他方の部分グラフとして含まれると判定する。これに対し、判定部２３は、イジングハミルトニアンが下限値を取る解が存在しないと判定した場合には（ステップＳ３７：Ｎｏ）、Ｇ１がＧ２の部分グラフとして含まれないと判定する（ステップＳ３９）。言い換えると、判定部２３は、二つのグラフの一方のグラフが他方の部分グラフとして含まれないと判定する。
【００８１】
［実施の形態２の効果］
このような処理を行うことによって、実施の形態２では、二つのグラフから構成される部分グラフ同型判定問題を解くためのＱＵＢＯの目的関数を作成する。また、このような処理を行うことによって、実施の形態２では、二つのグラフから構成される部分グラフ同型判定問題を解く場合に、ＱＵＢＯの目的関数を変数変換しイジングハミルトニアンを作成する。実施の形態２では、このＱＵＢＯの目的関数またはイジングハミルトニアンを解くことによって、二つのグラフが与えられたとき、一方が他方の部分グラフとして含まれるか否かを判定することができ、実施の形態１と同様の効果を奏する。
【００８２】
［実施例１］
次に、実施の形態１を適用した実施例１について説明する。実施例１では、処理装置１０が、実際に与えられたグラフＧ１，Ｇ２からＱＵＢＯを生成する流れについて説明する。図７及び図８は、処理対象のグラフの一例を示す図である。例えば、グラフＧ１として、図７に示すグラフを考える。また、グラフＧ２として、図８に示すグラフを考える。
【００８３】
このとき、Ｇ１，Ｇ２から得られる各制約は、ｘｉ，ｕ２＝ｘｉ，ｕであることに気をつけると、以下の（１８）式及び（１９）式となる。
【００８４】
【数１８】
2020149664.tif 000020
【００８５】
【数１９】
2020149664.tif 000021
【００８６】
ＨＣについては、Ｇ１がエッジを持たない頂点に対して、Ｇ２がエッジを持つ頂点となるような変換を考えるため、特に数式の展開は行わない。ＨＤについても同様とする。
【００８７】
ＱＵＢＯに変換するため、ｘｉ，ｖに関する二次多項式を（１）式の形で表現する係数行列Ｑを考える。ｉ∈［１，４］，ｖ∈［１，９］より、変数ｘｉ，ｖは、４×９＝３６個ある。したがって、Ｑは、３６×３６行列となる。紙面の都合上、（２０）式のようにブロック化を行う。
【００８８】
【数２０】
2020149664.tif 000022
【００８９】
各ブロックＱｉｊは、要素ｑｕｖｉｊ∈Ｒを用いて、（２１）式のように定義される。
【００９０】
【数２１】
2020149664.tif 000023
【００９１】
さらに、二値ベクトルｘ∈｛０，１｝３６を、（２２）式のように決める。
【００９２】
【数２２】
2020149664.tif 000024
【００９３】
このとき、ＱＵＢＯの目的関数は、（２３）式のように書ける。
【００９４】
【数２３】
2020149664.tif 000025
【００９５】
（２３）式に示すｘＴＱｘと、Ｈ´とが等価な式となるように、ｑｕｖｉｊの値を定める。まず、定義より、Ｑは、上三角行列としてもよいため、（２４）式と置くことができる。
【００９６】
【数２４】
2020149664.tif 000026
【００９７】
ＨＡ´より、（２５）式と置くことができる。
【００９８】
【数２５】
2020149664.tif 000027
【００９９】
ＨＢ´とＨＤより、（２６）式と置くことができる。
【０１００】
【数２６】
2020149664.tif 000028
【０１０１】
ＨＢ´とＨＣより、（２７）式と置くことができる。
【０１０２】
【数２７】
2020149664.tif 000029
【０１０３】
以上より、Ｈ´からＱを得ることができたため、Ｑを問題変換部１２の出力とする。
【０１０４】
さらに、判定部１３では、（１）式にＱを代入した最小化問題を解く。その結果、ｘＴＱｘ＝βｍ／４となったならば、同型、そうでなければ同型でないと判定する。
【０１０５】
［実施例２］
次に、実施の形態２を適用した実施例２について説明する。実施例２では、処理装置２０が、実際に与えられたグラフＧ１，Ｇ２からＱＵＢＯを生成する流れについて説明する。図９及び図１０は、処理対象のグラフの一例を示す図である。例えば、グラフＧ１として、図９に示すグラフを考える。また、グラフＧ２として、図１０に示すグラフを考える。
【０１０６】
実施例１と同様に定義した行列Ｑ∈Ｒ３６×３６と、ベクトルｘ∈｛０，１｝３６について、ｘＴＱｘ＝Ｈ″となるように、要素ｑｕｖｉｊの値を考える。
【０１０７】
まず、定義より、Ｑは、上三角行列としてもよいため、（２８）式と置くことができる。
【０１０８】
【数２８】
2020149664.tif 000030
【０１０９】
ＨＡ´より、（２９）式と置くことができる。
【０１１０】
【数２９】
2020149664.tif 000031
【０１１１】
ＨＢ´とＨＤより、（３０）式と置くことができる。
【０１１２】
【数３０】
2020149664.tif 000032
【０１１３】
ＨＢ´より、（３１）式と置くことができる。
【０１１４】
【数３１】
2020149664.tif 000033
【０１１５】
以上より、Ｈ″からＱを得ることができたため、Ｑを問題変換部２２の出力とする。さらに、判定部２３では、（１）式にＱを代入した最小化問題を解いて、判定処理を行う。
【０１１６】
［実施の形態３］
次に、実施の形態３について説明する。実施の形態１では、誘導部分グラフ同型判定問題を量子アニーリングマシンやイジングマシンを用いて解を得るための目的関数への変換を行ない、二つのグラフが厳密に同型であるか否かを判定した。ここで、実際には、同型ではないが類似するグラフを発見したい場合がある。例えば、一方のグラフと比較して他方のグラフに、エッジに過不足がある場合などを発見したい場合である。そこで、実施の形態３では、同形ではない二つのグラフの類似度を測定し、類似度に基づく判定処理を行う処理装置について説明する。本実施の形態３では、類似するグラフは、頂点数が同じであり、エッジの数が異なる二つのグラフと定義する。エッジ数の差が少ない程類似度は高いと表現する。
【０１１７】
図１１は、実施の形態３に係る処理装置の概略構成を示す図である。図１１に示す処理装置３０は、二つのグラフの類似性を測定する処理装置である。処理装置３０は、二つのグラフが与えられたとき、二つのグラフの類似度を計算する。処理装置３０は、二つのグラフの類似度を基に、一方のグラフと類似するグラフが、他方の誘導部分グラフとして含まれるか否かを判定する。処理装置３０は、図１に示す処理装置１０と比して、問題変換部１２及び判定部１３に代えて、問題変換部３２及び判定部３３を有する。なお、処理装置３０は、例えば、ＲＯＭ、ＲＡＭ、ＣＰＵ等を含むコンピュータ等に所定のプログラムが読み込まれて、ＣＰＵが所定のプログラムを実行することで実現される。
【０１１８】
問題変換部３２は、二つのグラフの類似度を計算するためのＱＵＢＯの目的関数を作成する。または、問題変換部３２は、二つのグラフの類似度を計算するために用いるイジングハミルトニアンを作成する。例えば、問題変換部３２は、二つのグラフに基づいて作成したＱＵＢＯの目的関数を変数変換し、イジングハミルトニアンを作成する。問題変換部３２は、入力されたグラフＧ１，Ｇ２とを、ＱＵＢＯ、または、イジングハミルトニアンに変換して出力する。
【０１１９】
問題変換部２２は、図３に示す処理手順にしたがって問題変換を行なう。ここで、問題変換部３２は、ＱＵＢＯにおける目的関数Ｈ´を実施の形態１と同じ（１４）式のように定義する。そして、問題変換部３２は、ＨＡ´，ＨＢ´，ＨＣ，ＨＤのハイパーパラメータα，β，γ，δ∈Ｒを以下の（３２）式のように設定する。
【０１２０】
【数３２】
2020149664.tif 000034
【０１２１】
（３２）式に示すように、問題変換部３２は、ハイパーパラメータα，βをγ，δのＫ倍に設定する。Ｋは、大きい正の実数であり、Ｐは、ペナルティ係数である。Ｐとして、通常は正の整数が設定される。このように、処理装置３０が使用する目的関数Ｈ´は、第１の関数の重みが、目的関数Ｈ´の第２の関数の重みよりも大きく設定される。なお、目的関数Ｈ´の第１の関数の重みは、目的関数Ｈ´の第２の関数の重みより優位に大きければよい。
【０１２２】
判定部３３は、問題変換部２２から出力されたＱＵＢＯの目的関数Ｈ´またはイジングハミルトニアンを基に、二つのグラフの類似度を計算する。判定部２３は、目的関数Ｈ´またはイジングハミルトニアンの値（解）を、二つのグラフに対する類似度の指標として用い、二つのグラフが類似するか否かを判定する。具体的には、判定部３３は、量子アニーリングやイジングマシンを用いてエネルギーを最小化することで解を得る。そして、判定部３３は、得られたエネルギーさの大きさで類似度を表現する。得られたエネルギーが小さいほど、類似度は高い。
【０１２３】
したがって、判定部３３は、目的関数の値に下限値を取る解がなかったとしても、求めた目的関数の値から類似性を判定する。判定部３３は、目的関数の解が小さいほど類似度が大きくなるような関数を使って、求めた解から類似度を算出する。判定部３３は、目的関数の解に対応する目的関数の値が小さいほど類似度が高くなるように、二つのグラフの類似度を計算する。さらに、判定部３３は、その結果から、二つのグラフがどの程度類似するかに対する判定を行ってもよい。
【０１２４】
例えば、判定部３３は、類似度として計算した目的関数の解（基底状態）が、βｍ／４＋Ｐｉ（ｉ∈｛０，１，２，３，・・・｝）である場合、二つのグラフは頂点制約項を満足し、一方のグラフは、他方のグラフに対しｉ本の余分なエッジまたは不足したエッジを持つグラフ、すなわち、他方のグラフに類似するグラフを誘導部分グラフとして含むと判定する。判定部３３は、目的関数の解（基底状態）が、βｍ／４＋Ｐｉ（ｉ∈｛０，１，２，３，・・・｝）である場合、二つのグラフは、類似すると判定する。
【０１２５】
これに対し、判定部３３は、目的関数の解（基底状態）が、βｍ／４＋Ｐｉでない場合には、二つのグラフは頂点制約項を満足しないため、類似しないと判定する。すなわち、判定部３３は、一方のグラフは、他方のグラフに類似するグラフを誘導部分グラフとして含まず、類似しないと判定する。なお、判定部３３は、類似判定まで行わず、類似度を出力するだけでもよい。
【０１２６】
図１２は、図１１に示す判定部３３による判定処理の処理手順を示すフローチャートである。図１２に示すステップＳ４１、ステップＳ４２、ステップＳ４６は、図４に示すステップＳ２１、ステップＳ２２、ステップＳ２６と同じ処理である。
【０１２７】
変換後の問題種別がＱＵＢＯである場合、判定部３３は、目的関数の解（基底状態）がβｍ／４＋Ｐｉの形で表現可能であるか否かを判定する（ステップＳ４３）。目的関数の解がβｍ／４＋Ｐｉの形で表現可能である場合（ステップＳ４３：Ｙｅｓ）、グラフＧ１に類似するグラフが、グラフＧ２の誘導部分グラフとして含まれると判定する（ステップＳ４４）。これに対し、判定部３３は、目的関数の解がβｍ／４＋Ｐｉの形で表現可能でない場合（ステップＳ４３：Ｎｏ）、判定部３３は、グラフＧ１とグラフＧ２とは類似しないと判定する（ステップＳ４５）。
【０１２８】
変換後の問題種別がイジング問題である場合、判定部３３は、目的関数の解（基底状態）がβｍ／４＋Ｐｉの形で表現可能であるか否かを判定する（ステップＳ４７）。目的関数の解がβｍ／４＋Ｐｉの形で表現可能である場合（ステップＳ４７：Ｙｅｓ）、グラフＧ１に類似するグラフが、グラフＧ２の誘導部分グラフとして含まれると判定する（ステップＳ４８）。これに対し、判定部３３は、目的関数の解がβｍ／４＋Ｐｉの形で表現可能でない場合（ステップＳ４７：Ｎｏ）、判定部３３は、グラフＧ１とグラフＧ２とは類似しないと判定する（ステップＳ４９）。
【０１２９】
［実施の形態３の効果］
ＨＡ´とＨＢ´とは、グラフＧ１とグラフＧ２との頂点数が一致していることを表現し、ＨＣとＨＤとは、グラフＧ１とグラフＧ２とは頂点接続関係が一致していることを表現する。すなわち、ＨＣはグラフグラフＧ１で接続していない頂点が、グラフＧ２で接続することを禁止する制約である。ＨＤはグラフＧ２で接続していない頂点が、グラフＧ１で接続することを禁止する制約である。
【０１３０】
実施の形態３では、制約項ＨＡ´および制約項ＨＢ´の重みを制約項ＨＣおよび制約項ＨＤの重みよりも優位に大きくすることで、頂点数の制約を強くし、頂点接続関係の制約を相対的に緩めることができる。そして、実施の形態３では、量子アニーリングマシンやイジングマシンを用いて得られた目的関数Ｈ´の値を、同形ではない問題の判断と同形ではない二つのグラフの類似度として用いる。これによって、実施の形態３では、二つのグラフは同形ではない問題と同形ではない二つのグラフの類似度を測定することが可能となる。
【０１３１】
［実施例３］
次に、実施の形態３を適用した実施例３について説明する。図１３及び図１４は、処理対象のグラフの一例を示す図である。図１５は、図１３に示すグラフに類似するグラフの一例を示す図である。例えば、グラフＧ１として、図１３に示すグラフを考える。また、グラフＧ２として、図１４に示すグラフを考える。
【０１３２】
実施例３では、Ｋ＝１０，Ｐ＝１２とし，α，β，γ，δは（３２）式に従うとして、Ｈ´＝αＨＡ´＋βＨＢ´＋γＨＣ＋δＨＤを目的関数とする。そして、処理装置３０は、量子アニーリングやイジングマシンを用いて、Ｈ´を最小化する。このとき得られる基底状態の値は、Ｈ´＝２８２である。この値はβｍ／４＋Ｐｉ（ただしｉ＝１）に等しい。
【０１３３】
この場合、ｉ＝１であるため、グラフＧ１とＧ２は同型でない。しかし、エッジが１本多い、または少ない類似部分が存在することが分かる。具体的な例としては、グラフＧ１の頂点１，４（グラフＧ２の頂点８，５）を接続する辺が１本少ない部分グラフ（図１５に示すグラフ）がグラフＧ２に含まれるので、確かに類似部分が存在する。
【０１３４】
［実施例４］
そして、実施の形態３を適用した実施例４について説明する。図１６及び図１７は、処理対象のグラフの一例を示す図である。図１８は、図１６に示すグラフに類似するグラフの一例を示す図である。例えば、グラフＧ１として、図１６に示すグラフを考える。また、グラフＧ２として、図１７に示すグラフを考える。
【０１３５】
実施例４では、Ｋ＝１０，Ｐ＝１２とし，α，β，γ，δは（３２）式に従うとして、Ｈ´＝αＨＡ´＋βＨＢ´＋γＨＣ＋δＨＤを目的関数とする。そして、処理装置３０は、量子アニーリングやイジングマシンを用いて、Ｈ´を最小化する。このとき得られる基底状態の値は、Ｈ´＝２８２である。この値はβｍ／４＋Ｐｉ（ただしｉ＝１）に等しい。
【０１３６】
この場合、ｉ＝１であるため、グラフＧ１とＧ２は同型でない。しかし、エッジが１本多い、または少ない類似部分が存在することが分かる。具体的な例としては、グラフＧ１の頂点２，４（グラフＧ２の頂点４，５）を接続する辺が１本多い部分グラフ（図１８に示すグラフ）がグラフＧ２に含まれるので、確かに類似部分が存在する。
【０１３７】
なお、処理装置３０は、二つのグラフが与えられたとき、一方のグラフと類似するグラフが、他方の部分グラフとして含まれるか否かを判定する場合には、ＱＵＢＯにおける目的関数として、（１７）式に示すＨ″を求める。この際、ＨＡ´，ＨＢ´，ＨＤのハイパーパラメータα，β，δのうち、α，βを、δのＫ倍に設定し、制約項ＨＡ´，ＨＢ´をＨＤのＫ倍に設定すればよい。そして、処理装置３０は、量子アニーリングマシンやイジングマシンを用いて得られた目的関数Ｈ″の値を、二つのグラフの類似度として用いる。
【０１３８】
［システム構成等］
図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部又は一部を、各種の負荷や使用状況等に応じて、任意の単位で機能的又は物理的に分散・統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部又は任意の一部が、ＣＰＵ及び当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０１３９】
また、本実施形態において説明した各処理のうち、自動的に行われるものとして説明した処理の全部又は一部を手動的に行なうこともでき、あるいは、手動的に行なわれるものとして説明した処理の全部又は一部を公知の方法で自動的に行なうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【０１４０】
［プログラム］
図１９は、プログラムが実行されることにより、処理装置１０，２０，３０が実現されるコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらの各部は、バス１０８０によって接続される。
【０１４１】
メモリ１０１０は、ＲＯＭ１０１１及びＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１１００に挿入される。シリアルポートインタフェース１０５０は、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、例えばディスプレイ１１３０に接続される。
【０１４２】
ハードディスクドライブ１０９０は、例えば、ＯＳ（Operating  System）１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、処理装置１０，２０，３０の各処理を規定するプログラムは、コンピュータにより実行可能なコードが記述されたプログラムモジュール１０９３として実装される。プログラムモジュール１０９３は、例えばハードディスクドライブ１０９０に記憶される。例えば、処理装置１０，２０，３０における機能構成と同様の処理を実行するためのプログラムモジュール１０９３が、ハードディスクドライブ１０９０に記憶される。なお、ハードディスクドライブ１０９０は、ＳＳＤ（Solid  State  Drive）により代替されてもよい。
【０１４３】
また、上述した実施形態の処理で用いられる設定データは、プログラムデータ１０９４として、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して実行する。
【０１４４】
なお、プログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限らず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、プログラムモジュール１０９３及びプログラムデータ１０９４は、ネットワーク（ＬＡＮ、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶されてもよい。そして、プログラムモジュール１０９３及びプログラムデータ１０９４は、他のコンピュータから、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【０１４５】
以上、本発明者によってなされた発明を適用した実施形態について説明したが、本実施形態による本発明の開示の一部をなす記述及び図面により本発明は限定されることはない。すなわち、本実施形態に基づいて当業者等によりなされる他の実施形態、実施例及び運用技術等は全て本発明の範疇に含まれる。
【符号の説明】
【０１４６】
１０，２０，３０  処理装置
１１  グラフ入力部
１２，２２，３２  問題変換部
１３，２３，３３  判定部
【図１】
2020149664.tif 000035
【図２】
2020149664.tif 000036
【図３】
2020149664.tif 000037
【図４】
2020149664.tif 000038
【図５】
2020149664.tif 000039
【図６】
2020149664.tif 000040
【図７】
2020149664.tif 000041
【図８】
2020149664.tif 000042
【図９】
2020149664.tif 000043
【図１０】
2020149664.tif 000044
【図１１】
2020149664.tif 000045
【図１２】
2020149664.tif 000046
【図１３】
2020149664.tif 000047
【図１４】
2020149664.tif 000048
【図１５】
2020149664.tif 000049
【図１６】
2020149664.tif 000050
【図１７】
2020149664.tif 000051
【図１８】
2020149664.tif 000052
【図１９】
2020149664.tif 000053