劃分成最大距離集

Question

我有一個GPS點的列表...但我要求什麼也可以適用於任何X，Y座標。

在我的用例中，我想分配集中的點。每個點只能屬於一個集合，並且每個集合都有一個條件，即集合中任意兩點之間的距離不大於某個常數......也就是說，該集合中的所有點都適合具有特定直徑的圓。

有關點列表，我想找到最少（或至少某些）安排，其中有最少數量的集合。

將有套只是一個單一的點，因爲其他的點周圍已經在不同的集合或僅僅是因爲周圍有沒有點（他們之間的距離大於設定的條件高）......我想要什麼避免是低效的集合賦值，例如而不是找到理想的2套，每個有30個點，我找到5套，一個1點，第二個40點，等等...

所有我能夠是一個蠻力的解決方案，計算所有距離，建立所有可能的佈置安排，按套數排序並選擇最少數量的套。

有沒有更好的方法？

Answer 1

這裏的問題是NP完全。你試圖解決的是最大集合問題和一個集合覆蓋問題。

你的問題可以表示爲一個圖G =（V，E），其中頂點是你的座標和邊緣連接的距離。這個圖可以在O（n^2）時間內完成。然後過濾掉所有的邊緣，距離大於圖G'的常量。

用剩下的圖G'你想找到所有派系（有效地解決最大派系）。一個派系是一組完整的頂點。將這個列表命名爲S.

現在找到覆蓋所有頂點V的S的最小元素集合就是集合覆蓋問題。

集覆蓋問題和最大集合都是NP完整的。因此尋找最佳解決方案將花費指數時間。你可以看看這兩個問題的近似算法。