1
我有一個加權邊和加權頂點的雙向圖。我想找到不相交的N組，連接的頂點，所以：將加權圖分割成等權重組
- 每個組的求和的權重接近，但大於某一值TargetWeight
- 所選邊的權重以形成這些不大於團體越少越好。這裏有一個問題：如果還選擇了另一條邊（邊的一部分是重量的一部分），邊的重量可能會減小。舉一個例子：邊E1的重量爲20，邊E2的重爲30，它們的重量爲5.僅取E1會使重量爲20，同時考慮到E1和E2將導致45的總重量（僅分擔重量考慮一次）。
N是預先已知的，但如果結果會大大改善，則允許更大。
TargetWeight已經提前知道，當多個成本較低的小團隊比一個成本高的大團隊好時，沒有真正的指標可用。
該圖在典型情況下具有大約50k個節點。該圖不存儲在數據庫中。
您可以將此問題看作是一種聚類算法，但關於聚類的一般討論可能與我所需要的不同。我嘗試了KMeans算法，但是我發現結果不夠好。現在我正在使用基於探索的啓發式方法來檢查某個選擇對未來羣體的選擇有多好。這種方法很有效，但速度很慢。