排序點使得連續點之間的最小歐幾里德距離將最大化

Question

給定3D笛卡爾空間中的一組點，我正在尋找一種算法來對這些點進行排序，使得兩個歐幾里德距離連續的點將被最大化。

如果算法傾向於最大化連續點之間的歐幾里德距離，那麼也是有益的。

編輯：

我crossposted上https://cstheory.stackexchange.com/並得到了一個很好的答案。見https://cstheory.stackexchange.com/questions/8609/sorting-points-such-that-the-minimal-euclidean-distance-between-consecutive-poin。

Answer 1

你可以通過圖形來模擬你的問題，在你的點之間劃線，現在你有一個完整的圖，現在你的問題是在這張圖中找到最長的路徑，這是NP-Hard，請參見wiki的longest path。

事實上，我回答了第二部分問題，即最大化平均值，這意味着最大化從圖的每個節點開始的路徑，如果將它們加權爲1 /距離，它將成爲旅行推銷員問題（最小化路徑長度）並且是NP-Hard。對於這種情況可能是有用的，看Metric TSP approximation。

Answer 2

下面是解決方案的成本，這可能會成爲一個構建塊分支定界或更不可靠的不完整的搜索算法的下界：

排序點之間的距離，並考慮他們在非 - 增加訂單。使用http://en.wikipedia.org/wiki/Disjoint-set_data_structure來跟蹤點集合，通過兩點之間的鏈接連接時合併兩個集合。在將所有點合併到一個集合中時，遇到的最短距離的長度是完美解決方案中最小距離的上限，因爲完美的解決方案也會將所有點合併爲一個點。然而，您的上限可能比完美解決方案的最小距離更長，因爲您加入的鏈接可能會形成一棵樹，而不是一條路徑。