Сортировка точек таким образом, чтобы минимальное евклидово расстояние между последовательными точками было бы максимальным - PullRequest
Новая
       14

Сортировка точек таким образом, чтобы минимальное евклидово расстояние между последовательными точками было бы максимальным

5 голосов
/ 11 октября 2011

Учитывая набор точек в трехмерном декартовом пространстве, я ищу алгоритм, который будет сортировать эти точки так, чтобы евклидово расстояние минимальное между двумя последовательными точками было бы максимальным.

Было бы также полезно, если бы алгоритм имел тенденцию максимизировать среднее евклидово расстояние между последовательными точками.

Редактировать:

Я имеюперекрестился на https://cstheory.stackexchange.com/ и получил хороший ответ.Смотри https://cstheory.stackexchange.com/questions/8609/sorting-points-such-that-the-minimal-euclidean-distance-between-consecutive-poin.

Ответы [ 2 ]

3 голосов
/ 12 октября 2011

Вот нижняя граница стоимости решения, которая может служить строительным блоком для ветвления и привязки или более ненадежного алгоритма неполного поиска:

Отсортируйте расстояния между точками и рассмотрите их вне возрастающий порядок.Используйте http://en.wikipedia.org/wiki/Disjoint-set_data_structure для отслеживания наборов точек, объединяя два набора при соединении связью между двумя точками.Длина кратчайшего расстояния, с которым вы сталкиваетесь до точки, когда вы объединяете все точки в один набор, является верхней границей минимального расстояния в идеальном решении, потому что идеальное решение также объединяет все точки в одну.Однако ваша верхняя граница может быть длиннее минимального расстояния для идеального решения, потому что соединяемые вами ссылки, вероятно, образуют дерево, а не путь.

1 голос
/ 12 октября 2011

Вы можете смоделировать вашу проблему с помощью графика, провести линию между вашими точками, теперь у вас есть полный график, теперь ваша проблема - найти самый длинный путь на этом графике, который является NP-Hard, см. Вики для самый длинный путь .

На самом деле я ответил на вторую часть проблемы: максимизировать среднее, что означает максимизировать путь, идущий от каждого узла графа, если вы взвесите их как 1 / расстояние, это будет проблемой коммивояжера (минимизировать длину пути) и является NP-Hard. и для этого случая может быть полезно увидеть метрическое приближение TSP .

...