Как переместить отрезки, чтобы устранить пересечения с минимальными движениями?
Есть ли какой-либо алгоритм или связанная работа для следующей проблемы?
Учитывая набор отрезков в 2D, как перемещать отрезки (по горизонтали или по вертикали), чтобы устранить пересечения, чтобы минимизировать общие перемещения? Пересечения в конечных точках могут быть разрешены.
1 ответ
Если вы хотите минимизировать количество движений сегмента:
Вы можете преобразовать проблему сегмента линии в задачу графа: каждый сегмент является вершиной графа, и между двумя вершинами есть ребро, если два сегмента пересекаются друг с другом. Вы хотите найти минимальное количество вершин, которые содержат хотя бы одну конечную точку всех ребер (потому что, если вы переместите все эти сегменты, пересечений больше не будет). Это проблема покрытия вершин, которая, к сожалению, сложна для NP, но существуют алгоритмы аппроксимации.