Самая маленькая сумма пар

Похоже, вы ищете Идеальное соответствие с минимальным весом .

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

По запросу, вот краткое описание «простого» алгоритма минимально взвешенного идеального соответствия в графе. Это краткое изложение частей главы о взвешенном сопоставлении в книге Пападимитриу и Стейглица Комбинаторная оптимизация, алгоритмы и сложность .

Допустим, вам дан взвешенный неориентированный граф 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, если это не так.

Теперь задачу сопоставления можно записать как задачу линейного программирования:

минимизировать Sum c (i, j) * x (i, j)

при условии, что

Sum x (1, j) = 1 , где j изменяется от 1 до n.

Sum x (2, j) = 1 , где j изменяется от 1 до n. . . .

Sum x (n, j) = 1 , где j изменяется от 1 до n.

(Сумма 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)

Sum x (i, j) + y (r) = s (r) для i, j в S (r).

Затем Эдмондс доказал, что этого достаточно, чтобы гарантировать, что каждый x (i, j) равен 0 или 1, что дает нам идеальное соответствие с минимальным весом.

К сожалению, теперь количество переменных стало экспоненциальным. Таким образом, симплексный алгоритм, если просто запустить его как есть, приведет к алгоритму экспоненциального времени.

Чтобы обойти это, Эдмондс рассматривает двойственную задачу линейного программирования (здесь я не буду вдаваться в подробности) и показывает, что первично-дуальный алгоритм при запуске на двойном алгоритме требует только O (n ^ 4) шагов для достичь решения, тем самым дав нам алгоритм с полиномиальным временем! Он показывает это, показывая, что не более O (n) из y (r) не равны нулю на любом этапе алгоритма (который он называет расцветом).

Вот ссылка, которая объясняет это более подробно: http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/papers/blossom5.pdf , Раздел 2.

Книгу, о которой я упоминал ранее, стоит прочитать (хотя она может быть немного сухой), чтобы получить более глубокое понимание.

Уф. Надеюсь, это поможет!