聚類不同角度的圓形區域

Question

假設我有一個圓形區域和n個在這個區域隨機部署的對象。我想從中心位置將圓圈分成K組，使同一區域中的物體被視爲同一組的成員。此外，K人被分配從圓圈中心的位置訪問K組（具體來說，一人一組）。現在，我想以這樣的方式分組，每個組的人的行進距離彼此接近。

如果對象統一部署，則非常簡單。只有將區域分成相等的角度才能獲得理想的結果。但是，對於隨機部署物體，我不能劃分圓形區域（具體地說，不能固定角度），這給出了每個組中彼此接近的每個人的行進距離。

Answer 1

正如在評論中提到的，在一個小組內找到最短路徑的子問題是NP難的。因此，總體問題是NP難。我將介紹一種動態規劃算法，它可以精確地解決問題（以指數時間）或用啓發式（在多項式時間內）逼近它。

這兩個變體都需要一個函數f(g)來評估組的行程距離。在確切的變體中，您需要解決TSP。在大致的變體中，您使用啓發式。你應該嘗試幾種啓發式方法，看看哪一種最適合。例如，對象的邊界環的面積可能是一個好的開始（加上最近的對象到中心的距離）。

實際算法如下所示：計算每個對象的角度位置並將它們相對於此位置進行排序。另外，計算到中心的距離。

現在，我們假設第一組從第一個對象開始。然後，我們希望找到最小化所有組的總和f(g)的分組。動態程序的狀態通過到目前爲止指定的組的數量和屬於第一個下一組的對象來參數化。這使得2D表。您可以輕鬆地對結果組計算f()初始化第一列：

 groups | 1   2 3 4 5 6 ... K 
next object | 
--------------+------------------------ 
    o2   | f(o1->o1) 
    o3   | f(o1->o2) 
    ...  | ... 
    on   | f(o1->on-1) 
    o1   | f(o1->on) 

然後，您填寫的後續列。對於每個條目，您必須將組比較各組上一列中，找到具有最小總和：

entry(column i, object j) = min_k (entry(i - 1, k) + f(ok->j-1)) 

其實，你不必計算整列。如果他們不允許適合K組，則可以在開始處將條目留空。例如。在第一列中，您只需要計算最多on-(K-1)，因爲您必須將K-1對象保留爲未分配狀態才能獲得有效的分組。您可以緩存f的結果以避免重複計算。

填表後，您有興趣entry(K, o1)。按照從這個條目返回到開始的路徑，您將獲得最佳分組，其中第一個分組的起始位置爲o1。在組合開始時爲第一個n-K對象執行此操作，並獲得總體最佳效果。

該算法的時間複雜度爲O(n^3 * K * T(f))其中T(f)是計算f(g)的複雜度。