4

複数の合同を含む複数のセットがあります。

各セットの 1 つのアイテムに中国の剰余定理を適用するときに、最小の剰余を見つけようとしています。

たとえば、2 セットの場合:

セット 1:

7x + 1
7x + 3

セット 2:

11x
11x + 2
11x + 7
11x + 8

7x + 1 & 11x を取ると 77x + 22になります。すべての組み合わせをテストする必要なく
、最小の残り (上記の例では 77x + 8 ) を求めています。

これは私の実際の問題の非常に単純化されたバージョンです (それぞれに ~100 の合同がある ~50 セットです)。

この問題にどのようにアプローチするかについて私は立ち往生しています。アドバイスをいただければ幸いです。

また、数学用語が間違っていたら申し訳ありません。

4

2 に答える 2

2

時間内に最小の残差を見つける中間アルゴリズムがあります

O(max(|S1|, |S2|) log(max(|S1|, |S2|)))。

最初に中国剰余定理を使用して、S1 の t mod n1 と t mod n2 == 0 を満たすすべての 0 <= t < n1*n2 の集合 T1 と、t を満たすすべての 0 <= u < n1*n2 の集合 T2 を見つけます。 S2 の mod n1 == 0 および t mod n2。

つまり、質問で与えられた例では：

T1 = {22, 66}

T2 = {0、7、35、63}

ここで探している剰余は、T1 の任意の t1 と T2 の t2 の和 (t1 + t2) mod n1*n2 です。したがって、最小の剰余は、T1 と T2 の 2 つの最小要素の合計、または n1*n2 よりわずかに大きい 2 つの要素のいずれかです。セット T1 と T2 を並べ替えると、最初のセットを最小要素から最大要素までスキャンし、最大セットを最大要素から最小要素までスキャンすることで、2 番目のケースの最適なソリューションを見つけることができます。つまり、T1 の位置を進めます。合計が n1*n2 よりも小さい場合は常に、n1*n2 よりも大きい場合は常に T2 の位置を減らします。

2 つ以上の法 n1 .. nk がある場合、私が見ることができる最速の解決策は、法を 2 つのセットに分割することです。たとえば、n1 .. nr と nr+1 .. nk は、T1 の t が t であるように、セット T1 を見つけます。すべての 1 <= i <= r に対して Si の mod ni およびすべての r < i <= k に対して t mod ni == 0。それに応じて T2 が定義されます。複雑さはモジュライの分布に依存しますが、通常は可能性の数の平方根程度になります。Schroeppel と Shamir によるアルゴリズムがあり、メモリをいくらか節約できますが、時間の計算量は減少しません。

あなたのアプリケーション、つまり 50 の係数と 100 の合同では、このアルゴリズムはまだ約 100^25 のステップを使用しており、これは実行不可能です。残念ながら、多項式アルゴリズムはないようです。特に、式 x^2 == a (mod n) の最小解 x を見つけること (n は高合成整数) は NP 完全であることが知られています。しかし、そのような解決策を見つけることで、問題を軽減できます。したがって、合同に悪用できる特別なプロパティがない限り、問題は一般的にNP完全である必要があります。

于 2011-06-29T22:21:12.837 に答える
1

セットを S1、S2、... Sk とすると、各セットのモジュラスは n1 > n2 > ... > nk であり、Si の剰余は a_i1 < a_i2 < ... したがって、例: n1 = 11 、n2 = 7 および S1 = {0, 2, 7, 8}、S2 = {1,3}

擬似コードは次のとおりです。

Find the target modulus, i.e. n = lcm(n1, n2, ..., nk)

Convert the sets Si into hashtables, so that you can check if a certain element is in the set or not.

for (int b = 0; b < n / n1; b++)
    foreach (int c in [a_11, a_12, a_13, ...])
        //candidate target reminder
        a = b*n1 + c
        works = true;
        foreach (int ni in [n2, n3, ..., nk])
           //test if there is an element in Si, which gives the correct reminder
           //if not then this candidate doesn't work, go to the next
           if( not Si contains (a % ni))
               works = false;
               break
        if (works)
            print "The solution is n*x+a"
            exit

アイデアは、最小限を検索することです。最小値が a の場合、a は として表すことができます a=x*n1+y。ここで、y は S1 の要素であるため、昇順ですべての可能性を繰り返します。次に、それらのそれぞれについて、他のセットと照合します-現在のaによって満たされる合同が含まれているかどうか。2 番目のセット S2 について言えば、S2 からの合同が存在する必要があります。たとえば、p*n2+q で、ある p に対して a = p*n2+q となります。しかし、これは a % n2 = q を意味します (q は剰余であるため)。つまり、% n2 は S2 にあるはずです。

アルゴリズムの複雑さは O (n/n1 * |S1| * k) です。そのため、n1 を最大のモジュラスとして選択しました。しかし、本当に複雑さを最小限に抑えたい場合は、n/ni * |Si| となるような方法でセット Si を選択する必要があります。最小で。

于 2011-06-28T04:13:15.857 に答える