Непересекающиеся отрезки при минимизации совокупной длины

Question

Я хотел бы найти лучший алгоритм для решения следующей проблемы:

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

Моей первой попыткой в ​​C ++ было перестановка всех возможных состояний, поиск состояний без пересечений, а также среди состояний с минимальной общей длиной сегмента O (n!) . Но я думаю, что должен быть лучший путь.

Есть идеи? Или хорошие ключевые слова для поиска?

Answer 1

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

Answer 2

Вы можете выбрать случайное соединение, затем каждый раз удалять одно пересечение (фактически меняете соединение своих конечных точек), этот алгоритм работает и завершается за конечные шаги.может быть, вы скажете, что переключение крестиков приводит к новому кресту, независимо от того, что каждый раз, переключая один крестик, вы минимизируете общую длину своего ответа, и этот путь не может быть бесконечным (поскольку общая длина линий конечна).На самом деле работает в O (F * n ^ 2), где F= sum of all line segments * power of 10 (чтобы сделать его целым числом).Это O очень оптимистично, я думаю, если вы попробуете этот простой алгоритм, он будет работать нормально.Конечно, это вообще лучше, чем грубая сила.

Answer 3

Используйте этот алгоритм с порядком O (n ³ ) :

Венгерский алгоритм - комбинаторный алгоритм оптимизации которая решает проблему присваивания за полиномиальное время.

Как это может помочь? Ну, он найдет только минимальную совокупную длину. Но ... * * 1013

Когда общая длина минимальна, пересечения нет.

Так, как @ qq3 сказал, что ограничение пересечения является избыточным, и после удаления этого ограничения оно может уменьшить порядок с O (n!) до O (n ³ ) .

Answer 4

Похоже, вы могли бы использовать BSP-тип алгоритм.