Наименьшая сумма пар

Ответ 1

Кажется, что вы ищете Минимальный вес идеального соответствия.

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

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

Скажем, вам дан взвешенный неориентированный граф G (с четным числом узлов). Граф можно рассматривать как полный взвешенный граф, добавляя недостающие края и присваивая им очень большие веса.

Предположим, что вершины помечены от 1 до n, а вес ребра между вершинами я и j равен c (i, j).

Мы имеем n (n-1)/2 переменных x (i, j), которые обозначают сопоставление G. x (i, j) = 1, если ребро между я и 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.

(Сумма x (1, j) = 1 в основном означает, что мы выбираем ровно одно ребро, инцидентное вершине, помеченной 1).

И последнее условие, что

x (i, j) >= 0

(мы могли бы сказать x (i, j) = 0 или 1, но это не сделало бы это проблемой линейного программирования, так как ограничения являются либо линейными уравнениями, либо неравенствами)

Существует метод, называемый методом Simplex, который может решить эту задачу линейного программирования, чтобы дать оптимальное решение в полиномиальное время по числу переменных.

Теперь, если 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, что дает нам идеальное соответствие минимального веса.

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

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

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

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

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

Ответ 2

В вашей окончательной сумме в основном будет доминировать самая большая сумма. Простейший алгоритм использования этого может быть таким (я не могу это доказать):

• сортировать точки, спускающиеся по их ближайшему соседству.
• сформировать пару первой записи и ее ближайшего соседа
• удалить пару из списка
• если список не пуст. goto 1.

Это должно работать очень часто.

Поскольку вы по существу ищете алгоритм кластеризации для кластеров 2 эту ссылку или поиск алгоритмы кластеризации для реконструкции струй могут быть интересными. Люди в экспериментальном сообществе физики частиц работают над эвристическими алгоритмами для таких проблем.

Ответ 3

После некоторого времени поиска я нашел несколько других ссылок на алгоритмы минимального веса, идеально подходящие, которые могут быть проще понять (по крайней мере, проще в определенной степени).

ИЗМЕНИТЬ

Здесь я нашел реализацию python одного из этих алгоритмов. Он имеет 837 строк кода (+ некоторые дополнительные модульные тесты), и я не пробовал это самостоятельно. Но, возможно, вы можете использовать его для своего случая.

Вот ссылка к алгоритму аппроксимации проблемы. Конечно, стиль статьи тоже математичен, но ИМХО гораздо легче понять, чем бумага Кука и Роха. И в его предисловии говорится, что он нацелен на то, чтобы его было проще реализовать, чем оригинальный алгоритм Эдмонда, поскольку вам не нужен решатель линейного программирования.

EDIT2:

Подумав немного о проблеме, IMHO необходимо установить A* поиск решения этой проблемы. Поисковое пространство здесь представляет собой набор "частично совпадающих" (или частично парных наборов точек). Как уже писал Морон в своих комментариях, можно ограничить поиск ситуацией, когда нет пар с пересекающимися соединительными линиями. Функция стоимости пути (для использования терминов из Википедии) представляет собой сумму расстояний от уже парных точек. Эвристическая функция h(x) может быть любой недооценкой для оставшихся расстояний, например, когда у вас есть 2M точки, которые не спарены до сих пор, возьмите сумму минимальных расстояний M между всеми оставшимися точками.

Вероятно, это будет не так эффективно, как указал алгоритм, на который указывает Морон, но я подозреваю, что это будет намного лучше, чем "грубая сила", и намного проще реализовать.