4

私は現在、数理最適化問題のアルゴリズムに取り組んでおり、次の状況に対処する必要があります。

多くの状況で、アルゴリズムはこの状況でどのサブセットS⊂Nが最適であるかを決定する必要があります。
N = {0、1、2、...、126、127}
| S | ∈{0、1、2、3、4、5}（サブセットのサイズは0から5の間です）

これにより、可能なサブセットの総数は265.982.833になります。（binom（128、5）+ binom（128、4）+ ... + binom（128、0））

可能なすべてのサブセットを事前に計算して配列に格納すると、この配列には265.982.833エントリがあり、メモリフットプリントは約1.27 GBになります。最適化を行わず、サブセットをバイト配列として単純に格納する必要はありません。

この場合、アルゴリズムがインデックスiの特定のサブセットに含まれる要素を知る必要がある場合は、テーブルルックアップのみが必要です。ただし、膨大なメモリ要件は受け入れられません。

したがって、私の質問は基本的に、事前に計算された配列を必要とせずに、インデックスiに基づいてサブセット内の要素を効率的に計算するアルゴリズムを誰かが考えることができるかどうかです。

含まれているサンプルの編集：
lookupTable [0] = {}
lookupTable [1] = {0}
...
lookupTable [127] = {126}
lookupTable [128] = {127}
lookupTable [129] = {0、1}
lookupTable [ 130] = {0、2}
...
lookupTable [265982832] = {123、124、125、126、127}

4

2 に答える 2

5

前のサブセットから各サブセットを構築するのは簡単です。サブセットを128ビットの数値として表すことも簡単です（ただし、ほとんどの値は適格なサブセットにマップされないため、質問の128の値が実際の値なのか単なる例なのかはわかりません）。確かに私が使用する最初のアプローチ。それが機能する場合、それはすべてO（1）であり、ストレージコストは極端ではありません（4ではなくインデックスの場合は16バイト）。

サブセットの簡潔なインデックスを本当に保存したい場合は、次の再帰を使用します。ここで、S（n、k）は、値<nからのサイズ≤kのすべてのサブセット（またはサブセットの数）を表します。

s(n,0) = { {} }
s(n,k) = (s(n-1,k-1) ⊙ {n}) ⋃ s(n-1,k) if n ≥ k > 0
s(n,k) = {} if n < k

ここで、演算子は「の各要素にP ⊙ S追加する」を意味します（したがって、結果はとまったく同じサイズになります）。したがって、カウントアルゴリズムと見なすと、次のようになります。SPP

S(n,0) = 1
S(n,k) = S(n-1,k-1) + S(n-1,k) if n ≥ k > 0
S(n,k) = 0 if n < k

2番目の再帰は、次のように再表現できます。

S(n,k) = Σni=kS(i-1,k-1)
（jsMath、grrrを使用すると見栄えが良くなります。）

これは、最大の要素の順にセットを生成するという別の言い方です。したがって、セットから始めて、すべてのセットを最大の要素として{0...k-1}、次にすべてのセットを、というように続けます。セットの各グループ内で、サイズのセットを見つけるために繰り返します。ここでも、最小の最大値から始めて、選択した最大値より1つ小さい値まで進みます。{k}{k+1}(k-1)

したがって、結果が負になるまでからからを連続S(n,k)して減算することにより、インデックスのインデックスセットの最大値を把握できます。次に、結果セットに追加します。1減らして、をに設定して繰り返します。S(i-1, k-1)ikn{i}kni-1

の関連するテーブルを事前に計算するとS(n,k)、約640の有効な組み合わせがあり、反復の代わりに二分探索を使用して各ステップでを見つけることができるiため、計算に時間がかかりますがk log(n)、これはひどいことではありません。

于 2013-03-27T03:13:34.977 に答える
0

単純な実装ではビットビットを使用します（bitX == 1は、アイテムXがセットに存在することを意味します）追加の制約は、マスク内の5ビット以下が1つになることです。また、セットを表すには128ビットが必要です。

素数の積を使用してセットを表すには、セットあたり64ビット未満しか必要ありません（124 ... 128番目の素数は{124：691、125：701、126：709、127：719、128：727}です。それらの製品は64ビット、IICCに収まります。それでもいくつかのビットを浪費します（OQが示したように、適切な列挙は32ビットに収まります）が、2セットの「重複する」一般的なアイテムを簡単にチェックできます。彼らのGCDの。

どちらの方法でも、値の配列を並べ替える必要があり、この配列内のセットのランクを列挙値として使用します。

于 2013-03-27T19:57:36.200 に答える