ニューラルネットワークの並列実行によるSATの解法

概要

論文の詳細を見る
代表的なNP完全問題の一つにSAT(充足可能性問題)がある。SATとは, 与えられた論理式を真にする変数の割り当てが存在するかどうかを判定する問題である。著者らは, ラグランジュの方法を利用することによってSATを解くニューラルネットワークLPPH (Lagrange programming neural network)を提案している。LPPHは, 局所探索法の一つであり, 初期値によって解を見つける速さの差が大きい。また, LPPHはDPや分岐限定法などに比べて高速に解を見つけることができるが, それでも大規模な問題を解く場合は非常に時間がかかる。そこで, LPPHを並列実行して解くことが考えられる。本論文では, 各プロセッサがそれぞれ異なる初期値に対する解の探索を独立に並列実行する方法を提案する。この方法で並列実行を行った場合, どれか一つのプロセッサが解を見つければ良い。この並列実行ではプロセッサ間で頻繁にデータをやり取りすることがないので並列化によって生じるオーバーヘッドが小さい。本論文では, LPPHを上述の方法で並列実行してSATを解いた場合の計算時間について考察を行う。
1997-09-24