我正在嘗試實施爬山算法，以根據特定條件決定從一組位置中選擇哪些位置。有多達5000個位置可供選擇。地理分散啓發式
其中一個標準是地理分散，因此我需要能夠爲我的位置的任何子集分配代表分散的值。
每個位置都有經度和緯度數據。
速度是一個問題，這就是爲什麼我需要一些啓發，估計如何分散一組特定的位置（即可能的解決方案）。
我試着在我的潛在解決方案中總結每個位置的成對距離，但是這證明太慢了。
然後，我試着在我的潛在解決方案中距所有位置中心的距離總和，事實證明這種方法更快，但效果不佳。使用這種方法將有利於少數幾個地點。
任何其他建議將不勝感激。
首先，你可以重申兩兩和數的含義嗎？我在問，因爲這聽起來是你形成了所有可能的配對，並且這將是非常不合適的。如果是這樣的話，找到第一個1）最近的鄰居，然後2）最長的路徑，那麼怎麼樣？
1）如果我記得它是正確的，你可以在小於O（n log n）的時間內做到這一點。 2）如果形成的樹木斷開連接，你也必須找到樹木之間的最短距離。由於樹木的原因，這不是一個NP完全問題，但實際上最短路徑足夠了。
在這個時刻，我懷疑我沒有正確理解你的問題，那麼geog區域出現的某種偏差怎麼樣，要麼在極端點之間平均分配，要麼以某種先驗啓發式來選擇。
您可以定義或進一步闡述分散概念嗎？
考慮三種情況：
你在所有成對距離上的總和可以很好地捕獲（1）和（2）：近似聚類的結果比大聚類要小。 （3）如何做？這裏，節點總數N的比例e很遠，平均距離爲D。其他(1-e)N節點聚集在平均距離爲d。
現在，必須考慮多少個成對連接？對於羣集節點，這種連接有((1-e)N)^2=e^2*N^2-2*e*N^2+N^2。對於遠端節點，有e^2*N^2連接。
現在，將這些值乘以平均距離。這給出了總配對平均值(d*(e^2*N^2-2*e*N^2+N^2)+D*(e^2*N^2))/N。現在，假設e很小，我們可以忽略包含e^2的條款。因此，平均值爲d*(N^2-2*e*N^2)/N。
現在，考慮你的第二個指標：每個人與平均中心點的距離。這在（1）和（2）上也很好：關閉集羣的結果小於大集羣。它如何做3？使用與上面相同的e來表示異常值的比例。現在，節點距中心點的平均距離由(d*(1-e)*N+D*e*N)/N給出。換句話說，羣集節點不再像過重那樣加權。
有沒有一種方法可以讓輕量級的計算，仍然更適當地加重羣集節點？我想是這樣。
我的建議是，你從你的列表中選擇隨機節點對，計算節間距離，然後對結果進行平均。對於（1）緊集羣，所有節點將靠近在一起，因此您繪製的所有隨機對都將接近您在計算時得到的成對平均值。對於（2），鬆散的簇，情況也是如此。對於（3），具有異常值的羣集，您更可能從羣集內抽取節點，而不是從外部抽取節點，因此異常值最終會被忽略。
隨着您增加採樣節點的數量，羣集將傾向於支配隨機採樣。我猜測這將提供不錯的準確性，而不是O(N^2)時間，而不是O(N)。
我很好奇爲什麼總結配對距離太慢。我認爲設施定位問題是戰略性的，高成本的決策問題，即需要數小時或數天才能運行的算法足以滿足多年將要修復的決策。 – raoulcousins
是的，我的問題在於，與其他因素相比，地理分散一直是三元目標，即所有其他因素相同時，選擇兩個解決方案的分散程度更高。沒有地域分散，我的實施在15秒內提供了良好的結果，我不能超過30秒。我基本上試圖找到一箇中間地帶，我可以收集甚至部分指示有關分散，而無需支付計算打擊。 – user1994232