Оптимальные пары самых дальних точек

Question

У меня есть четный набор точек в 2D. Мне нужен алгоритм, который может сделать пары таких точек, чтобы общая сумма расстояния между парами была максимальной.

Я думаю, что динамическое программирование, жадный подход не сработает. Могу ли я использовать линейное программирование или венгерский алгоритм? или любой другой?

Answer 1

Вы, конечно, можете использовать целочисленное линейное программирование. Вот пример формулировки:

Введите бинарную переменную x[ij] за каждую неупорядоченную пару разрозненных точек i а также j (т.е. такие как i<j), где x[ij]=1 если бы точки i а также j сгруппированы вместе.

Вычислить все расстояния d[ij] (за i<j).

Цель состоит в том, чтобы максимизировать sum_[i<j] d[ij]*x[ij]с учетом ограничений, что каждая точка находится в одной паре, т.е. forall j, sum_[i<j] x[ij] = 1,

Обратите внимание, что это работает и для 3d-точек: вам нужно только расстояние между двумя парами точек.