Поиск N узлов в графе с максимальным разбросом/расстоянием от друг друга

Question

Для графика с N узлами (в тысячах) мне нужно найти узлы K, чтобы средняя длина пути между каждой парой (K1, K2) K была максимизирована , Поэтому, в основном, я хочу разместить их как можно дальше от друг друга.

Какой алгоритм я использовал бы для этого/как я мог запрограммировать это, не пробовав несколько отдельных комбинаций K?

Также как расширение: если у меня теперь есть N узлов, и мне нужно разместить в графе две группы узлов K и L так, чтобы средняя длина пути между каждой парой (L, K) была максимизирована, как бы я мог сделай это?

Моя текущая попытка состоит в том, чтобы просто сделать несколько случайных мест размещения, а затем рассчитать среднюю длину пути между парами K и L, но этот расчет начинает занимать много времени, поэтому я бы предпочел не тратить что много времени просто оценивает случайно выбранные комбинации. Я бы предпочел потратить время на получение комбинации REAL most spread.

Существуют ли какие-либо алгоритмы для этого?

Answer 1

Плохая новость заключается в том, что эта проблема NP-hard, путем сокращения от Independent Set. (Предположим, что весы единицы добавляются в новую вершину, связанную со всеми другими вершинами, тогда мы ищем коллекцию K, имеющую среднее расстояние 2.)

Если вы решили получить точное решение (и я, m не уверен, что вы не должны быть), то я бы попробовал разветвление и привязку, используя node is/не является одним из K как решение ветвления и грубой привязкой (учитывая подмножество K, найдите два узла, которые максимизировать соответствующую комбинацию расстояния между ними и расстоянием до подмножества, а затем установить привязку к соответствующему средневзвешенному значению, включающему известные расстояния между узлами).

Если конкретный алгоритм выше дросселей на тысячах графов, как говорит Евгений, он будет использовать farthest-point clustering (ссылка идет на страницу Википедии о местоположении объекта, которая описывает FPC), чтобы сократить график до управляемого размера, мы надеемся, небольшая ошибка аппроксимации.