從集對創建套最小基數的

Question

我有一個像 一組對ID中的; （1212; 8977）（123 1765）...

我需要那些對分成n組，分離每個個體的大小（對數）。這些集合應該具有最小基數（=每個組中應該儘可能少地具有不同的ID）。 有沒有解決這個問題的現有算法？我不確定在哪裏/如何搜索它。 這是必要的，因爲我目前正在對我的一個項目進行負載平衡，並且由於RAM有限（每個ID連接到一個較大的數據集），每個節點都必須加載儘可能少的ID。

在此先感謝！

編輯： 一些背景： 羣集中的不同節點必須比較由ID標識的數據集。每個比較是一對ID（比較ID1與ID2的數據集）。每個節點都會得到一堆對，以知道要比較哪些ID，並將相應的數據集加載到RAM中。主節點將一大對對分成較小的束並將它們分配給從節點。由於每個節點只能存儲有限數量的數據集，因此這些較小的數據組需要包含儘可能少的不同ID。但節點具有不同數量的RAM，因此具有最小基數的組應具有不同的大小。 比較是對稱的，所以比較（ID1，ID2）與比較（ID2，ID1）相同，所以每一對都是唯一的。需要比較哪些數據集的客戶端會將這些作業作爲一對ID分配給主服務器。

一個例子： 客戶機要數據集(1;2)，(7;9)，(9;105)，(7;105)，(2;4)，(4;1)的比較（通常在這裏應該不多更多的比較，所以百萬通常） 客戶端發送那些對給主，這有兩個註冊的奴隸。現在，主人需要將這堆工作分成兩組，但是每個組中包含更多不同的ID，則需要由從站加載更多數據集（ID對應於特定數據集，請記住？）。

所以理想的主人將創建一組像((1;2), (2;4), (4;1))（僅包含3點不同的ID，所以從只裝載3集）和((7;9), (9;105), (7; 105))（再次只是三個ID），而不是： ((1;2), (9;105)...)和((2;4), (7;105)...)。在這裏兩個奴隸都需要加載4個ID等等，兩個奴隸都需要加載數據集編號。 2和105. 這需要以某種方式進行優化..

Answer 1

我的第一本能是說，也許這可以通過特殊聚類分析來解決，您可以在其中自定義聚合和距離函數。

• 集羣成員將成對。
• 集羣聚合將是 集羣中所有對的集合理論聯合（而不是標準方法中的平均值或中值）。
• 任何對相比於簇的距離函數將是 數在一對元件未在羣集聚合 （所以差集的基數發現的;這取代了的歐幾里得 距離標準方法）。
• 某些羣集算法可以在 預設中設置所需羣集的數量，因此您可以將其設置爲2。
• 最後，因爲您需要平衡一些事情，以便集羣 具有相同數量的元素，請進一步調整，但仍然可以使用 。

但是，你說你會有數百萬點的比較。聚類分析所需的處理以指數方式增加您輸入的更多輸入。在這種情況下，值得研究您的問題是NP還是NP-complete。我對此並不十分精通，但我懷疑是這樣的，在這種情況下，真正的最佳狀態總是會讓你失望。

但是，如果你發現你的問題實際上是NP完全的，那麼你仍然可以優化，你將無法保證在合理的時間內到達全局最優。因此，例如，您可以將您的對子集分解爲子集，並在子集上運行上述算法。這可能仍然是一個改進。