一連のオブジェクトがあるとしますS。fセットがその上にS特定のデータ構造を構築する場合、次のアルゴリズムがあります。が大きい場合、および/または非常に異なるオブジェクトが含まれている場合は、大きくなり、使用できなくなります (つまり、割り当てられたメモリに収まりません)。これを克服するために、いくつかの交差しないサブセットに分割し、サブセットごとにビルドします。構造体を使用すると、構造体を使用するよりも効率が低下しますが、少なくともこの方法では、メモリの制約に適合できます。のサイズはそれ自体よりも速く成長するため、 の合計サイズは のサイズよりもはるかに小さくなります。Df(S) = DSDSS = S1 + S2 + ... + SnDinf(S)SDiD
nただし、 を減らすこと、つまりサブセットの数を減らすことは依然として望ましいことです。または の合計サイズを小さくしDiます。このため、それぞれに「類似した」オブジェクトが含まSれるように分割する必要があります。入力オブジェクトが互いに「十分に類似している」場合、より小さな出力構造が生成されるためです。Sif
問題は、 のオブジェクトの「類似性」Sと のサイズがf(S)相関する一方で、 を評価する以外に後者を計算する方法がなく、あまり高速f(S)ではないことです。f
私が現在持っているアルゴリズムは、次の各オブジェクトを からSのいずれかに繰り返し追加するSiことです。これにより、（この段階で）結合Diサイズの増加が最小限に抑えられます。
for x in S:
i = such i that
size(f(Si + {x})) - size(f(Si))
is min
Si = Si + {x}
これにより実用的な結果が得られますが、確かに最適とはかなりかけ離れています (つまり、可能な最小の結合サイズ)。また、これは遅いです。いくらか高速化するために、 がすでに にあるオブジェクトと「十分に類似している」size(f(Si + {x})) - size(f(Si))ものだけを計算します。ixSi
そのような種類の問題に対する標準的なアプローチはありますか?
分枝境界アルゴリズム ファミリについては知っていますが、非常に遅くなるため、ここでは適用できません。私の推測では、合理的な時間内に の最適な分布を計算することは不可能SですSi。しかし、反復的に改善する一般的なアルゴリズムはありますか?
編集：
コメントが指摘したように、私は「類似性」を定義したことはありません。実際、私が望むのはSi、組み合わせたサイズDi = f(Si)が最小または少なくとも十分に小さいサブセットに分割することだけです。「類似度」はこれだけで定義されており、残念ながら簡単に計算することはできません。簡単な概算がありますが、それはあくまでも概算です。
したがって、後者を計算する簡単な方法がないsum f(Si)ことを考慮して最小化する (おそらくヒューリスティックな) アルゴリズムが必要です。良い結果が得られる可能性が非常に低いケースを破棄するために使用する近似値のみです。