私はこの問題に何日も取り組んできましたが、まだ解決策がありません。簡単な例で説明しましょう。
長さ 8 の整数の配列があるとします。すべてのセルは特定の値を取ることができます。最初の 4 つのセルは 0 または 1 を取ることができ、残りの半分は 0、1 または 2 を取ることができます。これらの 3 つの配列はいくつかの例です。
{1,1,0,1,2,1,0,2}
{1,0,0,1,0,0,2,2}
{0,0,0,0,2,0,0,1}
ただし、次のように、配列を構築するためのいくつかの制約があります。
constraint1 = {0,0,-,-,-,-,-,-} // !(constraint1[0]==0 && constraint1[1]==0)
constraint2 = {-,1,0,-,-,-,-,-} // !(constraint2[1]==1 && constraint2[2]==0)
constraint3 = {-,-,-,-,1,1,-,0} // !(constraint3[4]==1 && constraint3[5]==1 && constraint3[7]==0)
理解を深めるために;
{0,1,0,2,0,1,0,0} // this is not valid, because it violates the constraint2
{0,0,2,2,1,1,0,1} // this is not valid, because it violates the constraint1
{1,1,1,0,0,1,0,0} // this is valid, because it violates none of the constraints
問題は、これらの制約から推論された t タプル (t-長さ)の数を見つける必要があるということです。たとえば、どの制約にも違反しない生成された配列の 1 つが と呼ばれるとしmyArrayます。を見ると、が 0 のconstraint1場合は 1 でなければならないことがわかります。したがって;myArray[0]myArray[1]myArray[1]constraint1
myArray[0]=0 => myArray[1]=1
ここで を見ると、が 1のconstraint2場合は0 にはならないことが示されています。私たちのケースでは、すでに1を選択しているので、は 0 になります。myArray[1]myArray[2]myArray[1]myArray[2]
myArray[1]=1 => myArray[2]=0
これらの含意が組み合わされると、もう 1 つの制約が次のように形成されます。
myArray[0]=0 => myArray[1]=1 => myArray[2]=0
myArray[0]=0 => myArray[2]=0 // new constraint
{2,-,0,-,-,-,-,-}
これは問題を説明するためだけの非常に単純な例であることを強調したいと思います。私の場合、配列の長さは 50 ～ 200 の間で変化しています。数値の制約は、0 から 500 の間 (場合によってはそれ以上) の任意の値にすることができます。また、必要なのは推論された制約の数だけであり、それらを見つける必要がないことも強調したいと思います。
これが私が試したいくつかのアプローチです。
1) 少なくとも 1 つの共通オプションが同じである制約のオプションの真理値表を見つけます。次に、すべての t タプルを探します。スペースが非常に大きいことがわかりました。
2) Mathematica の制約に違反しないすべての解 (充足可能な問題) を見つけ、どの t-タプルが欠落しているかを探します。解決策は 1 つも見つかりません。
問題は、これらのアプローチでは、必要のないスペース全体を生成しようとしたことです。スペース全体を列挙せずに t タプル (制約) の数を見つけるためのより良いアイデアはありますか?