Отображение набора 3D-точек в другой набор с минимальной суммой расстояний

Question

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

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

Меня интересуют как приближения, так и точные решения.

Редактировать: Хаха, да, я думаю, это похоже на домашнюю работу. На самом деле это не так. Я пишу программу, которая получает позиции большого количества автомобилей, и я пытаюсь сопоставить их с соответствующими парковочными ячейками. :)

Answer 1

Один из способов решения этой проблемы - это решение классической задачи присваивания: http://en.wikipedia.org/wiki/Assignment_problem

Вы рассматриваете точки как вершины графа, а веса ребер - это расстояние между точками. Поскольку самые быстрые алгоритмы предполагают, что вы ищете максимальное совпадение (а не минимальное, как в вашем случае), и что веса неотрицательны, вы можете переопределить веса, например:

weight(A, B) = bigNumber- distance(A,B)

, где bigNumber больше вашего самого длинного расстояния.

Очевидно, что в итоге вы получите двудольный граф. Затем вы используете один из стандартных алгоритмов для максимально взвешенного двустороннего сопоставления (множество ресурсов в Интернете, например, http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/27_matchings_notes.pdf или Википедия для обзора: http://en.wikipedia.org/wiki/Perfect_matching#Maximum_bipartite_matchings) Таким образом, вы получите О ( NM max (N, M)), где N и M - размеры ваших наборов точек.

Answer 2

От макушки головы, пространственная сортировка с последующим моделированием отжига.

Сетка пространства и сортировка наборов в пространственные ячейки.

Решите проблему O (NM) в каждой ячейке, затем в окрестностях ячейки и т. Д., Чтобы получить пробное соответствие.

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

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

Answer 3

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

• Поиск ближайшего соседа
• к D-дерево

Надеюсь, это немного поможет.