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

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

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

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

Любая идея? Или хорошие ключевые слова для поиска?

Ответ 1

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

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

КОГДА ОБЩАЯ ДЛИНА МИНИМАЛЬНА, НЕТ ИНТЕРСЕКЦИИ.

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