C++ でいくつかのコードを書いており、2 つの未知の変数の不等式のリストが満たされているかどうかを確認する必要があります。
たとえば、可能なリストの 1 つは P = Q、Q < S、P = S であり、これは満たされるべきではありません。
別の例として、P = Q、Q < S、R = P、S > R を満たす必要があります。
私はこれを行う方法を長く懸命に考えてきましたが、追加されたすべての新しい不等式が以前のものすべてを満たすかどうかを確認することを含む、長くて退屈な方法以外の方法を見つけることができないようです.
これは、C++ というよりもブール論理の演習です。あなたがPythonを知っているなら、それを使ってください。
より高速な方法は、一度に 1 つのステートメントで "順序付け" (数学的な意味で) を構築することです。それはあなたがシーケンスを持っているところです、abc想定と
ここで、シーケンス内の各ものが互いに等しいもののベクトルであるとします。上記の例では:
P=Q
注文は次のようになります。
[P,Q]
次のQ
注文があるので、次のようにします。
[P,Q],[S]
[P,Q]<[S] を知っている
したがって、P=S は明らかな矛盾です。
まず、P = Q出現するすべての を に置き換えて、すべての等式を削除QしPます。これは に減少P = Q, Q < S, R = P, S > RしR < S, S > Rます。
次に、変数を頂点として有向グラフを作成し、リストにまたはが含まれている場合は からPへのエッジを作成します。QP < QQ > P
3 番目に、グラフにサイクルが含まれているかどうかを確認します。グラフにサイクルが含まれていない場合、不等式は充足可能です。
この問題に関連する 2-SAT をググってみることをお勧めします。