У меня есть набор элементов с функцией расстояния между элементами, удовлетворяющими неравенству треугольника.Самый большой диаметр набора с функцией расстояния
Я хочу найти пару элементов, разделенных наибольшим расстоянием.
Есть ли какое-либо известное решение лучше, чем попытки всех пар?
Если вы измеряете расстояние от точки a до точек b, c и d, и вы обнаружите, что | ab | + | ac | < | ad |, то вы знаете, что | bc | короче, чем | ad |, и нет необходимости измерять | bc |. Поэтому не все пары должны быть проверены, чтобы найти самое длинное расстояние.
Возможный алгоритм будет:
Старт путем измерения расстояния от точки А до всех остальных точек, найти точку п, который дальше всего от а, а затем дать все пары B, X, для которых | AB | + | топор | < | an | расстояние | ab | + | ax | (потому что это их максимально возможное расстояние).
Сделайте то же самое для точки b, измеряя только те расстояния, которые еще не установлены. Проверьте, нашли ли вы новый максимум, а затем снова укажите все пары c, x, для которых | bc | + | bx | < MAX расстояние | bc | + | bx |.
Продолжайте делать это для точек c, d, ...
В лучшем случае вы можете найти самое длинное расстояние в наборе из N точек после только измерений N-1 (если | ax | в два раза пока любое другое расстояние от а). В худшем случае вам нужно будет измерить каждую пару (если кратчайшее расстояние больше половины самого длинного расстояния, или если вам не повезло в том порядке, в котором вы пробегаете точки).
Если вы хотите, чтобы уменьшить количество измерений расстояния до абсолютного минимума, и для каждого неизвестного расстояния х, у вас проверить все ранее сохраненное значение | ах | + | ау |, | Ьх | + | по |, | cx | + | cy | ... чтобы увидеть, меньше ли он текущего максимума и поэтому может использоваться как значение для | xy |, количество измерений существенно уменьшается.
Выполнение этого алгоритма на 1000 случайных точек в квадратном 2D пространстве, которое обычно требует 499 500 измерений, возвращает максимальное расстояние между 2000 и 10000 измерений (или от 0,4% до 2% от общего числа, при среднем 1%).
Это не обязательно означает, что алгоритм на практике намного быстрее, чем измерение каждого расстояния; это зависит от того, насколько дорого сравнивается измерение с комбинацией петель, дополнений и сравнений, необходимых для предотвращения измерений.
Как указал @mcdowella, этот метод становится менее эффективным по мере увеличения количества измерений пространства. Большое количество очков также имеет большое значение. В приведенной ниже таблице показано количество измерений, которые должны быть выполнены в отношении общего количества пар. Это средние значения из теста со случайно распределенными точками в «квадратном» пространстве (т. Е. Координаты во всех измерениях находятся в одном диапазоне). Как вы можете видеть, этот метод имеет наибольший смысл для геометрических задач со многими точками в 2D или 3D пространстве. Однако, если ваши данные сильно искажены каким-то образом, результаты могут быть разными.
10 points (45 pairs) 100 points (4950 pairs) 1000 points (499500 pairs)
dim measurem. % of total measurem. % of total measurem. % of total
1 16.6674 37.04 221.17 4.47 4877.97 0.98
2 22.4645 49.92 346.77 7.01 5346.78 1.07
3 27.5892 61.31 525.73 10.62 7437.16 1.49
4 31.9398 70.98 731.83 14.78 12780.02 2.56
5 35.3313 78.51 989.27 19.99 19457.84 3.90
6 38.1420 84.76 1260.89 25.47 26360.16 5.28
7 40.2296 89.40 1565.80 31.63 33221.32 6.65
8 41.6864 92.64 1859.08 37.56 44073.42 8.82
9 42.7149 94.92 2168.03 43.80 56374.36 11.29
10 43.4463 96.55 2490.69 50.32 73053.06 14.63
20 44.9789 99.95 4617.41 93.28 289978.20 58.05
30 44.9996 99.999 4936.68 99.73 460056.04 92.10
40 4949.79 99.99 496893.10 99.48
50 4949.99 99.9999 499285.80 99.96
60 499499.60 99.9999
Как и ожидалось, результаты испытаний становятся предсказуемыми в более высоких измерениях, лишь несколько процентов между выбросами, в то время как в 2D некоторых тестовых случаях требуется в 30 раз больше измерений, чем другие.
Можно ли заказать ваши элементы? – njzk2
Это звучит как вариация «ближайшей пары проблем точек», которая может быть решена в O (n log n), если элементы являются точками в двумерном пространстве, и у вас есть доступ к отдельным координатам точек. – Chronio
Отмечу, что если есть N измерений, вам нужно расстояние от N известных точек, чтобы зафиксировать положение в пространстве, поэтому, если вы знаете, где N из N + 1 точки, и вы знаете только N-1 расстояний до N + 1-го вы не можете вычислить N-е расстояние. Поэтому я был бы удивлен, найдя алгоритм для ближайшей пары точек на N + 1 точке в N измерениях, которые не вычисляли расстояния между всеми парами. – mcdowella