Разбиение взвешенного графа на одинаково взвешенные группы

Question

У меня есть двунаправленный граф с взвешенными ребрами и взвешенными вершинами. Я хочу найти N групп непересекающихся, связанных вершин, чтобы:

1. Суммированные веса каждой группы близки к определенному значению, но не превышают его. TargetWeight
2. вес выбранных ребер для формирования этих групп настолько низок, насколько это возможно. Один улов здесь: вес ребра может уменьшиться, если выбрать другое ребро (часть веса распределяется между ребрами). Один пример: ребро E1 имеет вес 20, ребро E2 имеет вес 30, они делят вес 5. Взяв только E1, вы получите вес 20, взяв E1 и E2, вы получите общий вес 45 (общий вес взят только на счет один раз).

N известно заранее, но разрешено быть больше, если результаты значительно улучшатся.
TargetWeight известен заранее, и нет реальной доступной метрики, когда несколько небольших групп с низкой стоимостью лучше, чем большая группа с высокой стоимостью.

Граф имеет около 50 тыс. Узлов в типичном случае. График не хранится в базе данных.

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

Answer 1

Я думаю, что лучший способ справиться с такой проблемой:

• Во-первых: определите функцию стоимости исходя из двух критериев:

  Стоимость (график) = SUM(Расстояние (subgraphweight,TargetWeight)) + SUM(WeightEdges(подграф)), где расстояние (x,y) очень большое, если x>y, и равно yx в противном случае

• Второе: разбить граф случайным образом на N(или более) групп непересекающегося подграфа.

• третье: пройтись по графику и переместить одну вершину из одной группы в другую и проверить, уменьшится ли общая стоимость