Найти биекцию, которая лучше всего сохраняет расстояния

Question

У меня есть два пробела (не обязательно равных по размеру) с N точками. Я пытаюсь найти биекцию (спаривание) точек, чтобы расстояния сохранялись как можно лучше.

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

Answer 1

Я полагаю, что вы ищете алгоритм многомерного масштабирования , где вы минимизируете общее изменение расстояния. К сожалению, у меня очень мало опыта в этой области, и я не могу вам помочь.

Answer 2

Я не слышал о точно такой же проблеме.Существует два похожих типа задач:

1. Нелинейное уменьшение размерности, вам дано N точек высокой размерности, и вы хотите найти N точек низкой размерности, которые максимально сохраняют расстояние.MDS, упомянутый Майклом Ковалом, является одним из таких методов.
2. Это может быть более многообещающим: алгоритмы для задачи присваивания.Например, Kuhn-Munkres (венгерский алгоритм), вам дается матрица NxN, которая кодирует стоимость соответствия pi с pj, и вы хотите найти минимальную биекцию стоимости.Существует много обобщений этой проблемы, например, b-сопоставление (Kuhn-Munkres решает 1-сопоставление).

В зависимости от того, как вы определяете «сохраняет расстояния как можно лучше», я думаю, что вы хотите либо (2), либо обобщение (2) таким образом, что стоимость зависит не только отдве совпадающие точки, но присвоение всех остальных точек.

Наконец, Кун-Мункрес встречается повсюду в исследовании операций.