Выбирайте самые дальние k точек из заданных n точек

Question

У меня есть набор S n точки в размерах d, для которых я могу рассчитать все попарные расстояния, если потребуется. Мне нужно выбрать k точек в этом наборе, чтобы сумма их попарных расстояний была максимальной. В других, несколько более математических словах я хочу, чтобы p1, ..., pk в S, что сумма (i, j < k) dist (pi, pj) максимальна.

Я знаю, что этот вопрос связан с this one (который в основном такой же, как у меня, но для k = 2) и, возможно, до this one (с «самым дальним», а не «ближайшим»).

Я не слишком уверен в этом, но, возможно, все возможные решения имеют все свои точки в выпуклой оболочке?

Любое разумное приближение/эвристика в порядке.

Виртуальная бонусная точка № 1 для решения, которое работает для любой функции, которая дает оценку из четырех точек (один из которых может быть квадратным корнем из суммы квадратов расстояний).

Виртуальная бонусная точка №2, если решение легко реализовано в python + numpy/scipy.

Answer 1

Ваша проблема была похожа на weighted minimum vertex cover problem (которая NP-полная). Спасибо @Gareth Rees за комментарии ниже, поясняющие, что я был неверен в понимании отношения вершинной обложки к набору, который вы ищете. Но вы все еще можете исследовать проблему с крышкой вершин и литературу, потому что ваша проблема может обсуждаться вместе с ней, поскольку они все еще имеют некоторые функции.

Если вы хотите работать с диаметром вместо взвешенного веса графа, вы можете использовать подход для набора минимального диаметра, который вы связали в своем вопросе. Если ваша текущая дистанционная мера называется d (той, для которой вы хотите, чтобы точки были наиболее удалены друг от друга), просто укажите d' = 1/d и разрешите проблему с минимальным расстоянием с d'.

Также может быть взаимосвязь между алгоритмом обработки графа какой-либо формы, например, normalized cut и подмножеством, которое вы ищете. Если ваша дистанционная мера используется в качестве веса графа или сродства между узлами, вы можете изменить существующую целевую функцию резания графика, чтобы она соответствовала вашей целевой функции (поиск группы из k узлов с максимальным суммарным весом).

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

Для температурного режима вам потребуется хороший график охлаждения, и, возможно, потребуется использовать повторный нагрев в зависимости от стоимости. Но такого рода это очень просто программировать. До тех пор, пока n достаточно мал, вы можете просто беспорядочно выбирать k -подробнее и отжигать в сторону k -подвески с очень большим полным расстоянием.

Это позволит вам приблизиться, но даже детерминированные методы, вероятно, помогут решить эту проблему.

Ниже приведен первый взлом, на котором может быть смоделированный код отжига. Примечание, что я не делаю гарантий об этом.Это может быть неэффективное решение, если вычисление расстояния слишком сложно или размер экземпляра проблемы слишком велик. Я использую очень наивное геометрическое охлаждение с фиксированной скоростью охлаждения, и вы также можете захотеть возиться с более привлекательным предложением, чем просто случайным образом обмениваться узлами.

all_nodes = np.asarray(...) # Set of nodes 
all_dists = np.asarray(...) # Pairwise distances 

N = len(all_nodes) 
k = 10 # Or however many you want. 

def calculate_distance(node_subset, distances): 
    # A function you write to determine sum of distances 
    # among a particular subset of nodes.  

# Initial random subset of k elements 
shuffle = np.random.shuffle(all_nodes) 
current_subset = shuffle[0:k] 
current_outsiders = shuffle[k:] 

# Simulated annealing parameters. 
temp = 100.0 
cooling_rate = 0.95 
num_iters = 10000 

# Simulated annealing loop. 
for ii in range(num_iters): 
    proposed_subset = current_subset.copy() 
    proposed_outsiders = current_outsiders.copy() 

    index_to_swap = np.random.randint(k) 
    outsider_to_swap = np.random.randint(N - k) 

    tmp = current_subset[index_to_swap] 
    proposed_subset[index_to_swap] = current_outsiders[outsider_to_swap] 
    proposed_outsiders[outsider_to_swap] = tmp 

    potential_change = np.exp((-1.0/temp)* 
     calculate_distance(proposed_subset,all_dists)/ 
     calculate_distance(current_subset, all_dists)) 

    if potential_change > 1 or potential_change >= np.random.rand(): 
     current_subset = proposed_subset 
     current_outsiders = proposed_outsiders 

    temp = cooling_rate * temp 

Answer 2

Как насчет этого жадного алгоритма:

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

Позволяет называть наибольшее расстояние между любыми 2 точками D, для каждой добавляемой нами точки мы добавляем по крайней мере D из-за неравенства треугольника. поэтому решение будет по крайней мере (k-1) * D, тогда как любое решение будет иметь (k-1)^2 расстояния, ни один из них не превосходит D, поэтому в худшем случае вы получите решение k в разы оптимального.

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

Answer 3

Вот реализация рабочий (перебор) для малого п, что если ничего не показывает выразительность постижений генератора:

selection = max(
    itertools.combinations(points, k), 
    key=lambda candidate: sum(
     dist(p, q) for p, q in itertools.combinations(candidate, 2) 
    ) 
) 

Хотя это заканчивается вызов dist много:

(k!/2!/(k-2)!) * (n!/k!/(n-k)! == n! /(2(k-2)!(n-k)!) 

Answer 4

Шаг 1: Предкоммутировать dist (pi, pj) для всех пар pi, pj

Шаг 2: Построить полный граф V = {p1, ..., pn} с весами ребер w_ij = dist (pi, pj)

Шаг 3: Решите проблему максимальной клики с кромкой (MEC).

MEC определенно NP-complete, и он сильно связан с квадратичным программированием. Таким образом, вы можете сосредоточиться на эвристике, если n велико (или даже умеренного размера).

Обратите внимание, что, предварительно рассчитав край-папье, нет никаких ограничений на функции расстояния