Как разделить все точки на плоскости на пары с минимальным расстоянием?

Question

[VladisslavaMin]

Есть точки на координатной плоскости. Нужен алгоритм, как разделить все точки на пары с минимальным расстоянием у всех. Пары типа A-B, B-C, C-D (в любом порядке, каждая точка должна встречать в двух парах).

Если кто-то знает такие алгоритмы, или есть свои идеи, подскажите, пожалуйста)

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

Answer 1

[Wataru]

После сведения к теории графов есть решение за O(n^3) через венгерский алгоритм (реализация) или через алгоритм посика максимального потока минимальной стоимости (Там реализация, медленнее венгерского метода. Вот решение за n^3, но код готовый я не нашел).

Сведение к задаче о назначениях

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

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

Постройте матрицу расстояний, решите на ней задачу о назначениях. Вашими искомыми парами будут пары задача-работа. Каждая вершина будет и задачей и работой. Только одна хитрость: нельзя из вершины идти в нее саму, т.е. на диаганали должны быть бесконечности или очень большие числа.

Пример

3 вершины (0, 0), (1, 0) и (0, 1).
Матрица расстояний (с 1e90 на диаганали вместо 0):
((1e90, 1, 1),
(1, 1e90, 1.414),
(1, 1.414, 1e90)).

Решение ценой 3.414 (3-ий элемент в 1-ой строке, 1-ый во 2-ой строке и 2-ой в 3-ей)
((*, *, 1),
(1, *, * ),
(*, 1.414, *)).

Это значит, что вы берете пары 1-3 2-1 3-2.