最大平均サブセットサイズの等間隔サブセットを分割する方法は？

Question

私はそれらの間にN個のオブジェクトとN * Nの距離のセットを持っています。私はこの集合をサブセットに集めて、各クラスタにすべてのオブジェクトが同じ距離を持ち、すべてのクラスタの平均（cluster_size）が最大になるようにしたい。

私は、このようなアルゴリズムによって、このタスクを解決しようとした：

1. は、オブジェクト間のすべてのユニークな距離を列挙します。各一意の距離xの

2. は、オブジェクトAとBとの間の距離が正確である場合、AとBとの間にエッジが存在するノードと隣接行列、などのオブジェクトに基づいてグラフを構築することができX

3. は最大クリークを見つけることができますこのグラフ。このクリークのサイズが現在の最大値よりも大きい場合 - オブジェクト

4. 繰り返し

   のセットから結果に保存された更新最大と店舗クリーク結果として

5. 削除するオブジェクトのオブジェクトの集合が空でなくなるまで

効率的な[approximate]ソリューションがありますか？

Answer 1

平均（クラスタサイズ）=ポイントの合計数/クラスタ

これを最大化する唯一の方法の数は、クラスタの数を最小にすることです。それは最適化の目標としてかなり悪い選択であるようです。この目的を再考することができます。

あなたのアルゴリズムはかなり賢明だと思います。問題はおそらくNP困難なので、あなたは欲張りな近似を使いたいと思う。

私は、再計算にもっと怠け者であり、いくつかの境界を追加することをお勧めします。

1. すべてのユニークな距離のサブグラフを作成します。

2. サイズ、降順でサブグラフをソートします。

3. 以前の反復からキャッシュされた値がない限り、各サブグラフで最大のクリークを見つけます。全体的な最大のクリークを覚えています。現在の最大値が残りのサブグラフより大きい場合には停止します。

4. 最高のサブグラフが出力されました。

5. すべてのグラフから含まれているノードを削除し、見つかったばかりのノードが含まれている最良のクリークを忘れてしまいます。 2に戻る。