ペア

Question

Iは （123; 1765）のようなIDのペアの設定したのセットから最小のカーディナリティのセットを作成し、私はn個のグループにそれらの対を分離するのに必要...

を （8977 1212）個々のサイズ（ペア数）。それらの集合は、最小基数を持たなければならない（=各グループには異なるIDをできるだけ少なくすべきである）。 この問題を解決する既存のアルゴリズムはありますか？私はどこで/どのようにそれを検索するか分からない。 私は現在自分のプロジェクトの負荷分散に取り組んでおり、限られたRAM（各IDは大規模なデータセットに接続されている）のために、できるだけ少ないIDをロードする必要があるため、これは必要です。

ありがとうございます！

編集： 背景： クラスタ内のノードが異なると、IDで識別されるデータセットを比較する必要があります。各比較はIDのペアです（ID1とID2のデータセットを比較します）。各ノードは、どのIDを比較しなければならないかを知るためにペアを取得し、対応するデータセットをRAMにロードします。マスターノードは、大量のペアを小さなバンチに分割し、それらをスレーブノードに分配します。各ノードには限られた量のデータセットしか格納できないため、これらの小さなバンチにはできるだけ少ないIDを格納する必要があります。しかし、ノードのRAM量は異なるため、基数が最小のグループのサイズが異なります。 比較は対称であるため、compare（ID1、ID2）はcompare（ID2、ID1）と同じであるため、各ペアは一意です。どのデータセットを比較する必要があるかは、そのジョブをマスターに送ったクライアントによってIDのペアの集合として除外されます。

例： クライアントは、データセット(1;2)の比較を望んでいる(7;9)、(9;105)、(7;105)、(2;4)、(4;1)（通常はここでは通常は数百万人ので、はるかに比較する必要があります）クライアントがマスターにそれらのペアを送信し 、登録されたスレーブが2つあります。マスターはその作業のスタックを2つのグループに分ける必要がありますが、より多くのIDが各グループの一部であるほど、スレーブによってロードされるデータセットが多くなります（IDは特定のデータセットに対応します）。 ((1;2), (9;105)...)と((2;4), (7;105)...)：代わりにと((7;9), (9;105), (7; 105))（再びちょうど3のID）（スレーブのみ3つのデータセットをロードするために持っているので、わずか3つの異なるIDが含まれています）

は、理想的には、マスターは((1;2), (2;4), (4;1))のようなグループを作成します。ここでは両方のスレーブが4つ以上のIDをロードする必要があります。両方のスレーブがデータセットnoをロードする必要があります。 これはどういうわけか最適化する必要があります..

Answer 1

私の最初の本能は、集約関数と距離関数をカスタマイズする特別なクラスター分析で解決できる可能性があります。

• クラスタメンバーはペアになります。
• クラスタ集合体は、 クラスタ内のすべてのペアの集合論的結合である（標準アプローチでは平均値または中央値ではなく）。
• クラスタと比較して任意の対の距離関数は、クラスター凝集 （SOセット差のカーディナリティで見出されない組の要素 数であろう;これはでユークリッド 距離を置き換え標準アプローチ）。
• 一部のクラスタアルゴリズムでは、希望するクラスタの数を に設定しているため、2に設定します。
• 最後に、クラスタ の集約の要素数が同じになるようにバランスを調整する必要があるため、さらに微調整を行いますが、それでも は実行可能です。

しかし、あなたは何百万というポイントを比較すると言います。クラスター分析に必要な処理は、入力した入力が多いほど指数関数的に増加します。この状況では、NPまたはNP完全であるかどうかを調べる価値があります。私はそれに精通していませんが、それは疑いの余地があります。その場合、真の最適が常にあなたから逃げるでしょう。

しかし、問題がNP完全であることが判明した場合でも、最適化を行うことができます。妥当な時間内に大域最適で到着することを保証することはできません。たとえば、ペアのセットをサブセットに分割し、上のようなアルゴリズムをサブセットに実行することができます。それはまだ改善の可能性があります。