找到歐幾里得空間中的「最緊密」子集

Question

我在R^d中的點x_1，x_2，... x_n \處給出。我希望找到k個點的子集，使得這些k個點之間的距離總和最小。天真的這是一個O（N選擇K）的問題，但我正在尋找一個更快的算法。

我能想到兩個替代等效製劑：

1. 最小邊緣權重團問題：認爲點作爲曲線圖的，邊緣權重是的距離，並尋找最小權團。 This is equivalent to maximal edge weight problem，這是已知的NP完全。但是，我知道我的圖表嵌入在R^d中，並且所有權重都是正數，所以或許這可能有所幫助？

2. 最小無約束子矩陣問題：我給出了對稱距離矩陣，我想找到一個總和最小的kXk未成年人。

我很感謝這方面的幫助。

Answer 1

最明顯的優化並不需要任何不同的公式。

只是貪婪地找到一個接近最優的候選人。嘗試通過交換成員以線性時間來優化它。然後做一個詳盡的搜索，但是當新的候選人比貪婪的候選人更糟的時候停下來修剪搜索空間。

E.g.

1. 計算平均值由平方距離平均
2. 測試
3. Order對象順序長度爲k的所有NK間隔，選擇最佳
4. 對於任何非選擇的對象，嘗試將其交換與其中一個選擇的對象，如果它提高了分數

現在你應該有一個相當不錯的候選人修剪。

然後做一個詳盡的搜索，並停止每當它比這個候選人更糟糕。

注意：步驟1-3是從快速凸包算法中獲得的靈感。