Вы, похоже, ищете Минимальный вес идеального соответствия .
Существуют алгоритмы, позволяющие использовать тот факт, что это точки на плоскости. Эта статья: Mincost Perfect Matching на плоскости имеет алгоритм, а также упоминает некоторые предыдущие работы над ним.
В соответствии с запросом приведено краткое описание «простого» алгоритма минимально-взвешенного идеального сопоставления в графе. Это краткое изложение частей главы о взвешенном сопоставлении в книге Комбинаторная оптимизация, алгоритмы и сложность , написанной Papadimitriou & Steiglitz.
Скажем, вам дан взвешенный неориентированный граф G (с четным числом узлов). Граф можно считать полным взвешенным графом, добавив недостающие ребра и присвоив им очень большие веса.
Предположим, что вершины помечены от 1 до n, а вес ребра между вершинами i и j равен c (i, j).
У нас есть n (n-1) / 2 переменных x (i, j), которые обозначают совпадение G. x (i, j) = 1, если ребро между i и j находится в сопоставлении, а x (i , j) = 0, если это не так.
Теперь задачу сопоставления можно записать как задачу линейного программирования:
минимизировать сумму c (i, j) * x (i, j)
при условии, что
Сумма x (1, j) = 1 , где j колеблется от 1 до n.
Сумма x (2, j) = 1 , где j находится в диапазоне от 1 до n.
,
,
.
Сумма x (n, j) = 1 , где j колеблется от 1 до n.
(Sum x (1, j) = 1 в основном означает, что мы выбираем ровно одно ребро, падающее на вершину, помеченную как 1).
И последнее условие, что
x (i, j)> = 0
(мы могли бы сказать, что x (i, j) = 0 или 1, но это не сделало бы эту проблему линейным программированием, поскольку ограничения являются либо линейными уравнениями, либо неравенствами)
Существует метод, называемый симплекс-методом, который может решить эту проблему линейного программирования, чтобы дать оптимальное решение за полиномиальное время по числу переменных.
Теперь, если G были двудольными, можно показать, что мы можем получить оптимальное решение, такое что x (i, j) = 0 или 1. Таким образом, решая эту задачу линейного программирования для двудольного графа, мы получаем множество присваиваний каждому x (i, j), каждое из которых равно 0 или 1. Теперь мы можем получить соответствие, выбрав те ребра (i, j), для которых x (i, j) = 1. Ограничения гарантируют, что оно будет соответствие с наименьшим весом.
К сожалению, это не так для общих графов (т.е. x (i, j) равно 0 или 1). Эдмондс понял, что это связано с наличием на графике странных циклов.
Таким образом, в дополнение к вышеуказанным ограничениям, Эдмондс добавил дополнительное ограничение, согласно которому в любом подмножестве вершин размером 2k + 1 (т. Е. Нечетного размера) количество совпадающих ребер не превышает k
Перечислите каждое нечетное подмножество вершин, чтобы получить список множеств S (1), S (2), ..., S (2 ^ n - n). Пусть размер S (r) равен 2 * s (r) + 1.
Тогда вышеупомянутые ограничения для каждого множества S (r)
Сумма x (i, j) + y (r) = s (r) , для i, j в S (r).
Затем Эдмондс доказал, что этого было достаточно, чтобы гарантировать, что каждый x (i, j) равен 0 или 1, что дает нам минимальный вес идеального соответствия.
К сожалению, теперь количество переменных стало экспоненциальным по размеру. Таким образом, симплексный алгоритм, если он будет работать так, как он есть, приведет к экспоненциальному алгоритму времени.
Чтобы обойти это, Эдмондс рассматривает двойственную из этой задачи линейного программирования (я не буду здесь вдаваться в подробности) и показывает, что алгоритм primal-dual при запуске на двойном алгоритме требует всего O (n ^ 4) шагов к достичь решения, что дает нам алгоритм полиномиального времени! Он показывает это, показывая, что самое большее O (n) из y (r) ненулевые на любом этапе алгоритма (который он называет расцветом).
Вот ссылка, которая должна объяснить это более подробно: http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/papers/blossom5.pdf, Раздел 2.
Книга, о которой я упоминал ранее, заслуживает прочтения (хотя она может быть немного сухой), чтобы глубже понять.
Уф. Надеюсь, это поможет!