Sortowanie punktów, aby zminimalizować minimalną odległość euklidesową między kolejnymi punktami

Biorąc pod uwagę zestaw punktów w trójwymiarowej przestrzeni kartezjańskiej, szukam algorytmu, który posortuje te punkty, tak aby zminimalizować minimalną odległość euklidesową między dwoma kolejnymi punktami.

Byłoby również korzystne, gdyby algorytm miał tendencję do wyższej średniej odległości euklidesowej między kolejnymi punktami.

ETA: Wszystko poniżej znajduje się w artykule „ On the maximum scatter TSP ”, Arkin i in., SODA 1997.

Nie znam dokładnych odpowiedzi, ale oto inne podejście, które nieco różni się od sugestii Suresha dotyczącej klastrowania Gonzalez:

Załóżmy dla uproszczenia, że jest parzyste. Dla każdego wierzchołka p znajdź medianę odległości n - 1 d ( p , q ) . Utwórz niekierowany wykres, na którym każdy wierzchołek p jest połączony z innymi wierzchołkami znajdującymi się co najmniej w odległości mediany. Minimalny stopień na tym wykresie wynosi co najmniej n / 2 , więc według twierdzenia Diraca możliwe jest znalezienie cyklu hamiltonowskiego na tym wykresie.$n$$p$$n-1$$d(p,q)$$p$$n/2$

Z drugiej strony na dysku jest wierzchołków wyśrodkowanych w punkcie p o promieniu d ( p , q ) , zbyt wiele, aby utworzyć niezależny zestaw w cyklu, więc każdy cykl hamiltonowski musiałby mieć połączenie krawędzi niektóre dwa z tych wierzchołków, o długości co najwyżej 2 d ( p , q ) . Dlatego cykl hamiltonowski znaleziony przez ten algorytm jest w najgorszym przypadku 2-przybliżeniem maksymalnego cyklu wąskiego gardła.$n/2 + 1$$p$$d(p,q)$$2d(p,q)$

Działa to w dowolnej przestrzeni metrycznej i zapewnia optymalny współczynnik aproksymacji wśród algorytmów działających w dowolnej przestrzeni metrycznej. Gdyby można było uzyskać przybliżenie lepsze niż z dokładnością do współczynnika dwóch, wówczas można by dokładnie rozwiązać problemy cyklu hamiltonowskiego, zmniejszając wykres wejściowy do problemu cyklu hamiltonowskiego do przestrzeni metrycznej o odległości 2 dla każdej krawędzi wykresu i odległości 1 dla każdego braku -krawędź.

Prawdopodobnie z pewną ostrożnością można wbić to w algorytm aproksymacji ścieżek zamiast cykli.

Przesłaliśmy przedruk, który rozwiązuje to pytanie, tj. Podaje PTAS dla maksymalnego rozproszenia TSP w przypadku euklidesowej. http://arxiv.org/abs/1512.02963 (László Kozma, Tobias Mömke: PTAS dla Euclidean Maximum Scatter TSP)