Сопоставление набора трехмерных точек с другим набором с минимальной суммой расстояний

Question

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

Одним из способов решения этой проблемы является решение классической проблемы с назначением: 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 ) Таким образом, вы закончите с алгоритмами O (NM max (N, M)), где N и M - размеры ваших наборов точек.

Answer 3

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

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

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