Приближенная оценка дистанционных матриц

Question

У меня есть набор из N объектов, и я хотел бы вычислить матрицу расстояний NxN.Иногда мой набор из N объектов очень большой, и я хотел бы вычислить приближение к матрице расстояний NxN, только вычисляя подмножество сравнений расстояний.

Может ли кто-нибудь указать мне направление, которое вычисляет приближения для матрицы полного расстояния?У меня есть некоторые идеи, но я бы хотел не изобретать велосипед заново.

Редактировать: Пример типа алгоритма будет использовать тот факт, что, если между объектом A и объектом B очень небольшое расстояние, а между объектом B и объектом C очень небольшоемежду объектами А и С должно быть несколько короткое расстояние.

Answer 1

Честно говоря, я думаю, это зависит от того, насколько близко вы хотите, чтобы ваше приближение было, и насколько велико ваше подмножество. Если вы просто хотите получить общее представление о том, как будет выглядеть матрица, вы можете выполнить простую линейную интерполяцию для случайного подмножества (включая максимальные и минимальные узлы), получая довольно точные (tm) результаты.

Я думаю, что реальный трюк здесь заключается в вычислении эвристики (линейная, квадратичная и т. Д. Интерполяция) и размера подмножества. Вы также можете вычислить матрицы расстояний для различных подмножеств и затем интерполировать эти матрицы некоторым методом (линейный, сферический, линейный, кубический).

В зависимости от вашего исходного примера, это в значительной степени эвристический метод проб и ошибок, пока вы не скажете: «О, этого достаточно для того, что мне нужно».

Answer 2

Требуемое решение аналогично тому, что мы обычно видим на графике, вы можете использовать Кратчайший путь из всех пар , чтобы найти расстояние, вы также можете посмотреть алгоритм Джонсона

Answer 3

Ваши "объекты" находятся в сети? Если объекты находятся в сети, вы можете использовать , это или , это , что дает кратчайшие пути для всех пар. Если нет, то я думаю, что вы в значительной степени застряли на рассчитанных расстояниях n x n.

Answer 4

У меня возник тот же вопрос, и я написал для него код Python:

https://github.com/jpeterbaker/lazyDistance

README.md объясняет, как неравенство треугольника можно использовать для обновления верхних и нижних границ для каждого расстояния.

Просто запустите файл Python как скрипт для примера в 2-мерном пространстве. Построенные линии - единственные фактически рассчитанные расстояния.

В моей версии экономия времени не связана с большим количеством объектов. Как я уже писал, это алгоритм O (n ^ 4), так что это на самом деле хуже, чем просто вычисление всех расстояний, если число объектов велико. Но мой метод сэкономит время, когда у вас есть скромное количество объектов, а функция расстояния очень дорога для вычисления. Предполагается, что быстрее выполнить несколько операций O (n ^ 2), а не одно измерение расстояния.

Если n большое, вы можете найти более дешевые методы, чтобы решить, какое расстояние вычислить следующим (это не включает арифметику с n ^ 2 записями матриц границ расстояний). Вам также может не потребоваться обновлять все 2 * n ^ 2 границы каждый раз, когда этот код делает.