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.

graph-algorithms cg.comp-geom optimization

— Lior Kogan
źródło

Przekreślony , motywacja .

— Jukka Suomela

Brzmi jak wersja maksymalizacyjna wąskiego gardła TSP . Lub wersja wąskiego gardła najdłuższego problemu ścieżki . Czy to ma imię?

— Jukka Suomela

Poleciłbym użycie gonzalez heurystycznego k-klastrowania (chciwa strategia). nie zastanawiając się nad tym całkowicie, wydaje się, że powinno to dać przybliżenie 2?

— Suresh Venkat

Niestety, jak stwierdzono, Gonzalez nie udzieli dobrej odpowiedzi (rozważ punkty (-100,0), (99,0) i (100,0)). Jeśli na przykład zaczniemy od niewłaściwego punktu (-100,0), otrzymamy straszną odpowiedź. Nadal możliwe jest uruchomienie gonzalez z każdego punktu i wybranie najlepszej odpowiedzi.

— Suresh Venkat

Odpowiedzi:

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 znajdź medianę odległości . Utwórz niekierowany wykres, na którym każdy wierzchołek 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 , 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 o promieniu , 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 . 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.

— David Eppstein
źródło

Czy jest jakiś powód, by sądzić, że w sprawie euklidesowej nie ma PTAS?

— Jukka Suomela

Bez powodu o tym wiem. Ale zwykłe metody PTAS dla problemów projektowania sieci euklidesowej działają tylko w celu minimalizacji, a nie maksymalizacji.

— David Eppstein,

Jedynym wyjątkiem, o którym wiem, jest artykuł Chena i Har-Peleda na temat PTAS do biegów na orientację w samolocie. Jest to problem maksymalizacji.

— Chandra Chekuri

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

— László Kozma

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)

— László Kozma
źródło