5

私は組み合わせアルゴリズムに関するいくつかの演習を行っており、以下の質問を解決する方法を見つけようとしています:

25 ビットのグループが与えられた場合、15 を設定 (選択) します (順列不可で順序 NON は重要です)。

n!/(k!(n-k)!) = 3.268.760

ここで、これらの可能性のすべてについて、すべての一意の 25 ビット メンバーを他のすべての 25 ビット メンバーと交差させる行列を作成します。その間の関係では、少なくとも 11 個の共通の設定ビット (0 ではなく 1 のみ) が必要です。

それをバイナリ データとして表すことを説明してみましょう。したがって、最初のメンバーは次のようになります。

0000000000111111111111111 (10 zeros and 15 ones) or (15 bits set on 25 bits)
0000000001011111111111111 second member
0000000001101111111111111 third member
0000000001110111111111111 and so on....
...
1111111111111110000000000 up to here. The 3.268.760 member.

これらの値を 1 x 1 の行列に交差させると、15 ビットが共通である必要があります。結果は >= 11 であるため、「有用な」結果です。

1 x 2 の場合、14 ビットが共通であるため、有効な結果も得られます。

すべてのメンバーに対してこれを行うと、最終的に 1 x 3.268.760 を超えると 5 ビットが共通になるため、11 未満であるため「役に立ちません」。

私が必要としているのは、(数学またはアルゴリズムによって) 11 ビット共通のすべての可能性をカバーするために必要なメンバーの最小数を見つけることです。

言い換えれば、他のすべてに対してテストされた場合、3.268.760 x 3.268.760 ユニバース全体で共通する少なくとも 11 ビットを持つ可能性がある N メンバーのグループ。

ブルート フォース アルゴリズムを使用して、81 個の 25 ビット メンバーでこれを達成できることがわかりました。しかし、この数はもっと小さくする必要があると思います (12 に近いもの)。

ブルート フォース アルゴリズムを使用して、3.268.760 を超える 12 メンバーのすべての可能なバリエーションを作成しようとしましたが、可能性の数が非常に多いため、計算に 100 年以上かかります (3,156x10e69 の組み合わせ)。

私は組み合わせ論についてグーグルで調べましたが、これらの問題がどの分野に当てはまるか分からないほど多くの分野があります。

したがって、組み合わせ論のどの分野に関する方向性、またはこれらの問題に対するアルゴリズムは大歓迎です。

PS: 参考までに。2 人のメンバーの「類似度」は、次を使用して計算されます。

(Not(a xor b)) and a

その後、共通ビット数が与えられたビットをカウントするための小さな再帰ループがあります。

編集:約束された (@btilly) 以下のコメントで、関係の「フラクタル」画像関係マトリックスのようなフラクタルまたは画像へのリンクを次に示します。

カラー スケールの範囲は、赤 (15 ビットが一致) から緑 (11 ビットが一致)、10 ビットより小さい値の場合は黒です。

この画像は、4096 の最初のグループのサンプルです。

4

2 に答える 2

1

tl;dr:大規模で非常に対称的なグラフで支配集合を解きたいとします。正確な答えを期待するべきではないというのは正しいです。これが私の問題なら、貪欲な解決策から始めてローカル検索を試みます。1 つのセットを選択し、他のセットを変更してそれを取り除くようにしてください。これには、どのセットが 1 回だけカバーされるかを追跡するためのデータ構造が必要です。

編集：さて、これは下限のより良いアイデアです。1 から最適解の値までの k ごとに、[25 15 を選択] * k / [k セットの最大ジョイント カバレッジ] の下限があります。12 の境界 (私の計算では、実際には 10 です。いくつかの隣人を忘れているためです) は、k = 1 に対応します。選択された k のすべての対称性が一緒に平均化され、各要素が 1 回カバーされるようにスケーリングされる分数解を作成します。このソリューションのコストは、[25 15 を選択] * k / [これらの k セットの最大ジョイント カバレッジ] であり、これは少なくとも目標とする下限と同じ大きさです。ただし、各セットの限界リターンが減少しているため、元の m セットのソリューションと同じくらい小さいです。

最大カバレッジの計算は一般的に難しいですが、係数 (e/(e-1))-近似 (≈ 1.58) アルゴリズムがあります: 貪欲で、すぐに実装できるように思えます (注: そのセットを選択する必要があります毎回最も発見されている他のセットをカバーしています）。貪欲な解に e/(e-1) を掛けると、k 要素の最大範囲の上限が得られます。これは、前の段落で説明した下限を十分に補うことができます。

警告: この上限が [25 choose 15] より大きい場合、k は大きすぎます!

于 2012-04-09T22:44:56.297 に答える
0

この種の問題は非常に難しいので、正確な答えを見つけることができると期待すべきではありません。

欲張りな解決策は、「かなり良い」答えを生み出すはずです。しかし..どのように貪欲になるのですか？

アイデアは、常に次の要素を選択して、現在一致していない可能性をできるだけ多く一致させる要素にすることです。残念ながら、300万人を超える可能性のあるメンバーがいるため、数百万の一致しないメンバーとの照合を試みる必要があります（次の最良の推測は、候補セット内の別のメンバーとすでに一致している可能性があります）。

したがって、次の要素の選択については貪欲でなければなりません。現在一致していないすべての要素に最終的に一致する確率の合計を最大化するために、各ビットを選択します。

そのためには、最初のメンバーで1である最初のビットが2番目のメンバーでも1である場合に、2つのランダムメンバーが少なくとも11ビットの共通点を持つことが判明する確率である2次元ルックアップテーブルが必要になりますP。。この225の確率の表は、事前に計算する必要があります。P(n, m)mn

このテーブルは、次のルールを使用して簡単に計算できます。

  1. P(15, m)の場合は0 m < 11、それ以外の場合は1です。

  2. の場合n < 15：

    P(n, m) = P(n+1, m+1) * (15-m) / (25-n) + P(n+1, m) * (10-n+m) / (25-n)

それでは、互いに「非常に遠い」メンバーから始めましょう。私の提案は次のようになります：

  1. 最初の15ビット1、残りは0。
  2. 最初の10ビットは0、残りは1です。
  3. 最初の8ビット1、最後の7 1、残りは0。
  4. ビット1-4、9-12、16-23は1、残りは0です。

次に、（25から15を選択）メンバーのユニバースから始めて、最初のコレクションの要素の1つに一致するメンバーをすべて削除します。

次に、アルゴリズムの核心に入ります。

While there are unmatched members:
    Find the bit that appears in the most unmatched members (break ties randomly)
    Make that the first set bit of our candidate member for the group.
    While the candidate member has less than 15 set bits:
        Let p_best = 0, bit_best = 0;
        For each unset bit:
            Let p = 0
            For each unmatched member:
                p += P(n, m) where m = number of bits in common between
                             candidate member+this bit and the unmatched member
                             and n = bits in candidate member + 1
            If p_best < p:
                p_best = p
                bit_best = this unset bit
        Set bit_best as the next bit in our candidate member.
    Add the candidate member to our collection
    Remove all unmatched members that match this from unmatched members
The list of candidate members is our answer

私はコードを書いたことがないので、このアルゴリズムがどれほど良い答えを生み出すかわかりません。しかし、それが現在よりも良くないと仮定すると、77人の候補メンバー（私たちは4人から始めました）について、あなたはあなたの比類のない候補を271回通過させる必要があります（最初のビットを見つけるために25、2番目のビットを見つけるために24など） 11は15番目を検索し、もう1つは一致したメンバーを削除します）。それは20867パスです。平均して100万人の比類のないメンバーがいる場合、それは200億回のオペレーションのオーダーになります。

これは速くはありません。しかし、それは計算上実行可能でなければなりません。

于 2012-04-09T20:02:10.677 に答える