SATのラグランジュの方法による解法

概要

論文の詳細を見る
命題論理の充足可能性問題(SAT)は,情報科学における基本的な問題であり,また,NP完全な問題としてよく知られている.従来,よく使用されてきたDavis-Putnumのアルゴリズムは厳密な意味でSATを解くことができるが,問題が大きくなると解くのに長い時間を必要とする.一方,SelmanのGSATアルゴリズムは,局所的アルゴリズムであり,充足不能な問題は扱えないが,ほとんどの充足可能な問題に対して,高速に解を見つけることができる.多くの離散的な制約条件付き最適化問題(決定問題)をニューラルネットワークで解くことができることが知られている.このアプローチでは,問題の解がエネルギー関数の最小値に対応するようにエネルギー関数を作り,その最小値を勾配法により求める.従って,最小値ではなく極小値にとらわれることが問題となる.この問題を解決するひとつの方法は,ラグランジュプログラミングニューラルネットワークやタブ学習を用いたニューラルネットワークに用いられている.ニューロン間の結合係数(ラグランジュ乗数)の学習を用いることである.SATに関しても,このアプローチを用いることができる.我々は,SATを連続的な変数算をとる問題とみなし,ラグランジュの方法を用いて解く連続的局所的アルゴリズムLMSを提案し,その有効性を示している.本論文では,LMSにおけるラグランジュ乗数の学習方程式の減衰係数について,その実行時間に対する影響を調べる.
社団法人電子情報通信学会の論文
1995-03-27

SATのラグランジュの方法による解法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク