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

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

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

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

Моя текущая попытка состоит в том, чтобы просто сделать пару случайных размещений, а затем вычислить среднюю длину пути между парами K и L, но этот расчет начинает занимать много времени, поэтому я бы не стал тратить так много времени на просто оценивая случайно выбранные комбинации. Я лучше один раз потрачу время на получение НАСТОЯЩЕЙ наиболее распространенной комбинации.

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


java graph cluster-computing algorithm maximize
person user134589    schedule 23.04.2015    source источник
comment
Я голосую за то, чтобы закрыть этот вопрос как не по теме, потому что это вопрос о математическом / геометрическом алгоритме, и он должен быть на математическом форуме.   -  person ControlAltDel    schedule 23.04.2015
comment
это будут просто разные теги или есть другой раздел этого сайта, с которым я не знаком?   -  person user134589    schedule 23.04.2015
comment
math.stackexchange.com для математических вопросов. Вопрос в том, если у вас есть алгоритм, который вы не знаете, как реализовать, или если вы хотите понять, какой алгоритм может решить эту проблему?   -  person Asthor    schedule 23.04.2015
comment
Это вопрос об алгоритме, который на самом деле не находится в центре внимания Mathematics SE. Есть компьютерная наука SE, которая бы подошла, но здесь все в порядке. Тег algorithm содержит более 50 000 вопросов.   -  person j_random_hacker    schedule 23.04.2015
comment
Может быть, вы сможете адаптировать пружинный алгоритм, который используется для построения графиков на евклидовой плоскости.   -  person biziclop    schedule 23.04.2015
comment
@j_random_hacker Я согласен, мне не нравится (недавняя?) тенденция, что любой вопрос глубже, чем какую кнопку я нажимаю, чтобы получить шарик? признан не относящимся к теме и подходящим только для знатоков математики.   -  person biziclop    schedule 23.04.2015
comment
@biziclop Это не недавно, но стало намного хуже, когда биржа CS начала лоббировать, чтобы вопросы об алгоритмах здесь не по теме.   -  person David Eisenstat    schedule 23.04.2015
comment
Объясняя свое голосование, я не щелкнул этот вопрос, я просто предположил, что вы можете найти лучшие ответы на другом форуме, который более тесно связан с вашим вопросом. Если вас устраивает NP-жесткий ответ, то хорошо. Но я бы предположил, что могут быть другие решения, о которых люди здесь не знают.   -  person ControlAltDel    schedule 23.04.2015

Ответы (1)


arrow_upward
5
arrow_downward

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

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

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

person David Eisenstat    schedule 23.04.2015
comment
Филиал и привязка к тысячам узлов? Сомневаюсь... Да и сокращение от клики/биклики тоже не сложно. - person Evgeny Kluev; 23.04.2015
comment
@EvgenyKluev Я запускал Bron-Kerbosch с тысячами узлов. Почему бы и нет? - person David Eisenstat; 23.04.2015
comment
@DavidEisenstat: я сделал ошибку. Я удалю свой комментарий. - person j_random_hacker; 23.04.2015