満足度モデルの数を数える - 指定された数学的制約
https://cs.stackexchange.com/questions/126829
-
29-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
質問
#sat 問題を解決するためのアルゴリズムが多数あります。 DPLLアルゴリズムとあらゆる種類のプログラミング言語に実装されています。私が見た限りでは、それらはすべて入力としてCNF上のブール式を取得し、満たされた解釈の数を出力します。
href="htpps://en.wikipedia.org/wiki/constraint_（mathematics )" REL="NOFOLLOW NOREFERRORER">数学的制約は、一方、インスタンスを定義する別の方法です。 SATの問題のうち、さまざまな最適化でよく使用されます。ここで、これらの制約に関していくつかの機能を最適化しようとします。 入力として数学的な制約を取っているプログラムは、満足解釈の数を出力しますか？
例
ブール式 $ Q=（A \ Lor B）\ Wedge（C \ Lor D）$ として表される $$ A + B \ GEQ 1 \\ C + D \ GEQ 1 $$ 、またはマトリックスとして、またはマトリックスとして、$ A $ とサポートベクトル< SPAN CLASS="math-container"> $ b $ $$ a= \ begin {bmatrix} 1＆1＆0＆0 \\ 0＆0＆1＆1 \ end {bmatrix} \\ B=begin {bmatrix} 1＆1 \ end {bmatrix} $$
ここで、すべての変数 $ a、b、c、d \ in \ {0,1 \} $ 。 $ q $ を入れるプログラムがあることを知っていますが、解釈回数を出力しますが、 $ a $ < / span>と $ b $ 入力として（または同様の構成）と同じ解釈数を出力しますか？
解決
私は2つの合理的なアプローチを知っています。
アプローチ＃1 ：凸状ポリテープ内の整数点数を数える。
あなたが提供した一連の線形不平等のセットは、不等式 $ 0 \ lea、b、c、d \ le 1 $ と一緒に、凸型のポリテープを定義します。さて、このPolytope の範囲内の整数ポイントの数をカウントします。
それをするための標準的なアルゴリズムがあり、あなたは直接申請することができます。 「Polytopeの整数ポイント」または「Polytopeの格子点を数える」を検索する場合は、多くの研究論文があります。例えば、 https://cstheory.stackexchange.com/q/22280/5038 、整数線形プログラミング（ILP）の問題
をすべて解決する。アプローチ＃2 ： CNFに変換してから#SATソルバーを使用してください。
必ず制約をCNF式に変換できます。各線形不等式は、一組のCNF句に変換できます。 $ x_i + \ dots + x_j \ ge 1 $ に直ちにCNF句 $（x_i）に対応しています。 \ lor \ dots \ lor x_j）$ 。 $ x_i + \ dots + x_j \ ge c $ の形式のより一般的な線形不平等については、少なくとも $ C $ $ k $ 変数 $ x_i、\ dots、x_j $ は真です。それをエンコードする標準的な方法はたくさんあります。 https://cstheory.stackexchange.com/q/23771/5038 、 ref 、エンコーディング1 SATソルバー、
のためのnのNの制約（1つのアプローチは、 $ x_i + \ dots + x_j $ を計算するブール回路を変換し、それをに比較します。 $ C $ 、次に tseitin transform を使用してBoolean回線をCNFに変換します。標準の加算器および比較回路を使用してそのようなブール回路を作成できます。しかし、他にも多くの方法があります。）
制約のセットに相当するCNF式を持っていると、任意のオフの#SATソルバーを使用して、そのCNF式への解の数をカウントすることができます。
これら2つのアプローチのどれがよりよく機能するかを言うのは難しいです。あなたが扱っているインスタンスの種類を両方とも試す必要があるかもしれません。 $ x_i + \ dots + x_j \ ge c $ の形式の線形不等式がある場合は、 $ C $ が大きく、次にアプローチ＃1が優れている可能性があります。しかし、 $ C $ が小さい場合は、Approach＃2が優れています。
他のヒント
句の代わりに制約を直接使用してDPLLを実装できます。これには、データ構造と伝播アルゴリズムを変更する必要がありますが、すべて同じ機能です。
拘束のすべての変数が1つ以外に設定されるとすぐに、単位の伝播が発生する可能性があります。
制約のすべての変数が設定されるとすぐに、競合が発生する可能性があります。
残りのアルゴリズムは同じままです。
ブール値の制約は、隠されたCNF句のコレクションだけです（潜在的には拘束に応じて潜在的には多数の句）。
