わかりました。2^Nを取得することはできませんが、サンプルセットを減らすことはできます。これを行うために、「構成された制約」を計算します。構成された制約は、左側のすべてのオプションが選択されている場合、右側のオプションを選択できない制約ですが、左側のオプションに基づく他の制約は適用されません。
一連の制約から、すべての可能な合成制約のセットを計算する必要があります。必須ではありませんが、右手のグループが左のグループよりも小さい場合は、左手と右手を入れ替えて既存の制約を「修正」します。これにより、いくつかの構成された制約が軽減される可能性がありますが、スワッピングにはより優れたヒューリスティックが可能です。
また、グループごとに任意に選択できるオプションの「最小セット」を計算する必要があります。この最小セットは、使用可能なオプションのリストから、構成された制約の左側に表示されるオプションを削除することによって計算されます。
アルゴリズムが続きますが、CCが正しく計算されることを証明していません。もしそうなら、それらを使用して可能な組み合わせの数を計算できることを証明します。
- 左手のグループが右手のグループ以下になるように制約を修正します。
制約を作成します。
- 制約を左手で並べ替える
続いて、制約ごとに：
- 同じ左手でそれに続くすべての制約で制約を折り、、を回し
x1 <-> y1てx1 <-> y2...x1 <-> yNSet(x1) <-> Set(y1 ... yN)
- 次の場合は、すでに折りたたまれている各制約を使用して、折りたたまれた制約を作成します。
- x1は、すでに折りたたまれている制約の右側にはありません
- x1は、左側のどの要素の同じグループにも含まれていません
- 折りたたまれた制約とそのすべての構成を折りたたまれた制約のセットに追加します
すべてのオプションを選択し、固定制約の左側に表示されているオプションを削除して、最小セットを計算します。
これで、次の式を使用して組み合わせの数を計算できます。CCを合成制約と呼びましょう。その場合、組み合わせの数は次のとおりです。
C(Mininum Set) + CCC1 + ... + CCCn
どこ：
- C（最小セット）は、最小セットで可能な組み合わせの数です。
- CCCxは、最小セットを取得し、CCxの左側にオプションがあるグループをそのオプションに置き換えてから、CCxの右側にあるオプションを削除することで可能な組み合わせの数です。
式は純粋に加算的であることに注意してください。つまり、その式で期待される結果が得られるには、次の2つの条件が満たされている必要があります。
- その2つの用語に同じ組み合わせを含めることはできません。
- すべての組み合わせは、これらの用語で説明する必要があります。
- どの用語でも無効な組み合わせを生成することはできません。
最初の証明として、同じ左手に2つの異なるCCがないことに注意してください。2つのCCの左手が同じで右手が異なる場合、一方のCCに適用する必要のある追加の制約があるか、もう一方のCCに無効な制約が適用されていることを意味します。
同じ左手を持つ2つのCCはなく、最小セットには定義上どのCCの左手も含まれていないため、2つのCCは、一方に対して選択され、他方に対しては選択されない少なくとも1つのオプションによって区別できます。 。したがって、2つのCCが同じ組み合わせを生成することはできません。
2番目の証明として、CCのセットには、定義上、左側のオプションのすべての有効な組み合わせが含まれていることに注意してください。
最小セットにもCCのセットにも表示されない組み合わせが1つあると想定します。この組み合わせに左側のオプションが含まれていない場合は、定義上、最小セットの組み合わせである必要があります。したがって、左手からのオプションが含まれている必要があります。
CCのセットには左側の有効な組み合わせがすべて含まれているため、同じ左側のオプションを持つCCが1つあります。したがって、この組み合わせには、そのCCのどの組み合わせにも含まれないオプションが必要です。ただし、そのCCに含まれていないオプションは、他のCCの左側に表示されるオプションと、制約によって除外する必要があるオプションのみです。どちらも当てはまらない可能性があるため、この組み合わせは存在できません。
3番目の証明として、最初に最小セットについて考えてみましょう。最小セットには、グループの左側にオプションが含まれていません。すべての制約は1つの左側と1つの右側のオプションの間にあるため、最小セットには制約は適用されません。
それでは、CCについて考えてみましょう。CCには、定義上、左側のオプションの有効な組み合わせがあります。その左手と互換性のないオプションはすべて右手に表示する必要があり、その右手からのオプションは最小セットから削除する必要があります。そもそもそれらの間で互換性がない最小セットにはオプションがないため、CCのどの組み合わせでも満たされない制約はあり得ません。
そして、それで証明は終わりです。
コメントの例を使用して、これがどのように適用されるかを見てみましょう。
G1: x1, x2, x3
G2: y1, y2
G3: z1, z2, z3
R1: x1 <-> y2
R2: x3 <-> y2
R3: y1 <-> z1
R4: y2 <-> z2
R5: y2 <-> z3
CC1: {x1} <-> {y2}
CC2: {x3} <-> {y2}
CC3: {y1} <-> {z1}
CC4: {x1, y1} <-> {y2, z1}
CC5: {x3, y1} <-> {y2, z1}
CC6: {y2} <-> {z2, z3}
リストにない構成されたグループについて簡単に考えてみましょう。
R1&R2: {x1, x3} <-> {y2} -- not in the list because x1 and x3 belongs to the same
group
R1&R5: {x1, y2} <-> {y2} -- not in the list because the left hand of R2, y2
appears in the right hand of R1
次に、各セットで可能なオプションを見てみましょう。
Minimum Set: (x2), (), (z1, z2, z3)
CC1: (x1), (), (z1, z2, z3) -- replace G1 with x1, remove y2 from G2
CC2: (x3), (), (z1, z2, z3) -- replace G1 with x3, remove y2 from G2
CC3: (x2), (y1), (z2, z3) -- replace G2 with y1, remove z1 from G3
CC4: (x1), (y1), (z2, z3) -- replace G1 with x1, G2 with y1, remove y2 and z1
CC5: (x3), (y1), (z2, z3) -- replace G1 with x3, G2 with y1, remove y2 and z1
CC6: (x2), (y2), (z1) -- replace G2 with y2, remove z2 and z3 from G3
さて、物事を追加しましょう：
C(Minimum Set) = 1 * 0 *3 = 0
CCC1 = 1 * 0 * 3 = 0
CCC2 = 1 * 0 * 3 = 0
CCC3 = 1 * 1 * 2 = 2
CCC4 = 1 * 1 * 2 = 2
CCC5 = 1 * 1 * 2 = 2
CCC6 = 1 * 1 * 1 = 1
C(Minimum Set) + CCC1 + CCC2 + CCC3 + CCC4 + CCC5 + CCC6
0 + 0 + 0 + 2 + 2 + 2 + 1 = 7
ここにもう1つ考えを追加します。5つのルールに対してCCCは6つしかなく、他の方法で予想される32の用語よりもはるかに少ないですが、ルールごとに、これまでに作成されたすべてのCCCと比較して組み合わせる必要があるため、これらのCCCは2^Nの最悪の時間で計算されます。それらは2進数と考えることができます。ここで、ルールが結合されている場合はビットが設定され、そうでない場合は設定されません。
ただし、互換性のない組み合わせはすぐに破棄されるため、新しいルールを組み合わせるたびに、すでに無効と見なされている組み合わせで時間が失われることはありません。また、ルールを事前に並べ替えることで、同じグループ内の連続するルールを、適切なデータ構造で非互換性をテストすることなく破棄できます。
この特定の例が示すように、平均時間は2^Nよりもはるかに優れている可能性があります。
代替アルゴリズムと考慮事項
2-SATと3-SATの話があります。私には、これは2-SATの問題であるように思われます。つまり、すべての制約a <-> bは、実際には句 "！a ||！b"であるという意味です。したがって、すべての制約をまとめて、「（！x1 ||！y2）&&（！x1 ||！z4）&&（！y2 &&！z3）」などと書くことができます。つまり、ある意味で「解決」できるということです。これを真にする各オプションへのブール割り当てがあるかどうかを確認できます。Aspall、Plass、Tarjanによるこのための線形アルゴリズムがあり、ここにスライドプレゼンテーションがあります。
しかし、制約を解決できるかどうかを知ることは、求められたものではありません。質問されたのは、2-SATの問題を真に保ちながら、すべてのオプションを設定できる方法の数です。
現在、2-SAT問題を満たす方法の数を数えるための効率的なアルゴリズムがあります。たとえば、このペーパーでは、1.2561nで実行されるアルゴリズムを紹介します。しかし、それでも、そのソリューションを満たす組み合わせの数を計算できるようにするためのソリューションを知る必要があるため、役に立ちません。
ウィキペディアによると、この論文には、すべてのソリューションを効率的に列挙するアルゴリズムがあります。これは私たちが望んでいることです。しかし、カウントがすでに指数関数的である場合は、列挙されます。おそらく2nよりも優れていますが、それでも指数関数的です。
2-SAT問題のすべての解決策を列挙すると、各グループの組み合わせの数は、オプションが選択されていない各グループの無料オプション（制約に表示されないオプション）の数を掛けた1で与えられます。解決策によって。
たとえば、前のグループと制約のセットを取り上げます。相互排除を含む2-SATの問題は次のとおりです。
（！x1 ||！y2）&&（！x3 ||！y2）&&（！y1 ||！z1）&&（！y2 ||！z2）&&（！y2 ||！z3）&&（！x1 || ！x3）&&（！y1 ||！y2）&&（！z1 ||！z2）&&（！z1 ||！z3）&&（！z2 ||！z3）
最初の行は5つのルールです。2行目は、制約ルールに表示される同じグループ内のすべてのオプションの相互排除です。
この2-SAT問題の解決策は次のとおりです。
x1 x3 y1 y2 z1 z2 z3 Combinations
true false true false false true false 1
true false true false false false true 1
true false true false false false false 0
true false false false true false false 0
true false false false false true false 0
true false false false false false true 0
true false false false false false false 0
false true true false false true false 1
false true true false false false true 1
false true true false false false false 0
false true false false true false false 0
false true false false false true false 0
false true false false false false true 0
false true false false false false false 0
false false true false false true false 1
false false true false false false true 1
false false true false false false false 0
false false false true true false false 1
false false false true false false false 0
false false false false true false false 0
false false false false false true false 0
false false false false false false true 0
false false false false false false false 0
最初の2つのソリューションでは、オプションが選択されていないグループがないため、組み合わせの数は1です。3番目のソリューションでは、グループG3に対してオプションが選択されていないため、1に0を掛けます。 false」、グループG1に選択されたオプションはなく、1つの無料オプション：x2。したがって、1を1で乗算し、G2またはG3でオプションが選択されていない場合は0を乗算します（この場合、空きオプションの数は0です）。
ここで、各グループで選択されている1つのオプションを強制し、それでも2-SATであると主張するにはどうすればよいかという問題があります。前述のように、問題には2つの暗黙の制約があります。グループごとに1つだけのオプションを選択する必要があります。これらの2つの制約は、次のように記述できます。
x 1 || x 2 || x 3（オプションx1のグループxの場合..x 3 ）（
！x 1 ||！x 2）&&（！x 1 ||！x 3）&&（！x 2 ||！x 3）
後者の制約は2-SATであり、前者は重要なケースでは3-SATです。たまたま、最初の制約を適用しませんが、カウントは0になります。カウントアルゴリズムは次のようになります。
- 制約のない組み合わせの場合は、各グループの制約のないオプションの数を互いに乗算します。
- 制約と完全な組み合わせの場合、次のカウントの結果を追加します。
- ソリューションごとに、互いに「真」と評価されたオプションを使用せずに、各グループの制約のないオプションの数を掛けます。
したがって、制約のないオプションが少なくとも1つあるすべてのグループについて、選択は暗黙的で匿名です。すべてのオプションが何らかの制約の一部であるすべてのグループについて、オプションが選択されていない場合、そのグループのカウントは0になるため、そのソリューションの組み合わせの数も0になります。
これは、有効な>2-SAT制約から問題をだましているように感じます。結局のところ、これが可能であれば、3-SATの問題は、その2-SAT部分の解を列挙し、3-SAT部分を満たさないものをすべて破棄するだけで解決できます。残念ながら、私が特定できる根本的な違いが1つあります。
- 問題の2-SAT部分で解決されないすべての述語には、それ以上の制約はありません。
句に対するこのかなり制限的な制約を考えると、2-SATの明示的な制約の解を列挙することでこの問題を解決できます。
誰かがこれをさらに追求したいなら、先に進んでください。私が提案した2nソリューションの改善に満足しています。