(57)【要約】  解探索装置が、和積標準形の論理式に含まれる変数毎に設けられて変数の値を算出する変数値演算回路と、変数値演算回路が算出した変数値を、他の変数値演算回路へ通知する通知経路と、を備え、変数値演算回路の各々は、他の変数値演算回路が算出した他の変数の値を論理式に入力したときに、論理式の節のうち否定の付いていない対象変数を含む全ての節が真となるための対象変数の値を算出する肯定側変数値演算回路と、他の変数値演算回路が算出した他の変数の値を論理式に入力したときに、論理式の節のうち否定の付いている対象変数を含む全ての節が真となるための対象変数の値を算出する否定側変数値演算回路と、肯定側変数値演算回路が算出した対象変数の値と、否定側変数値演算回路が算出した対象変数の値と、対象変数の前回値とに基づいて対象変数の値を算出する今回値算出回路と、を備える。
2019017412.tif 000002
【特許請求の範囲】
【請求項１】
和積標準形の論理式に含まれる変数毎に設けられて前記変数の値を算出する変数値演算回路と、
前記変数値演算回路が算出した変数値を、他の変数値演算回路へ通知する通知経路と、
を備え、
前記変数値演算回路の各々は、
その変数値演算回路が値を算出する変数である対象変数の値に関して、他の変数値演算回路が算出した他の変数の値を前記論理式に入力したときに、前記論理式の節のうち否定の付いていない前記対象変数を含む全ての節が真となるための前記対象変数の値を算出する肯定側変数値演算回路と、
他の変数値演算回路が算出した他の変数の値を前記論理式に入力したときに、前記論理式の節のうち否定の付いている前記対象変数を含む全ての節が真となるための前記対象変数の値を算出する否定側変数値演算回路と、
前記肯定側変数値演算回路が算出した前記対象変数の値と、前記否定側変数値演算回路が算出した前記対象変数の値と、前記対象変数の前回値とに基づいて前記対象変数の値を算出する今回値算出回路と、
を備える、
解探索装置。
【請求項２】
前記肯定側変数値演算回路は、
前記論理式の節のうち否定の付いていない前記対象変数を含む節に含まれるリテラルのうち、前記対象変数のリテラル以外のリテラルが全て偽の場合は真を出力し、前記対象変数のリテラル以外のリテラルのうちいずれか１つ以上が真である場合は偽を出力する肯定側節演算回路と、
前記論理式の節のうち否定の付いていない前記対象変数を含む全ての節に対応する前記肯定側節演算回路の出力の論理和を算出する論理和演算回路と、
を備える、請求項１に記載の解探索装置。
【請求項３】
前記肯定側節演算回路は、
他の変数値演算回路が算出した他の変数の値、前記他の変数の値の否定、及び、恒真のうち何れか１つを、前記節における前記他の変数のリテラルの態様に応じて選択する選択回路と、
前記節に含まれる全てのリテラルに対応する全ての前記選択回路の出力の否定論理和を算出する否定論理和演算回路と、
を備える請求項２に記載の解探索装置。
【請求項４】
前記否定側変数値演算回路は、
前記論理式の節のうち否定の付いている前記対象変数を含む節に含まれるリテラルのうち、前記対象変数のリテラル以外のリテラルが全て偽の場合は偽を出力し、前記対象変数のリテラル以外のリテラルのうちいずれか１つ以上が真である場合は真を出力する否定側節演算回路と、
前記論理式の節のうち否定の付いている前記対象変数を含む全ての節に対応する前記否定側節演算回路の出力の論理積を算出する論理積演算回路と、
を含む、請求項３に記載の解探索装置。
【請求項５】
前記否定側節演算回路は、
前記選択回路と、
前記節に含まれる全てのリテラルに対応する全ての前記選択回路の出力の論理和を算出する論理和演算回路と、
を備える請求項４に記載の解探索装置。
【請求項６】
前記肯定側変数値演算回路が算出した前記対象変数の値、及び、前記否定側変数値演算回路が算出した前記対象変数の値のうち少なくともいずれか一方の真偽を、設定された確率で反転させる誤り回路をさらに備える、請求項１から５の何れか一項に記載の解探索装置。
【請求項７】
前記肯定側変数値演算回路が算出した前記対象変数の値と、前記否定側変数値演算回路が算出した前記対象変数の値とが両立し得ないことを検出する矛盾検出回路と、
他の変数値演算回路における矛盾検出回路の検出結果を、前記今回値算出回路による前記対象変数の値の算出に反映させる矛盾検出反映回路と、
をさらに備える請求項１から６の何れか一項に記載の解探索装置。
【請求項８】
前記他の変数値演算回路における矛盾検出回路が、前記肯定側変数値演算回路が算出した前記対象変数の値と前記否定側変数値演算回路が算出した前記対象変数の値とが両立し得ないことを検出した場合に、検出結果を前記今回値算出回路による前記対象変数の値の算出に反映させることを、設定された確率で抑制する誤り回路をさらに備える、請求項７に記載の解探索装置。
【請求項９】
請求項１から８の何れか一項に記載の解探索装置を模擬するプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、解探索装置に関する。
本願は、２０１７年７月１９日に、日本国に出願された特願２０１７−１４０２７２号に基づき優先権を主張し、その内容をここに援用する。
【背景技術】
【０００２】
充足可能性問題など全解探索が困難な組み合わせ最適化問題を解くための装置が幾つか提案されている。
例えば、特許文献１には、量子ドットを用いた解探索システムが記載されている。この解探索システムでは、解くべき問題に応じて量子ドットを配置し、配置した量子ドットからの発光状態を用いて解を探索する。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】日本国特許第６０２９０４８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
特許文献１に記載の解探索システムは、解くべき問題に応じて、問題毎に量子ドットを配置する必要がある。これに対し、より汎用的に問題に対応できることが好ましい。【０００５】
本発明は、より汎用的に問題に対応することができる解探索装置およびプログラムを提供する。
【課題を解決するための手段】
【０００６】
本発明の態様の１つによれば、解探索装置は、和積標準形の論理式に含まれる変数毎に設けられて前記変数の値を算出する変数値演算回路と、前記変数値演算回路が算出した変数値を、他の変数値演算回路へ通知する通知経路と、を備え、前記変数値演算回路の各々は、その変数値演算回路が値を算出する変数である対象変数の値に関して、他の変数値演算回路が算出した他の変数の値を前記論理式に入力したときに、前記論理式の節のうち否定の付いていない前記対象変数を含む全ての節が真となるための前記対象変数の値を算出する肯定側変数値演算回路と、他の変数値演算回路が算出した他の変数の値を前記論理式に入力したときに、前記論理式の節のうち否定の付いている前記対象変数を含む全ての節が真となるための前記対象変数の値を算出する否定側変数値演算回路と、前記肯定側変数値演算回路が算出した前記対象変数の値と、前記否定側変数値演算回路が算出した前記対象変数の値と、前記対象変数の前回値とに基づいて前記対象変数の値を算出する今回値算出回路と、を備える。【０００７】
前記肯定側変数値演算回路は、前記論理式の節のうち否定の付いていない前記対象変数を含む節に含まれるリテラルのうち、前記対象変数のリテラル以外のリテラルが全て偽の場合は真を出力し、前記対象変数のリテラル以外のリテラルのうちいずれか１つ以上が真である場合は偽を出力する肯定側節演算回路と、前記論理式の節のうち否定の付いていない前記対象変数を含む全ての節に対応する前記肯定側節演算回路の出力の論理和を算出する論理和演算回路と、を備えるようにしてもよい。【０００８】
前記肯定側節演算回路は、他の変数値演算回路が算出した他の変数の値、前記他の変数の値の否定、及び、恒真のうち何れか１つを、前記節における前記他の変数のリテラルの態様に応じて選択する選択回路と、前記節に含まれる全てのリテラルに対応する全ての前記選択回路の出力の否定論理和を算出する否定論理和演算回路と、を備えるようにしてもよい。【０００９】
前記否定側変数値演算回路は、前記論理式の節のうち否定の付いている前記対象変数を含む節に含まれるリテラルのうち、前記対象変数のリテラル以外のリテラルが全て偽の場合は偽を出力し、前記対象変数のリテラル以外のリテラルのうちいずれか１つ以上が真である場合は真を出力する否定側節演算回路と、前記論理式の節のうち否定の付いている前記対象変数を含む全ての節に対応する前記否定側節演算回路の出力の論理積を算出する論理積演算回路と、を含むようにしてもよい。【００１０】
前記否定側節演算回路は、前記選択回路と、前記節に含まれる全てのリテラルに対応する全ての前記選択回路の出力の否定論理積を算出する否定論理積演算回路と、を備えるようにしてもよい。【００１１】
前記解探索装置は、前記肯定側変数値演算回路が算出した前記対象変数の値、及び、前記否定側変数値演算回路が算出した前記対象変数の値のうち少なくともいずれか一方の真偽を、設定された確率で反転させる誤り回路をさらに備えるようにしてもよい。【００１２】
前記解探索装置は、前記肯定側変数値演算回路が算出した前記対象変数の値と、前記否定側変数値演算回路が算出した前記対象変数の値とが両立し得ないことを検出する矛盾検出回路と、他の変数値演算回路における矛盾検出回路の検出結果を、前記今回値算出回路による前記対象変数の値の算出に反映させる矛盾検出反映回路と、をさらに備えるようにしてもよい。【００１３】
前記解探索装置は、前記他の変数値演算回路における矛盾検出回路が、前記肯定側変数値演算回路が算出した前記対象変数の値と前記否定側変数値演算回路が算出した前記対象変数の値とが両立し得ないことを検出した場合に、検出結果を前記今回値算出回路による前記対象変数の値の算出に反映させることを、設定された確率で抑制する誤り回路をさらに備えるようにしてもよい。【００１４】
プログラムは、上記した解探索装置の何れかを模擬するプログラムであってもよい。
【発明の効果】
【００１５】
上記した解探索装置およびプログラムによれば、より汎用的に問題に対応することができる。
【図面の簡単な説明】
【００１６】
【図１】実施形態に係る解探索装置の概略構成を示す図である。
【図２】実施形態に係る解探索装置の第一構成例を示す図である。
【図３】実施形態に係る解探索装置の第二構成例を示す図である。
【図４】実施形態に係る解探索装置の第三構成例を示す図である。
【図５】実施形態に係る変数値演算回路の構成例を示す図である。
【図６】実施形態に係る肯定側節演算回路におけるマルチプレクサの設定例を示す図である。
【図７】実施形態に係る肯定側節演算回路のもう１つの構成例を示す図である。
【図８】実施形態に係る否定側節演算回路におけるマルチプレクサの設定例を示す図である。
【図９】実施形態に係る否定側節演算回路のもう１つの構成例を示す図である。
【図１０】実施形態で、節に含まれるリテラルの数が３つに限定されない場合の、変数値演算回路の構成例を示す図である。
【図１１】実施形態に係る肯定側変数値演算回路の構成例を示す図である。
【図１２】実施形態に係る肯定側節演算回路の構成例を示す図である。
【図１３】実施形態に係る否定側変数値演算回路の構成例を示す図である。
【図１４】実施形態に係る否定側節演算回路の構成例を示す図である。
【図１５】実施形態に関して、マルチプレクサを含まない変数値演算回路の構成例を示す図である。
【図１６】実施形態に係る解探索装置を用いた解探索の第一例を示す図である。
【図１７】実施形態に係る解探索装置を用いた解探索の第二例を示す図である。
【図１８】実施形態に係る解探索装置を用いた解探索の第三例を示す図である。
【図１９】アメーバ型アルゴリズムを用いて充足可能性問題を解く場合の、解探索の繰り返し回数の例を示すグラフである。
【図２０】少なくとも１つの実施形態に係るコンピュータの構成を示す概略ブロック図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態を説明するが、以下の実施形態は請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
図１は、実施形態に係る解探索装置の概略構成を示す図である。図１に示すように、解探索装置１は、変数値演算回路１０と、通知経路２０とを備える。
【００１８】
解探索装置１は、充足可能性問題の解を探索する。充足可能性問題はＮＰ（Non-deterministic Polynomial）完全問題であり、いろいろなＮＰ完全問題を充足可能性問題に変形することができる。従って、充足可能性問題を解くことができれば、いろいろなＮＰ完全問題を解くことができる。
変数値演算回路１０は、充足可能性問題における変数の値を算出する。１つの変数値演算回路１０が充足可能性問題における１つの変数に割り当てられる。変数値演算回路１０は、割り当てられた変数の値を示す信号を出力する。
【００１９】
通知経路２０は、変数値演算回路１０が算出した変数値を他の変数値演算回路１０に通知する。具体的には、通知経路２０は、変数値演算回路１０が出力する信号を他の変数値演算回路１０へ伝達する。これにより、変数値演算回路１０の各々は、変数値演算回路１０自らに割り当てられた変数の値を、他の変数の値を参照して算出することができる。
通知経路２０は、変数値を伝達できるものであればよく、その形態は特定のものに限定されない。例えば、変数値演算回路１０の各々が装置として構成され、通知経路２０が通信ネットワークとして構成されていてもよい。あるいは、通知経路２０が、解探索装置１内部のバス（Ｂｕｓ）として構成されていてもよい。あるいは、通知経路２０が、２つの変数値演算回路１０間を結ぶ信号線の集合として構成されていてもよい。
【００２０】
図２は、解探索装置の第一構成例を示す図である。図２の例で、解探索装置１ａは、変数値演算回路１０と、通知経路２０ａとを備える。解探索装置１ａは、解探索装置１の例に該当する。通知経路２０ａは、通知経路２０の例に該当する。通知経路２０ａを構成する個々の経路を、個々の経路２１ａと表記する。
図２は、通知経路２０ａが全結合型に構成されている場合の例を示している。従って、通知経路２０ａを構成する個々の経路２１ａは２つの変数値演算回路１０を一対一に接続し、全ての変数値演算回路１０間に個々の経路２１ａが設けられている。
図２に示す構成により、変数値演算回路１０の各々は、他の全ての変数値演算回路１０が算出した変数値を参照することができる。
【００２１】
図３は、解探索装置の第二構成例を示す図である。図３の例で、解探索装置１ｂは、変数値演算回路１０と、通知経路２０ｂとを備える。解探索装置１ｂは、解探索装置１の例に該当する。通知経路２０ｂは、通知経路２０の例に該当する。通知経路２０ｂを構成する個々の経路を、個々の経路２１ｂと表記する。
図３は、通知経路２０ｂがリング型に構成されている場合の例を示している。
【００２２】
図３の例で、変数値演算回路１０が、変数値演算回路１０自らに接続されている２つの個々の経路２１ｂのうち一方からの信号を他方へ転送するようにしてもよい。これにより、変数値演算回路１０の各々は、他の全ての変数値演算回路１０が算出した変数値を参照することができる。あるいは、いずれの変数値演算回路１０も両隣の変数値演算回路１０が算出した変数値のみを参照すればよい充足可能性問題の場合は、変数値演算回路１０が２つの個々の経路２１ｂのうち一方からの信号を他方へ転送する必要は無い。
【００２３】
図４は、解探索装置の第三構成例を示す図である。図４の例で、解探索装置１ｃは、変数値演算回路１０と、通知経路２０ｃとを備える。解探索装置１ｃは、解探索装置１の例に該当する。通知経路２０ｃは、通知経路２０の例に該当する。通知経路２０ｃを構成する個々の経路を個々の経路２１ｃと表記する。
図４は、通知経路２０ｃが二次元メッシュ型に構成されている場合の例を示している。
【００２４】
図４の例で、変数値演算回路１０が、接続されている１つの個々の経路２１ｃからの信号を他の個々の経路２１ｃへ転送するようにしてもよい。これにより、変数値演算回路１０の各々は他の全ての変数値演算回路１０が算出した変数値を参照することができる。あるいは、いずれの変数値演算回路１０も隣接する変数値演算回路１０が算出した変数値のみを参照すればよい充足可能性問題の場合は、変数値演算回路１０が１つの個々の経路２１ｃからの信号を他の個々の経路２１ｃへ伝達する必要は無い。
【００２５】
図５は、変数値演算回路の構成例を示す図である。図５の例で、変数値演算回路１０ａは、肯定側変数値演算回路１０１ａと、否定側変数値演算回路１０２ａと、多数決回路１０３と、変数値ラッチ１０４と、矛盾検出回路１１１と、矛盾検出側ラッチ１１２と、矛盾検出総合回路１２１と、反映側ラッチ１２２と、矛盾検出反映回路１２３と、マルチプレクサ１２４と、肯定側誤り回路１３１−１と、否定側誤り回路１３１−２と、反映側誤り回路１３１−３とを備える。肯定側誤り回路１３１−１と、否定側誤り回路１３１−２と、反映側誤り回路１３１−３とを総称して誤り回路１３１と表記する。
【００２６】
誤り回路１３１は、誤りを発生させる。具体的には、誤り回路１３１は、予め設定された確率で入力される信号の否定をとって出力することで誤りを発生させる。誤りを発生させない場合、誤り回路１３１は、入力された信号をそのまま出力する。
誤り回路１３１が誤りを発生させることで、解探索装置１は、局所解に陥った場合に、局所解から抜け出して別の解を探索することができる。
【００２７】
肯定側変数値演算回路１０１ａは、肯定側節演算回路２１１ａと、肯定側積回路２１２と、肯定側ラッチ２１３とを備える。肯定側節演算回路２１１ａは、リテラル回路２２１と、肯定側和回路２２４ａとを備える。
リテラル回路２２１は、ＮＯＴ回路２２２と、マルチプレクサ２２３とを備える。
否定側変数値演算回路１０２ａは、否定側節演算回路２３１ａと、否定側積回路２３２と、否定側ラッチ２３３とを備える。否定側節演算回路２３１ａは、リテラル回路２２１と、否定側和回路２４４ａとを備える。
【００２８】
以下では、解探索装置が、和積標準形（連言標準形）の論理式の値を真にする変数値の有無を判定する充足可能性問題の解を探索する場合を例に説明する。和積標準形の論理式は、式（１）のように示される。
【００２９】
【数１】
2019017412.tif 000003
【００３０】
Ｎは変数の数を示す。Ｌｉは、変数ｘiのリテラルを示す。ここでは、リテラルを、変数、変数の否定、又は、恒偽の論理値と定義する。恒偽をリテラルに含めるのは、ある変数が節に含まれる場合と含まれない場合とを統一的に表記するためである。ある変数がある節に含まれない場合、その変数のリテラルを恒偽にすることで、そのリテラルの値が節の値に影響しないようにすることができる。
【００３１】
変数ｘiの否定を「¬ｘi」と表記する。また、論理値「偽」を「０」と表記し、論理値「真」を「１」と表記する。
Ｍは、節の数を示す。節はリテラルの論理和又は１つのリテラルで構成され、節の論理積は和積標準形の論理式を構成する。
論理和を「Σ」、「＋」又は「，」で表記する。論理積を「Π」、「・」又は、節を演算子無しに並べて書くことで表記する。
【００３２】
図５から図９では、説明対象の変数値演算回路に割り当てられている変数をｘｉで表し、他の変数値演算回路に割り当てられている変数をｘｊ、ｘｋ、ｘｌ、ｘｍ、・・・で表す。図５から図９の各々で説明対象の変数値演算回路とは、その図で示される変数値演算回路である。図１から図４を参照して説明したように、解探索装置は複数の変数値演算回路を含む。変数値演算回路は、和積標準形の論理式に含まれる変数毎に設けられてその変数の値を算出する。図５から図９の各々は、解探索装置が備える複数の変数値演算回路のうちの１つ、またはその一部を示す。説明対象の変数値演算回路に割り当てられている変数とは、その変数値演算回路が値を算出する変数である。説明対象の変数値演算回路に割り当てられている変数を、対象変数とも称する。
【００３３】
変数値演算回路は、他の変数値演算回路が算出する変数ｘｊ、ｘｋ、ｘｌ、ｘｍ、・・・の値を用いて、リテラルｘｉを含む全ての節の値、及び、リテラル¬ｘｉを含む全ての節の値が真となるための、変数ｘｉの値を算出する。リテラルｘｉを含む全ての節の値、及び、リテラル¬ｘｉを含む全ての節の値が真となることは、和積標準形の論理式の値が真になるための必要条件である。和積標準形の論理式に含まれる全ての節の値が真となることは、和積標準形の論理式の値が真になるための必要十分条件である。
また、時刻（クロックタイミング）を示す場合、時刻を括弧で囲み変数の後ろに付して示す。例えば、時刻ｔにおける変数ｘｉの値をｘｉ（ｔ）と表記する。
【００３４】
変数値演算回路１０ａは、変数値演算回路１０の例に該当する。変数値演算回路１０ａは、節に含まれるリテラルの数が３つである場合に対応する。
以下、図５から図９を参照して変数値演算回路１０ａの各部について説明する際、変数値演算回路１０との関係で説明する場合がある。変数値演算回路１０は、変数値演算回路１０ａを例として含む、より一般的な変数値演算回路である。
リテラル回路２２１の各々は、変数値の入力を受け、マルチプレクサ２２３が信号を選択することで、リテラルの値を出力する。リテラル回路２２１が示すリテラルが、否定を付されていない変数である場合、マルチプレクサ２２３を、ＮＯＴ回路２２２を通らない変数値を選択するように設定する。リテラル回路２２１が示すリテラルが、否定を付された変数である場合、マルチプレクサ２２３を、ＮＯＴ回路２２２が変数値を真偽反転させた値を選択するように設定する。
【００３５】
マルチプレクサ２２３は、マルチプレクサ２２３自らに入力される３つ信号のうちいずれか１つを選択する。リテラル回路２２１に入力される変数値をｘｋ（ｔ）とすると、マルチプレクサ２２３に入力される信号値はｘｋ（ｔ）、¬ｘｋ（ｔ）及び１である。マルチプレクサ２２３は、マルチプレクサ２２３自らに対応付けられるリテラルに応じて、これら３つの信号のうち何れか１つを選択する。１つの充足可能性問題に対するマルチプレクサ２２３の設定は固定である。すなわち、１つの充足可能性問題に対するマルチプレクサ２２３の信号値の選択は固定である。
マルチプレクサ２２３は、選択回路の例に該当する。
【００３６】
リテラル回路２２１は、肯定側節演算回路２１１ａ又は否定側節演算回路２３１ａの数が余る場合に対応する。肯定側節演算回路２１１ａに含まれる２つのリテラル回路２２１とも、マルチプレクサ２２３が恒真を選択するように設定すると、その肯定側節演算回路２１１ａは恒偽を出力するようになる。これにより、その肯定側節演算回路２１１ａを不使用として、その肯定側節演算回路２１１ａの出力が、肯定側積回路２１２の演算に影響を与えないようにすることができる。
【００３７】
否定側節演算回路２３１ａに含まれる２つのリテラル回路２２１とも、マルチプレクサ２２３が恒真を選択するように設定すると、その否定側節演算回路２３１ａは恒真を出力するようになる。これにより、その否定側節演算回路２３１ａを不使用として、その否定側節演算回路２３１ａの出力が、否定側積回路２３２の演算に影響を与えないようにすることができる。
【００３８】
肯定側和回路２２４ａは、節におけるリテラルの論理和の演算を行う。具体的には、肯定側和回路２２４ａはＮＯＲ回路を用いて構成され、リテラル回路２２１の各々が出力する値のＮＯＲを算出する。ＮＯＲを否定論理和と称し、ＮＯＲ回路を否定論理和演算回路と称する。
肯定側和回路２２４ａは、変数ｘｉの値が真でも偽でも節の値が真となる場合は、変数ｘｉの値を偽と算出する。一方、肯定側和回路２２４ａは、節の値が真となるためには変数ｘｉの値が真である必要がある場合は、変数ｘｉの値を真と算出する。
【００３９】
肯定側和回路２２４ａが算出する値は、肯定側節演算回路２１１ａが算出する値として用いられる。１つの肯定側節演算回路２１１ａは、リテラルｘｉを含む１つの節に対応して、その節の値が真となるための変数ｘｉの値を算出する。
具体的には、肯定側節演算回路２１１ａは、リテラルｘｉを含む１つの節に含まれるリテラルのうち、変数ｘｉのリテラル以外のリテラルが全て偽の場合は真を出力する。肯定側節演算回路２１１ａは、リテラルｘｉを含む１つの節に含まれるリテラルのうち、変数ｘｉのリテラル以外のリテラルのうちいずれか１つ以上が真である場合は偽を出力する。
【００４０】
肯定側積回路２１２は、否定を付されていないｘｉを含む各節を結合する論理積の演算を行う。具体的には、肯定側積回路２１２は、肯定側節演算回路２１１ａの出力のＯＲをとる。いずれの肯定側節演算回路２１１ａも偽を出力している場合、肯定側積回路２１２は、偽を出力する。すなわち、いずれの節でも、変数ｘｉの値が真でも偽でも節の値が真となる場合、肯定側積回路２１２は、偽を出力する。
一方、１つ以上の肯定側節演算回路２１１ａが真を出力している場合、肯定側積回路２１２は、真を出力する。すなわち、いずれか１つ以上の節において、その節の値が真となるために変数ｘｉの値が真である必要がある場合、肯定側積回路２１２は、真を出力する。
【００４１】
肯定側ラッチ２１３は、肯定側積回路２１２の出力値を一時的に保持する。
肯定側誤り回路１３１−１は、肯定側ラッチ２１３の出力を、定められた確率で真偽反転させる。肯定側誤り回路１３１−１の動作をいろいろに設定することができる。例えば、肯定側誤り回路１３１−１が、肯定側ラッチ２１３の出力が真の場合のみ、ある確率で真偽反転させるようにしてもよい。あるいは、肯定側誤り回路１３１−１が、肯定側ラッチ２１３の出力が偽の場合のみ、ある確率で真偽反転させるようにしてもよい。肯定側誤り回路１３１−１が、肯定側ラッチ２１３の出力が真、偽いずれの場合も、ある確率で真偽反転させるようにしてもよい。
肯定側誤り回路１３１−１が真偽反転を行う確率は、例えば５％など、比較的小さい値に設定されていてもよい。
【００４２】
肯定側積回路２１２の出力を肯定側ラッチ２１３が遅延させた信号が、肯定側変数値演算回路１０１ａの出力となる。肯定側変数値演算回路１０１ａは、和積標準形の論理式の節のうち否定の付いていない変数ｘｉを含む全ての節が真となるための変数ｘｉの値を算出する。
【００４３】
否定側和回路２４４ａは、節におけるリテラルのＯＲ（論理和）の演算を行う。具体的には、否定側和回路２４４ａはＯＲ回路（論理和演算回路）を用いて構成され、リテラル回路２２１の各々が出力する値のＯＲを算出する。
否定側和回路２４４ａは、変数ｘｉの値が真でも偽でも節の値が真となる場合は、変数ｘｉの値を真と算出する。一方、否定側和回路２４４ａは、節の値が真となるためには変数ｘｉの値が偽である必要がある場合は、変数ｘｉの値を偽と算出する。すなわち、否定側和回路２４４ａは、節の値が真となるためにはリテラル¬ｘｉの値が真である必要がある場合は、変数ｘｉの値を偽と算出する。
【００４４】
否定側和回路２４４ａが算出する値は、否定側節演算回路２３１ａが算出する値として用いられる。１つの否定側節演算回路２３１ａは、リテラル¬ｘｉを含む１つの節に対応して、その節の値が真となるための変数ｘｉの値を算出する。
具体的には、否定側節演算回路２３１ａは、リテラルｘｉを含む１つの節に含まれるリテラルのうち、リテラル¬ｘｉ以外のリテラルが全て偽の場合は偽を出力する。肯定側節演算回路２１１ａは、リテラル¬ｘｉを含む１つの節に含まれるリテラルのうち、リテラル¬ｘｉ以外のリテラルのうちいずれか１つ以上が真である場合は真を出力する。
【００４５】
否定側積回路２３２は、¬ｘｉを含む各節を結合する論理積の演算を行う。具体的には、否定側積回路２３２は、否定側節演算回路２３１ａの出力のＡＮＤ（論理積）をとる。否定側積回路２３２は、ＡＮＤ回路（論理積演算回路）を用いて構成される。
いずれの否定側節演算回路２３１ａも真を出力している場合、否定側積回路２３２は、真を出力する。すなわち、いずれの節でも、変数ｘｉの値が真でも偽でも節の値が真となる場合、否定側積回路２３２は、真を出力する。
一方、１つ以上の否定側節演算回路２３１ａが偽を出力している場合、否定側積回路２３２は、偽を出力する。すなわち、いずれか１つ以上の節において、その節の値が真となるために変数ｘｉの値が偽（リテラル¬ｘｉの値が真）である必要がある場合、否定側積回路２３２は、偽を出力する。
【００４６】
否定側ラッチ２３３は、否定側積回路２３２の出力値を一時的に保持する。
否定側誤り回路１３１−２は、否定側ラッチ２３３の出力を、定められた確率で真偽反転させる。否定側誤り回路１３１−２の動作をいろいろに設定することができる。例えば、否定側誤り回路１３１−２が、否定側ラッチ２３３の出力が真の場合のみ、ある確率で真偽反転させるようにしてもよい。あるいは、否定側誤り回路１３１−２が、否定側ラッチ２３３の出力が偽の場合のみ、ある確率で真偽反転させるようにしてもよい。否定側誤り回路１３１−２が、否定側ラッチ２３３の出力が真、偽いずれの場合も、ある確率で真偽反転させるようにしてもよい。
否定側誤り回路１３１−２が真偽反転を行う確率は、例えば５％など、比較的小さい値に設定されていてもよい。
【００４７】
否定側積回路２３２の出力を否定側ラッチ２３３が遅延させた信号が、否定側変数値演算回路１０２ａの出力となる。否定側変数値演算回路１０２ａは、和積標準形の論理式の節のうち否定の付いている変数ｘｉ（¬ｘｉ）を含む全ての節が真となるための変数ｘｉの値を算出する。
【００４８】
多数決回路１０３は、多数決回路１０３の出力（変数値ｘｉ（ｔ））と、肯定側変数値演算回路１０１ａの出力と、否定側変数値演算回路１０２ａの出力とに基づいて、変数値ｘｉ（ｔ＋１）を算出する。多数決回路１０３は、今回値算出回路の例に該当する。変数値ｘｉ（ｔ）は、対象変数の前回値の例に該当する。
変数値ラッチ１０４は、多数決回路１０３の出力を１クロック周期の間保持する。変数値演算回路は、時刻ｔにおける他の変数値の入力に対して、次のクロック周期である時刻ｔ＋１における変数ｘiの値を出力する。この変数値をｘi（ｔ＋１）と表記する。「ｘi（ｔ＋１）」の「ｔ＋１」は、タイミングｔの次のクロック周期のタイミングであるタイミングｔ＋１を示す。従って、変数ｘiの値は、タイミングｔにおいては変数値ｘｉ（ｔ）であり、その次のタイミングｔ＋１においては変数値ｘｉ（ｔ＋１）である。
【００４９】
多数決回路１０３について、説明を簡単にするために、肯定側誤り回路１３１−１、否定側誤り回路１３１−２の何れも真偽反転を行っておらず、かつ、変数値ラッチ１０４の出力がそのまま多数決回路１０３へ入力される場合について考える。
この場合、多数決回路１０３は、肯定側変数値演算回路１０１ａの出力と、否定側変数値演算回路１０２ａの出力とに基づいて、変数ｘｉの値（ｘｉ（ｔ＋１））を前回値（ｘｉ（ｔ））から変更するか否かを決定する。
【００５０】
肯定側変数値演算回路１０１ａの出力、否定側変数値演算回路１０２ａの出力の何れも偽である場合、リテラルｘｉを含む節の値及びリテラル¬ｘｉを含む節の値が全て真になるためには、変数ｘｉの値が偽である必要がある。この場合、多数決回路１０３は、変数ｘｉの値を偽にする。
一方、肯定側変数値演算回路１０１ａの出力、否定側変数値演算回路１０２ａの出力の何れも真である場合、リテラルｘｉを含む節及びリテラル¬ｘｉを含む節の値が全て真になるためには、変数ｘｉの値が真である必要がある。この場合、多数決回路１０３は、変数ｘｉの値を真にする。
それ以外の場合、多数決回路１０３は、変数ｘｉの前回値を保持する。
【００５１】
図５における誤り回路１３１の個数及び位置は一例である。変数値演算回路１０ａが備える誤り回路１３１の個数及び位置は、この例に限らずいろいろな個数及び位置とすることができる。
例えば、変数値演算回路１０ａが肯定側誤り回路１３１−１及び否定側誤り回路１３１−２を備えていない構成など、変数値演算回路１０ａが、図５に示す誤り回路１３１のうち一部又は全部を備えていない構成としても、解探索を行える場合がある。
また、変数値ラッチ１０４の後ろに誤り回路１３１を設けた構成としてもよい。この場合、図５に示す３つの誤り回路１３１を全て残しておいてもよいし、これらのうち一部又は全部を取り除いた構成としてもよい。
【００５２】
図５では、変数値ラッチ１０４、矛盾検出側ラッチ１１２、反映側ラッチ１２２、肯定側ラッチ２１３、及び、否定側ラッチ２３３の５つのラッチが示されている。これらのラッチの個数及び位置は一例であり、変数値演算回路１０ａが備えるラッチの個数及び位置は、この例に限らずいろいろな個数及び位置とすることができる。
例えば、各論理ゲート及びマルチプレクサにおける遅延の大きさによっては、変数値演算回路１０ａが、図５に示す５つのラッチのうち一部又は全部を備えていない構成としても、適切なタイミングで変数値を算出できる場合がある。
また、変数値演算回路１０ａが備えるラッチの構成方法は、特定の構成方法に限定されず、入力された値を保持可能ないろいろな回路を用いて構成することができる。例えば、変数値演算回路１０ａが備えるラッチの一部または全部が、フリップフロップを用いて構成されていてもよい。
【００５３】
図６は、肯定側節演算回路２１１ａにおけるマルチプレクサ２２３の設定例を示す図である。
例えば、節（ｘｉ＋ｘｊ＋ｘｋ）及び節（ｘｉ＋ｘｌ＋¬ｘｍ）が論理式に含まれる場合、マルチプレクサ２２３による信号選択を図６のように設定して信号の経路を形成する。
この場合、２つの肯定側節演算回路２１１ａは、それぞれ¬（ｘｊ＋ｘｋ）、¬（ｘｌ＋¬ｘｍ）を算出する。
【００５４】
節（ｘｉ＋ｘｊ＋ｘｋ）の値が真になる必要十分条件は、ｘｉ、ｘｊ及びｘｋのうち１つ以上の値が真になることである。従って、ｘｊ及びｘｋのうち１つ以上の値が真である場合は、ｘｉの値は真でも偽でもよい。一方、ｘｊ及びｘｋの値がいずれも偽である場合、ｘｉの値が真である必要がある。このように、否定を付されていない変数ｘｉを含む節では、変数ｘｉの値は、真でも偽でもよいか、あるいは、真である必要があるかのいずれかである。
上記のように、肯定側節演算回路では、変数ｘｉの値が真でも偽でもよい場合は、変数ｘｉの値を偽にし、変数ｘｉの値が真である必要がある場合は、変数ｘｉの値を真にする。この変数ｘｉの値は、肯定側節演算回路２１１ａが演算する¬（ｘｊ＋ｘｋ）にて算出される。
【００５５】
また、節（ｘｉ＋ｘｌ＋¬ｘｍ）の値が真になる必要十分条件は、ｘｉ、ｘｌ及び¬ｘｍのうち１つ以上の値が真になることである。従って、ｘｌ及び¬ｘｍのうち１つ以上の値が真である場合は、ｘｉの値は真でも偽でもよい。一方、ｘｌ及び¬ｘｍの値がいずれも偽である場合、ｘｉの値が真である必要がある。
上記のように、肯定側節演算回路では、変数ｘｉの値が真でも偽でもよい場合は、変数ｘｉの値を偽にし、変数ｘｉの値が真である必要がある場合は、変数ｘｉの値を真にする。この変数ｘｉの値は、肯定側節演算回路２１１ａが演算する¬（ｘｌ＋¬ｘｍ）にて算出される。
【００５６】
図７は、肯定側節演算回路のもう１つの構成例を示す図である。図７に示す肯定側節演算回路２１１ｂは、４つの論理ゲート３１１から３１４とマルチプレクサ３１５とを備える。
節において変数ｘｊ、ｘｋそれぞれに否定が付されているか否かに応じてマルチプレクサ３１５が４つの論理ゲート３１１から３１４のうち何れかの出力を選択するように設定することで、肯定側節演算回路２１１ｂは、肯定側節演算回路２１１ａと等価な回路になる。ここでいう等価な回路は、同じ入力値に対して同じ値を出力する回路である。
この肯定側節演算回路２１１ｂを不使用とする場合は、マルチプレクサ３１５が恒偽を選択するように設定する。
【００５７】
図８は、否定側節演算回路２３１ａにおけるマルチプレクサ２２３の設定例を示す図である。
例えば、節（¬ｘｉ＋¬ｘｊ＋ｘｋ）が論理式に含まれる場合、マルチプレクサ２２３による信号選択を図８のように設定して信号の経路を形成する。変数ｘｌ及びｘｍの値の入力を受ける否定側節演算回路２３１ａ（図８で下側の否定側節演算回路２３１ａ）は、不使用に設定されている。
この場合、変数ｘｊ及びｘｋの値の入力を受ける否定側節演算回路２３１ａ（図８で上側の否定側節演算回路２３１ａ）は、¬ｘｊ＋ｘｋを算出する。
【００５８】
節（¬ｘｉ＋¬ｘｊ＋ｘｋ）の値が真になる必要十分条件は、¬ｘｉ、¬ｘｊ及びｘｋのうち１つ以上の値が真になることである。従って、¬ｘｊ及びｘｋのうち１つ以上の値が真である場合は、ｘｉの値は真でも偽でもよい。一方、¬ｘｊ及びｘｋの値がいずれも偽である場合、¬ｘｉの値が真である必要がある。従って、ｘｉの値が偽である必要がある。
【００５９】
このように、否定を付されている変数ｘｉを含む節では、変数ｘｉの値は、真でも偽でもよいか、あるいは、偽である必要があるかのいずれかである。
上記のように、否定側節演算回路では、変数ｘｉの値が真でも偽でもよい場合は、変数ｘｉの値を真にし、変数ｘｉの値が偽である必要がある場合は、変数ｘｉの値を偽にする。この変数ｘｉの値は、否定側節演算回路２３１ａが演算する¬ｘｊ＋ｘｋにて算出される。
【００６０】
図９は、否定側節演算回路のもう１つの構成例を示す図である。図７に示す否定側節演算回路２３１ｂは、４つの論理ゲート３２１から３２４とマルチプレクサ３２５とを備える。
節において変数ｘｊ、ｘｋそれぞれに否定が付されているか否かに応じてマルチプレクサ３２５が４つの論理ゲート３２１から３２４のうち何れかの出力を選択するように設定することで、否定側節演算回路２３１ｂは、否定側節演算回路２３１ａと等価な回路になる。
この否定側節演算回路２３１ｂを不使用とする場合は、マルチプレクサ３２５が恒真を選択するように設定する。
【００６１】
図５の矛盾検出回路１１１は、肯定側変数値演算回路１０１ａの出力と否定側変数値演算回路１０２ａの出力とが矛盾している状態を検出する。すなわち、矛盾検出回路１１１は、肯定側変数値演算回路１０１ａが算出した変数ｘｉの値と、否定側変数値演算回路１０２ａが算出した変数ｘｉの値とが、両立し得ないことを検出する。
具体的には、肯定側変数値演算回路１０１ａの出力が、変数値が真であることが必要であることを示し、否定側変数値演算回路１０２ａの出力が、変数値が偽であることが必要であることを示している場合、両者を共に成立させることはできない。矛盾検出回路１１１は、この状態を検出する。
【００６２】
矛盾検出回路１１１の検出結果は、他の変数値演算回路１０の出力値を変化させるために用いられる。そのために、通知経路２１は、変数値演算回路１０が算出した変数値に加えて、矛盾検出回路１１１の検出結果を他の変数値演算回路１０へ通知する。矛盾検出回路１１１の検出結果を矛盾検出結果とも称する。他の変数値演算回路１０は、変数値演算回路１０ａであってもよいし、後述する変数値演算回路１０ｂまたは１０ｃであってもよい。
矛盾検出側ラッチ１１２は、矛盾検出回路１１１の出力を、１クロック周期の間保持する。
変数ｘiに対応付けられた変数値演算回路１０の矛盾検出回路１１１の時刻ｔにおける出力値をｃｏｎｔｒａｉ（ｔ）と表記する。
【００６３】
図５の例では、「ｃｏｎｔｒａｉ（ｔ）」および「ｘｉ（ｔ＋１）」のように、ｃｏｎｔｒａｉの、他の変数値演算回路への出力タイミングは、ｘｉの出力タイミングよりも１クロック前となっている。但し、ｃｏｎｔｒａｉの出力タイミングは、これに限定されない。例えば、ｃｏｎｔｒａｉがｘｉに対して数クロック遅れて出力されても、解探索装置１が充足可能性問題を解くことができることが、実験で確認された。従って、図５の「ｃｏｎｔｒａｉ（ｔ）」に代えて、「ｃｏｎｔｒａｉ（ｔ＋１）」または「ｃｏｎｔｒａｉ（ｔ＋２）」となっていてもよい。
また、ｃｏｎｔｒａｉが時刻ｔよりも遅れて出力された方が、このｃｏｎｔｒａｉの出力先の変数値演算回路が、ｃｏｎｔｒａｉと他の信号との同期を取り易くなる場合があることが、実験で確認された。
他の図の例における「ｃｏｎｔｒａｉ（ｔ）」の出力タイミングについても、図５の場合と同様である。
【００６４】
マルチプレクサ１２４は、他の変数値演算回路１０から通知された矛盾検出結果のうち、マルチプレクサ１２４自らを備える変数値演算回路１０（図５の例では変数値演算回路１０ａ）に割り当てられている変数と節を共有する変数の矛盾検出結果を通過させる。一方、マルチプレクサ１２４は、マルチプレクサ１２４自らを備える変数値演算回路１０に割り当てられている変数と節を共有していない変数の矛盾検出結果を恒偽に置き換える。
【００６５】
上述したように、変数値演算回路１０に割り当てられている変数とは、その変数値演算回路１０が変数値を算出する変数である。
複数の変数が節を共有するとは、これら複数の変数が同じ節に含まれていることである。各変数は、否定（¬）を付されていない形で節に含まれていてもよいし、否定を付された形で節に含まれていてもよい。本実施形態では、和積標準形の論理式の充足可能性問題を扱っている。この場合、複数の変数が節を共有するとは、この充足可能性問題の論理式の節のうち、これら複数の変数を含む節が少なくとも１つ存在することである。
マルチプレクサ１２４を上記のように動作させるために、充足可能性問題の論理式に応じて、マルチプレクサ１２４による信号の選択を、マルチプレクサ１２４毎に予め設定しておくことができる。
【００６６】
図５の場合、この図の変数値演算回路１０ａは、変数ｘｉの値を算出する。従って、図５に示すマルチプレクサ１２４の各々は、マルチプレクサ１２４自らに入力される矛盾検出結果の対象となっている変数が、変数ｘｉと節を共有している場合は、矛盾検出結果をそのまま通過させる。一方、これらのマルチプレクサ１２４の各々は、マルチプレクサ１２４自らに入力される矛盾検出結果の対象となっている変数が、変数ｘｉと節を共有していない場合は、矛盾検出結果に代えて恒偽を出力する。
【００６７】
例えば、ｃｏｎｔｒａｊ（ｔ）を入力されるマルチプレクサ１２４は、変数ｘｉと変数ｘｊとが節を共有している場合は、ｃｏｎｔｒａｊ（ｔ）の値を出力するように予め設定されている。一方、変数ｘｉと変数ｘｊとが節を共有していない場合、ｃｏｎｔｒａｊ（ｔ）を入力されるマルチプレクサ１２４は、恒偽（論理０）を出力するように予め設定されている。
【００６８】
矛盾検出結果は、ある変数値の算出結果が矛盾している場合に、他の変数値を変化させることで矛盾状態の解消を図るために用いられる。具体的には、矛盾検出結果は、ある変数の値が真かつ偽でなければならないと算出された場合に、他の変数値の真偽を反転させることで、真かつ偽との矛盾状態の解消を図るために用いられる。
これに対し、変数値が矛盾している変数と節を共有していない変数の値を変化させても、矛盾状態は解消されない。しかも、変数値を算出された値から変化させると、解から遠ざかってしまう可能性が高いと考えられる。
【００６９】
そこで、上記のようにマルチプレクサ１２４が、マルチプレクサ１２４自らを備える変数値演算回路１０に割り当てられている変数と節を共有していない変数の矛盾検出結果を恒偽に置き換える。これにより、変数値演算回路１０は、変数値演算回路１０自らが変数値を算出する変数と節を共有していない変数の矛盾検出結果を無視する。これにより、変数値演算回路１０は、矛盾状態の解消に貢献しない変数値の変更、及び、この変更によって解から遠ざかってしまうことを回避することができる。
【００７０】
矛盾検出総合回路１２１は、他の変数値演算回路１０から通知された矛盾検出結果を総合する。具体的には、矛盾検出総合回路１２１は、他の変数値演算回路１０から通知された矛盾検出結果の信号のＯＲをとる。いずれかの変数値演算回路１０が矛盾を検出した場合、矛盾検出総合回路１２１は１を出力する。いずれの変数値演算回路１０も矛盾を検出していない場合、矛盾検出総合回路１２１は０を出力する。
反映側ラッチ１２２は、矛盾検出総合回路１２１の出力を１クロック周期の間保持する。
【００７１】
反映側誤り回路１３１−３は、定められた確率で矛盾検出結果の真偽を反転させる。例えば、反映側ラッチ１２２の出力が偽の場合、反映側誤り回路１３１−３が偽をそのまま出力するようにしてもよい。また、反映側ラッチ１２２の出力が真の場合、反映側誤り回路１３１−３が例えば９０％の確率で反映側ラッチ１２２の出力を反転させるようにしてもよい。
このように、他の変数値演算回路における矛盾検出回路１１１が、肯定側変数値演算回路１０１ａが算出した対象変数の値と、否定側変数値演算回路１０２ａが算出した対象変数の値とが両立し得ないことを検出した場合に、検出結果を多数決回路１０３による変数ｘｉの値の算出に反映させることを、誤り回路１３１−３が、設定された確率で抑制するようにしてもよい。
【００７２】
矛盾検出反映回路１２３は、矛盾検出結果と変数値ラッチ１０４からの出力との排他的論理和をとる。これにより、矛盾検出反映回路１２３は、矛盾検出結果が矛盾有りを示す１である場合に、変数値ラッチ１０４からの出力の否定をとって出力する。これにより、多数決回路１０３が、前回値と異なる値を出力し易くなる。このように、矛盾検出反映回路１２３は、他の変数値演算回路１０における矛盾検出回路１１１の検出結果を、多数決回路１０３による変数ｘｉの値の算出に反映させる。
矛盾検出反映回路１２３を用いることで、いずれかの変数値演算回路１０で矛盾が検出された場合に変数値の更新を促進させ、矛盾の生じている状態を速やかに解消できることが期待される。
【００７３】
次に図１０から図１４を参照して、節に含まれるリテラルの数が３つに限定されない場合の、変数値演算回路の構成例について説明する。
図１０は、節に含まれるリテラルの数が３つに限定されない場合の変数値演算回路の構成例を示す図である。図１０に示す変数値演算回路１０ｂは、肯定側変数値演算回路１０１と、否定側変数値演算回路１０２と、多数決回路１０３と、変数値ラッチ１０４と、誤り回路１３１と、矛盾検出回路１１１と、矛盾検出側ラッチ１１２と、矛盾検出総合回路１２１と、反映側ラッチ１２２と、矛盾検出反映回路１２３と、マルチプレクサ１２４とを備える。
【００７４】
図１０の各部のうち、図５の各部に対応して同様の機能を有する部分には同一の符号（１０３、１０４、１１１、１１２、１２１、１２２、１２３、１２４、１３１−１、１３１−２、１３１−３）を付して、ここでは説明を省略する。
図１０から図１４では、変数値演算回路１０ｂが値を算出する変数をｘi（１≦ｉ≦Ｎ）として、変数値演算回路１０ｂの内部の構成例について説明する。時刻（クロックタイミング）ｔにおいて他の変数値演算回路１０が値を算出する変数は、ｘ１（ｔ）、・・・ｘi−１（ｔ）、ｘi＋１（ｔ）、・・・、ｘＮ（ｔ）と表記される。他の変数値演算回路１０は、変数値演算回路１０ａ、１０ｂであってもよい。あるいは、他の変数値演算回路１０は、後述する変数値演算回路１０ｃであってもよい。
肯定側変数値演算回路１０１は、否定が付されていない変数ｘiを含む節に基づいて変数ｘiの値を算出する。
否定側変数値演算回路１０２は、否定が付されている変数ｘi（¬ｘi）を含む節に基づいて変数ｘiの値を算出する。
【００７５】
図１１は、肯定側変数値演算回路１０１の構成例を示す図である。図１１の例で肯定側変数値演算回路１０１は、肯定側節演算回路２１１と、肯定側積回路２１２と、肯定側ラッチ２１３とを備える。
肯定側積回路２１２と、肯定側ラッチ２１３とは図５の場合と同様であり、ここでは説明を省略する。
肯定側節演算回路２１１は、否定が付されていない変数ｘiを含む１つの節に基づいて変数ｘiの値を算出する。
【００７６】
図１２は、肯定側節演算回路２１１の構成例を示す図である。図１２の例で、肯定側節演算回路２１１は、リテラル回路２２１ｂと、肯定側和回路２２４とを備える。リテラル回路２２１ｂは、ＮＯＴ回路２２２と、マルチプレクサ２２３ｂとを備える。
肯定側和回路２２４は、入力の数が２つに限らないこと以外は、図５の場合と同様である。
リテラル回路２２１ｂでは、図５のリテラル回路２２１の構成に加えて、マルチプレクサ２２３ｂへの恒偽（論理０）の入力が設けられている。節に含まれる変数の数がＮより少ない場合、Ｎ個のリテラル回路２２１ｂのうち余りのリテラル回路２２１ｂのマルチプレクサが恒偽を選択することで、このリテラル回路２２１ｂを不使用とすることができる。
【００７７】
図１３は、否定側変数値演算回路１０２の構成例を示す図である。図１３の例で、否定側変数値演算回路１０２は、否定側節演算回路２３１と、否定側積回路２３２と、否定側ラッチ２３３とを備える。
否定側積回路２３２と、否定側ラッチ２３３とは図５の場合と同様であり、ここでは説明を省略する。
否定側節演算回路２３１は、否定が付されている変数ｘi（¬ｘi）を含む１つの節に基づいて変数ｘiの値を算出する。
【００７８】
図１４は、否定側節演算回路２３１の構成例を示す図である。図１４の例で、否定側節演算回路２３１は、リテラル回路２２１ｂと、否定側和回路２４４とを備える。リテラル回路２２１ｂは、ＮＯＴ回路２２２と、マルチプレクサ２２３ｂとを備える。
否定側和回路２４４は、入力の数が２つに限らないこと以外は、図５の場合と同様である。
リテラル回路２２１ｂは、図１２の場合と同様であり、ここでは説明を省略する。
【００７９】
以上のように、変数値演算回路１０は、和積標準形の論理式に含まれる変数毎に設けられて対象変数の値を算出する。通知経路２０は、変数値演算回路１０が算出した対象変数の値を、他の変数値演算回路１０へ通知する。変数値演算回路１０の例である変数値演算回路１０ｂの肯定側変数値演算回路１０１は、変数ｘｉ（対象変数）の値に関して、他の変数値演算回路が算出した他の変数の値を論理式に入力したときに、論理式の節のうち否定の付いていない変数ｘｉを含む全ての節が真となるための、変数ｘｉの値を算出する。否定側変数値演算回路１０２は、他の変数値演算回路１０が算出した他の変数の値を論理式に入力したときに、論理式の節のうち否定の付いている変数ｘｉ（¬ｘｉ）を含む全ての節が真となるための変数ｘｉの値を算出する。多数決回路１０３は、肯定側変数値演算回路１０１が算出した変数ｘｉの値と、否定側変数値演算回路１０２が算出した変数ｘｉの値と、変数ｘｉの前回値とに基づいて、変数ｘｉの値を算出する。
【００８０】
このように、解探索装置１では、変数毎に、否定の付いていない変数を含む節、否定の付いている変数を含む節それぞれに基づいて変数値を算出し、算出した変数値と前回値とに基づいて変数値（今回値）を決定することで、いろいろな充足可能性問題に対応できる。特に、解探索装置１は、扱う変数の数及び節の数を、物理的な制約を無視すれば際限なく増やすことができる。
このように、解探索装置１によれば、汎用的に問題を解くことができる。
【００８１】
また、肯定側変数値演算回路１０１は、論理式の節のうち否定の付いていない変数ｘｉを含む節に含まれるリテラルのうち変数ｘｉのリテラル以外のリテラルが全て偽の場合は真を出力し、変数ｘｉのリテラル以外のリテラルのうちいずれか１つ以上が真である場合は偽を出力する肯定側節演算回路２１１と、論理式の節のうち否定の付いていない変数ｘｉを含む全ての節に対応する肯定側節演算回路２１１の出力の論理和を算出する肯定側積回路２１２と、を含む。
これにより、肯定側変数値演算回路１０１は、問題に対する汎用性が高い。特に肯定側変数値演算回路１０１では、扱う変数の数及び節の数を、物理的な制約を無視すれば際限なく増やすことができる。
【００８２】
また、肯定側節演算回路２１１は、他の変数値演算回路１０が算出した他の変数の値、他の変数の値の否定、及び、恒真のうち何れか１つを、節における他の変数のリテラルの態様に応じて選択するリテラル回路２２１（マルチプレクサ２２３）と、節に含まれる全てのリテラルに対応する全てのリテラル回路２２１の出力の否定論理和を算出する肯定側和回路２２４と、を備える。
これにより、肯定側節演算回路２１１は、問題に対する汎用性が高い。特に肯定側節演算回路２１１では、いろいろなリテラルに、リテラル回路２２１による選択の設定にて対応することができ、回路を組み換える必要がない。
また、肯定側節演算回路２１１は、マルチプレクサ及び否定論理和回路を用いた簡単なハードウェア構成で実装することができる。
【００８３】
また、否定側変数値演算回路１０２は、論理式の節のうち否定の付いている変数ｘｉ（¬ｘｉ）を含む節に含まれるリテラルのうち、変数ｘｉのリテラル以外のリテラルが全て偽の場合は偽を出力し、変数ｘｉのリテラル以外のリテラルのうちいずれか１つ以上が真である場合は真を出力する否定側節演算回路２３１と、論理式の節のうち否定の付いている変数を含む全ての節に対応する否定側節演算回路２３１の出力の論理積を算出する否定側積回路２３２と、を含む。
これにより、否定側変数値演算回路１０２は、問題に対する汎用性が高い。特に肯定側変数値演算回路１０１では、扱う変数の数及び節の数を、物理的な制約を無視すれば際限なく増やすことができる。
【００８４】
また、否定側節演算回路２３１は、リテラル回路２２１（マルチプレクサ２２３）と、節に含まれる全てのリテラルに対応する全てのリテラル回路２２１の出力の論理和を算出する否定側和回路２４４と、を備える。
【００８５】
これにより、否定側節演算回路２３１は、問題に対する汎用性が高い。特に否定側節演算回路２３１では、いろいろなリテラルに、リテラル回路２２１による選択の設定にて対応することができ、回路を組み換える必要がない。
また、否定側節演算回路２３１は、マルチプレクサ及び論理和回路を用いた簡単なハードウェア構成で実装することができる。
【００８６】
また、誤り回路１３１は、肯定側変数値演算回路１０１が算出した変数ｘｉの値、及び、否定側変数値演算回路１０２が算出した変数ｘｉの値のうち少なくともいずれか一方の真偽を、設定された確率で反転させる。
これにより、解探索装置１による解探索の速度を上げることができ、解の検出に要する時間が短縮されることが期待される。
また、解探索装置１が不正解の状態で停留したりループしたりする事態に陥った場合に、誤り回路１３１が上記のように変数値を反転させることで、不正解の状態から離脱することができる。
また、解が複数ある問題の場合、解探索装置１が、１つの解を検出した状態で誤り回路１３１が上記のように変数値を反転させることで、解を検出した安定状態から離脱して他の解を探索することができる。
【００８７】
また、矛盾検出回路１１１は、肯定側変数値演算回路１０１が算出した変数値と否定側変数値演算回路１０２が算出した変数値とが両立し得ないことを検出する。矛盾検出反映回路１２３は、他の変数値演算回路１０における矛盾検出回路１１１の検出結果を、多数決回路１０３による変数値の算出に反映させる。
これにより、解探索装置１では、解探索において算出した変数値に矛盾が生じた場合に変数値の変更を促進させて解探索の速度を上げることができ、解の検出に要する時間が短縮されることが期待される。
【００８８】
また、誤り回路１３１−３は、他の変数値演算回路１０における矛盾検出回路１１１が、肯定側変数値演算回路１０１が算出した変数ｘｉの値と否定側変数値演算回路１０２が算出した変数ｘｉの値とが両立し得ないことを検出した場合に、検出結果を多数決回路１０３による変数値の算出に反映させることを、設定された確率で抑制する。
これにより、解探索装置１は、解探索において算出した変数値の矛盾の検出結果を変数値に反映させる頻度を調整することができ、この点で、解の検出に要する時間の短縮を図ることができる。
【００８９】
ここで、矛盾検出反映回路１２３が、他の変数値演算回路１０における矛盾検出回路１１１の検出結果を変数値の算出に反映させることで、解の候補としての変数値に矛盾が生じている状態の解消の促進を図ることができる。一方、矛盾検出結果の反映では、解探索装置１が算出する解の候補としての変数値を変更するので、矛盾検出結果の反映が頻発すると、解から遠ざかる可能性が高い。これに対し、他の変数値演算回路１０における矛盾検出回路１１１が矛盾を検出した場合に、誤り回路１３１−３が検出結果の変数値への反映を抑制することで、解から遠ざかることを抑制できると期待される。このように、誤り回路１３１−３によれば、解の候補としての変数値に矛盾が生じている状態の解消の促進と、解から遠ざかることの抑制との両立を図ることができ、解の検出に要する時間が短縮されることが期待される。
【００９０】
図１０における誤り回路１３１の個数及び位置は一例である。変数値演算回路１０ｂが備える誤り回路１３１の個数及び位置は、この例に限らずいろいろな個数及び位置とすることができる。
例えば、変数値演算回路１０ｂが肯定側誤り回路１３１−１及び否定側誤り回路１３１−２を備えていない構成など、変数値演算回路１０ｂが、図１０に示す誤り回路１３１のうち一部又は全部を備えていない構成としても、解探索を行える場合がある。
また、変数値ラッチ１０４の後ろに誤り回路１３１を設けた構成としてもよい。この場合、図１０に示す３つの誤り回路１３１を全て残しておいてもよいし、これらのうち一部又は全部を取り除いた構成としてもよい。
【００９１】
図１０、１１及び１３には、変数値ラッチ１０４、矛盾検出側ラッチ１１２、反映側ラッチ１２２、肯定側ラッチ２１３、及び、否定側ラッチ２３３の４つのラッチが示されている。これらのラッチの個数及び位置は一例であり、変数値演算回路１０ｂが備えるラッチの個数及び位置は、この例に限らずいろいろな個数及び位置とすることができる。
例えば、各論理ゲート及びマルチプレクサにおける遅延の大きさによっては、変数値演算回路１０ｂが、図１０、１１及び１３に示す５つのラッチのうち一部又は全部を備えていない構成としても、適切なタイミングで変数値を算出できる場合がある。
【００９２】
また、図１２に示す構成内にラッチが設けられていてもよいし、図１４に示す構成内にラッチが設けられていてもよい。
また、変数値演算回路１０ｂが備えるラッチの構成方法は、特定の構成方法に限定されず、入力された値を保持可能ないろいろな回路を用いて構成することができる。例えば、変数値演算回路１０ｂが備えるラッチの一部または全部が、フリップフロップを用いて構成されていてもよい。
【００９３】
変数値演算回路１０がマルチプレクサを含まない構成となっていてもよい。この点について、図１５を参照して説明する。
図１５は、マルチプレクサを含まない変数値演算回路の構成例を示す図である。図１５に示す変数値演算回路１０ｃは、肯定側変数値演算回路１０１ｂと、否定側変数値演算回路１０２ｂと、多数決回路１０３と、変数値ラッチ１０４と、誤り回路１３１と、矛盾検出回路１１１と、矛盾検出総合回路１２１ｂと、矛盾検出反映回路１２３とを備える。肯定側変数値演算回路１０１ｂは、肯定側積回路２１２と、論理ゲート３３１及び３３２とを備える。否定側変数値演算回路１０２ａは、否定側積回路２３２ｂと、論理ゲート３３３とを備える。
【００９４】
図１５の各部のうち、図５の各部に対応して同様の機能を有する部分には、同一の符号（１０３、１０４、１１１、１２３、１３１−１、１３１−２、１３１−３）を付して、ここでは説明を省略する。
図１５では、変数値演算回路１０ｃが値を算出する変数をｘiとして、変数値演算回路１０ｃの内部の構成例について説明する。時刻（クロックタイミング）ｔにおいて他の変数値演算回路１０が値を算出する変数は、ｘｊ（ｔ）、ｘｋ（ｔ）、ｘｌ（ｔ）と表記される。他の変数値演算回路１０は、変数値演算回路１０ａ、１０ｂまたは１０ｃであってもよい。
【００９５】
変数値演算回路１０ｃは、変数値演算回路１０の例に該当し、変数ｘｉの値を算出する。図１５は、変数値演算回路１０ｃが、「（ｘｉ＋ｘｊ＋ｘｋ）（ｘｉ＋¬ｘｊ＋ｘｌ）（¬ｘｉ＋ｘｊ＋ｘｌ）（¬ｘｋ＋ｘｌ＋ｘｍ）＝１」が成り立つための変数ｘｉの値を求める場合の例を示している。
【００９６】
肯定側変数値演算回路１０１ｂは、肯定側変数値演算回路１０１の例に該当し、否定が付されていない変数ｘiを含む節に基づいて変数ｘiの値を算出する。上記の式「（ｘｉ＋ｘｊ＋ｘｋ）（ｘｉ＋¬ｘｊ＋ｘｌ）（¬ｘｉ＋ｘｊ＋ｘｌ）（¬ｘｋ＋ｘｌ＋ｘｍ）＝１」では、節「（ｘｉ＋ｘｊ＋ｘｋ）」及び「（ｘｉ＋¬ｘｊ＋ｘｌ）」が、否定が付されていない変数ｘiを含む節に該当する。
【００９７】
論理ゲート３３１、３３２の各々は、肯定側節演算回路２１１の例に該当し、否定が付されていない変数ｘiを含む１つの節に基づいて変数ｘiの値を算出する。
論理ゲート３３１は、節「（ｘｉ＋ｘｊ＋ｘｋ）」の値が「１」になるための、変数ｘiの値を算出する。リテラルｘｊ及びｘｋのうち、少なくとも何れか一方の値が「１」である場合、変数ｘｉの値が「０」、「１」のいずれであっても、節「（ｘｉ＋ｘｊ＋ｘｋ）」の値は「１」になる。この場合、論理ゲート３３１は、変数ｘｉの値を「０」と算出する。
一方、リテラルｘｊ及びｘｋのいずれも値が「０」である場合、節「（ｘｉ＋ｘｊ＋ｘｋ）」の値が「１」になるためには、変数ｘｉの値が「１」である必要がある。この場合、論理ゲート３３１は、変数ｘｉの値を「１」と算出する。
【００９８】
論理ゲート３３２は、節「（ｘｉ＋¬ｘｊ＋ｘｌ）」の値が「１」になるための、変数ｘiの値を算出する。リテラル¬ｘｊ及びｘｌのうち、少なくとも何れか一方の値が「１」である場合、変数ｘｉの値が「０」、「１」のいずれであっても、節「（ｘｉ＋¬ｘｊ＋ｘｌ）」の値は「１」になる。この場合、論理ゲート３３２は、変数ｘｉの値を「０」と算出する。
一方、リテラル¬ｘｊ及びｘｌのいずれも値が「０」である場合、節「（ｘｉ＋¬ｘｊ＋ｘｌ）」の値が「１」になるためには、変数ｘｉの値が「１」である必要がある。この場合、論理ゲート３３２は、変数ｘｉの値を「１」と算出する。
【００９９】
論理ゲート３３１の例では、論理ゲート３３１に入力されるリテラルｘｊ及びｘｋのいずれにも否定（¬）が含まれていない。この場合、論理ゲート３３１のように、ＮＯＲ回路を用いて肯定側節演算回路２１１を構成する。
一方、論理ゲート３３２の例では、論理ゲート３３２に入力されるリテラル¬ｘｊ及びｘｌのうち、リテラル¬ｘｊに否定（¬）が含まれている。そこで、論理ゲート３３２は、変数ｘｊ（ｔ）の値の否定をとっている。すなわち、論理ゲート３３２は、入力される変数ｘｊ（ｔ）の値の真（１）偽（０）を反転させる。
このように、肯定側節演算回路２１１を構成する論理ゲートとして、否定を含まないリテラルについては、入力される変数値をそのまま使用し、否定を含むリテラルについては、入力される変数値の否定をとる論理ゲートを用いることができる。
【０１００】
肯定側積演算回路２１２ｂは、肯定側積演算回路２１２の例に該当し、否定を付されていないｘｉを含む各節を結合する論理積の演算を行う。具体的には、肯定側積回路２１２ｂは、肯定側節演算回路２１１の例である論理ゲート３３１及び３３２の出力のＯＲをとる。
【０１０１】
図１５の例で、肯定側積演算回路２１２ｂは、否定を付されていないｘｉを含む節の数よりも多い入力を受け付ける。否定を付されていないｘｉを含む節の数が２つであるのに対し、肯定側積演算回路２１２ｂは、３つの入力を受け付ける。肯定側積演算回路２１２ｂへの入力のうち、否定を付されていないｘｉを含む節の数よりも多い分の入力については、恒偽を示す「０」が入力される。この入力「０」は、肯定側積演算回路２１２ｂが行うＯＲの演算に影響を与えない。
【０１０２】
このように、否定を付されていないｘｉを含む節の数と同数の入力、または、それ以上の数の入力を受け付けるＯＲ回路を用いて、肯定側積演算回路２１２を構成することができる。このＯＲ回路への入力のうち、否定を付されていないｘｉを含む節の数よりも多い分の入力については、「０」を入力することができる。
【０１０３】
否定側変数値演算回路１０２ｂは、肯定側変数値演算回路１０２の例に該当し、否定が付されている変数ｘi（¬ｘi）を含む節に基づいて変数ｘiの値を算出する。上記の式「（ｘｉ＋ｘｊ＋ｘｋ）（ｘｉ＋¬ｘｊ＋ｘｌ）（¬ｘｉ＋ｘｊ＋ｘｌ）（¬ｘｋ＋ｘｌ＋ｘｍ）＝１」では、節「（¬ｘｉ＋ｘｊ＋ｘｌ）」が、否定が付されている変数ｘiを含む節に該当する。
【０１０４】
論理ゲート３３３は、否定側節演算回路２３１の例に該当し、否定が付された変数ｘiを含む１つの節に基づいて変数ｘiの値を算出する。
論理ゲート３３３は、節「（¬ｘｉ＋ｘｊ＋ｘｌ）」の値が「１」になるための、変数ｘiの値を算出する。リテラルｘｊ及びｘｋのうち、少なくとも何れか一方の値が「１」である場合、変数ｘｉの値が「０」、「１」のいずれであっても、節「（¬ｘｉ＋ｘｊ＋ｘｌ）」の値は「１」になる。この場合、論理ゲート３３３は、変数ｘｉの値を「１」と算出する。
一方、リテラルｘｊ及びｘｋのいずれも値が「０」である場合、節「（¬ｘｉ＋ｘｊ＋ｘｌ）」の値が「１」になるためには、変数ｘｉの値が「０」である必要がある。この場合、論理ゲート３３３は、変数ｘｉの値を「０」と算出する。
【０１０５】
論理ゲート３３１及び３３２を例に肯定側節演算回路２１１について説明したのと同様、否定側節演算回路２３１を構成する論理ゲートとして、否定を含まないリテラルについては、入力される変数値をそのまま使用し、否定を含むリテラルについては、入力される変数値の否定をとる論理ゲートを用いることができる。
【０１０６】
否定側積演算回路２３２ｂは、否定側積演算回路２３２の例に該当し、否定を付されているｘｉを含む各節を結合する論理積の演算を行う。具体的には、否定側積回路２３２ｂは、否定側節演算回路２３１からの出力のＡＮＤをとる。図１５の例では、否定側節演算回路２３１の例の論理ゲートは、論理ゲート３３３のみである。そこで、否定側積回路２３２ｂは、論理ゲート３３３の出力をそのまま出力する。
【０１０７】
図１５の例で、否定側積演算回路２３２ｂは、否定を付されているｘｉを含む節の数よりも多い入力を受け付ける。否定を付されているｘｉを含む節の数が１つであるのに対し、否定側積演算回路２３２ｂは、２つの入力を受け付ける。否定側積演算回路２３２ｂへの入力のうち、否定を付されているｘｉを含む節の数よりも多い分の入力については、恒真を示す「１」が入力される。この入力「１」は、否定側積演算回路２３２ｂが行うＡＮＤの演算に影響を与えない。
【０１０８】
このように、否定を付されているｘｉを含む節の数と同数の入力、または、それ以上の数の入力を受け付けるＡＮＤ回路を用いて、否定側積演算回路２３２を構成することができる。このＡＮＤ回路への入力のうち、否定を付されているｘｉを含む節の数よりも多い分の入力については、「１」を入力することができる。
【０１０９】
矛盾検出総合回路１２１ｂは、矛盾検出総合回路１２１の例に該当し、他の変数値演算回路１０から通知された矛盾検出結果を総合する。具体的には、矛盾検出総合回路１２１ｂは、他の変数値演算回路１０から通知された矛盾検出結果の信号のＯＲをとる。いずれかの変数値演算回路１０が矛盾を検出した場合、矛盾検出総合回路１２１ｂは１を出力する。いずれの変数値演算回路１０も矛盾を検出していない場合、矛盾検出総合回路１２１ｂは０を出力する。
【０１１０】
矛盾検出総合回路１２１ｂは、変数ｘｉと節を共有している変数が対象となっている矛盾検出結果の入力を受ける。図１５の例では、変数ｘｉと節を共有している変数は、変数ｘｊ、ｘｋ及びｘｌである。矛盾検出総合回路１２１ｂは、これらの変数が対象となっている矛盾検出結果ｃｏｎｔｒａｊ（ｔ）、ｃｏｎｔｒａｋ（ｔ）及びｃｏｎｔｒａｌ（ｔ）の入力を受ける。
【０１１１】
図５の例、及び、図１０の例では、いずれも、マルチプレクサ１２４が、変数ｘｉと節を共有している変数が対象となっている矛盾検出結果を選択し、選択された矛盾検出結果が矛盾検出総合回路１２１へ入力される。
これに対して、図１５の例では、変数ｘｉと節を共有している変数が対象となっている矛盾検出結果が、直接、矛盾検出総合回路１２１ｂへ入力される。これにより、図１５の構成では、マルチプレクサ１２４を不要とすることができる。
矛盾検出総合回路１２１への入力のうち、変数ｘｉと節を共有している変数の数よりも多い分の入力については、恒偽を示す「０」が入力される。この入力「０」は、矛盾検出総合回路１２１が行うＯＲの演算に影響を与えない。
【０１１２】
次に、図１６から図１８を参照して、解探索装置１による解探索の例について説明する。
図１６は、解探索装置１を用いた解探索の第一例を示す図である。
図１６では、解が１つ存在する充足可能性問題ｕｆ５０−０１００．ｃｎｆを解いた場合の例を示している。充足可能性問題ｕｆ５０−０１００．ｃｎｆの論理式は、変数の数が５０、節の数が２１８である。
図１６の例では、変数値が解に等しくなったときに状態（変数値）が安定している。このように、解探索装置１では、状態が安定することで解を発見したことを検出することができる。
【０１１３】
図１７は、解探索装置１を用いた解探索の第二例を示す図である。
図１７では、解が存在しない充足可能性問題ｕｕｆ５０−０１．ｃｎｆを解いた場合の例を示している。充足可能性問題ｕｕｆ５０−０１．ｃｎｆの論理式は、変数の数が５０、節の数が２１８である。
図１７の例では、解を発見することができず、状態が安定しない。
このように、本発明によれば、解が存在しないことを推定できる。
【０１１４】
図１８は、解探索装置１を用いた解探索の第三例を示す図である。
図１８では、解が２つ以上存在する充足可能性問題ｕｆ５０−０１．ｃｎｆを解いた場合の例を示している。充足可能性問題ｕｆ５０−０１．ｃｎｆの論理式は、変数の数が５０、節の数が２１８である。
図１８の例では、変数値が解に等しくなったときに状態が安定している。この状態から変数値が変化した後、変数値が別の解に等しくなった時に再び状態が安定している。
このように、解探索装置１では、複数の解それぞれで状態が安定することで、複数の解を発見することができる。
【０１１５】
次に図１９を参照して、解探索装置１にて得られる効果をアメーバ型アルゴリズムとの関係で説明する。
アメーバ型アルゴリズムは、充足可能性問題などの解を探索するアルゴリズムとして提案されている。アメーバ型アルゴリズムでは、変数を伸び縮みするアメーバが構成する足に対応付け、アメーバが光を嫌う性質、及び、この光を嫌う性質に反する動作を低頻度で行うことを反映させてアメーバの動きを模擬する。
【０１１６】
図１９は、アメーバ型アルゴリズムを用いて充足可能性問題を解く場合の、解探索の繰り返し回数の例を示すグラフである。
ここでは充足可能性問題の規模（変数の数Ｎ）を大きくしていったときのアメーバ型アルゴリズムの性能を定量的に評価しやすくするために、変数の数が大きくなっても解を１つだけもつような充足可能性問題を、次のような方法で作成した。
・  解が１つ存在することが予めわかっている、変数の数が５０、節の数が２１８の充足可能性問題ｕｆ５０−０１００．ｃｎｆをｋ個用意する。
・  それらを互いの変数が共有されないように論理積で連結する。
こうすると、変数の数がｋ×５０、節の数がｋ×２１８で、やはり解が１つ存在するような充足可能性問題を作成できる。
ここでいう解探索の繰り返し回数は、解の候補として変数値のセットを算出する回数である。図１９のグラフの横軸は問題の規模（変数の数Ｎ）を示し、縦軸は、繰り返し回数を示す。
【０１１７】
線Ｌ１１は、アメーバ型アルゴリズムによる解探索における、問題の規模と繰り返し係数との関係を示す。線Ｌ１２は、充足可能性問題を解くための一般的な確率的局所探索アルゴリズムにおける、問題の規模と繰り返し回数との関係を示す。一般的な確率的局所探索アルゴリズムでは、この場合の繰り返し回数がＯ（Ｎ）（Ｎのオーダ）になるのに対し、アメーバ型アルゴリズムでは、この場合の繰り返し回数はＯ（ｌｏｇＮ）（ログＮのオーダ）となる。
解探索装置１の場合、アメーバ型アルゴリズムの場合と同様、比較的少ない繰り返し回数で解を求めることができる。さらに、解探索装置１によれば、１回の繰り返し処理に要する時間が比較的短くて済む。これにより、解探索装置１によれば、比較的短時間で解を探索することができる。
【０１１８】
解探索装置１の全部または一部を、コンピュータでエミュレート（Emulate、模擬）するようにしてもよい。
図２０は、少なくとも１つの実施形態に係るコンピュータの構成例を示す概略ブロック図である。図２０の構成で、コンピュータ４００は、ＣＰＵ（Central Processing Unit、中央処理装置）４０１、主記憶装置４０２、補助記憶装置４０３及びインタフェース４０４を備える。
【０１１９】
上述の解探索装置１の全体を１つのコンピュータ４００でエミュレートする場合、解探索装置１の各部の動作は、プログラムの形式で補助記憶装置に記憶されている。ＣＰＵ４０１は、プログラムを補助記憶装置４０２から読み出して主記憶装置４０３に展開し、このプログラムに従って解探索装置１の動作を模擬する。また、ＣＰＵ４０１は、プログラムに従って、ラッチなどメモリを用いて構成される素子に対応する記憶領域を、主記憶装置４０３に確保する。
【０１２０】
１つの変数値演算回路１０を１つのコンピュータ４００でエミュレートする場合、変数値演算回路１０の各部の動作は、プログラムの形式で補助記憶装置に記憶されている。ＣＰＵ４０１は、プログラムを補助記憶装置４０２から読み出して主記憶装置４０３に展開し、このプログラムに従って変数値演算回路１０の動作を模擬する。また、ＣＰＵ４０１は、プログラムに従って、ラッチなどメモリを用いて構成される素子に対応する記憶領域を、主記憶装置４０３に確保する。
また、ＣＰＵ４０１は、インタフェース４０４を介して他の変数値演算回路１０との信号のやり取りを行う。
【０１２１】
変数値演算回路１０は、変数値演算回路１０ａ、１０ｂまたは１０ｃであってもよい。他の変数値演算回路１０も、変数値演算回路１０ａ、１０ｂまたは１０ｃであってもよい。また、他の変数値演算回路１０は、ＣＰＵ４０１でエミュレートされていてもよいし、図に示される素子を用いてハードウェア的に構成されていてもよい。
【０１２２】
変数値演算回路１０を部分的に１つのコンピュータ４００でエミュレートする場合、変数値演算回路１０のうちエミュレート対象部分の動作は、プログラムの形式で補助記憶装置に記憶されている。ＣＰＵ４０１は、プログラムを補助記憶装置４０２から読み出して主記憶装置４０３に展開し、このプログラムに従って変数値演算回路１０のうちエミュレート対象部分の動作を模擬する。また、エミュレート対象部分にラッチなどメモリを用いて構成される素子が含まれる場合、ＣＰＵ４０１は、プログラムに従って、この素子に対応する記憶領域を主記憶装置４０３に確保する。また、ＣＰＵ４０１は、インタフェース４０４を介して他の部分との信号のやり取りを行う。
変数値演算回路１０は、変数値演算回路１０ａ、１０ｂまたは１０ｃであってもよい。
図２０に示す構成で、ＣＰＵ４０１に加えて、あるいは代えて、ＧＰＵ（Graphics Processing Unit）が用いられていてもよい。
【０１２３】
上述した、解探索装置１の全部または一部をエミュレートするプログラムなど、解探索装置１が行う演算及び制御の全部または一部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することで各部の処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【０１２４】
以上、本発明の実施形態を図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【産業上の利用可能性】
【０１２５】
本発明の実施形態は、解探索装置に適用してもよい。
【符号の説明】
【０１２６】
１、１ａ、１ｂ、１ｃ  解探索装置
１０、１０ａ、１０ｂ、１０ｃ  変数値演算回路
２０、２０ａ、２０ｂ、２０ｃ  通知経路
１０１、１０１ａ、１０１ｂ  肯定側変数値演算回路
１０２、１０２ａ、１０２ｂ  否定側変数値演算回路
１０３  多数決回路
１０４  変数値ラッチ
１１１  矛盾検出回路
１１２  矛盾検出側ラッチ
１２１、１２１ｂ  矛盾検出総合回路
１２２  反映側ラッチ
１２３  矛盾検出反映回路
１２４、２２３、２２３ｂ、３１５、３２５  マルチプレクサ
１３１、１３１−１、１３１−２、１３１−３  誤り回路
２１１、２１１ａ、２１１ｂ  肯定側節演算回路
２１２、２１２ｂ  肯定側積回路
２１３  肯定側ラッチ
２２１、２２１ｂ  リテラル回路
２２２  ＮＯＴ回路
２２４、２２４ａ  肯定側和回路
２３１、２３１ａ、２３１ｂ  否定側節演算回路
２３２、２３２ｂ  否定側積回路
２３３  否定側ラッチ
２４４、２４４ａ  否定側和回路
３１１、３１２、３１３、３１４、３２１、３２２、３２３、３２４、３３１、３３２、３３３  論理ゲート
４００  コンピュータ
４０１  ＣＰＵ
４０２  主記憶装置
４０３  補助記憶装置
４０４  インタフェース
【図１】
2019017412.tif 000004
【図２】
2019017412.tif 000005
【図３】
2019017412.tif 000006
【図４】
2019017412.tif 000007
【図５】
2019017412.tif 000008
【図６】
2019017412.tif 000009
【図７】
2019017412.tif 000010
【図８】
2019017412.tif 000011
【図９】
2019017412.tif 000012
【図１０】
2019017412.tif 000013
【図１１】
2019017412.tif 000014
【図１２】
2019017412.tif 000015
【図１３】
2019017412.tif 000016
【図１４】
2019017412.tif 000017
【図１５】
2019017412.tif 000018
【図１６】
2019017412.tif 000019
【図１７】
2019017412.tif 000020
【図１８】
2019017412.tif 000021
【図１９】
2019017412.tif 000022
【図２０】
2019017412.tif 000023
【国際調査報告】
2019017412.tif 000024
2019017412.tif 000025