У меня двунаправленный граф с взвешенными ребрами и взвешенными вершинами. Я хочу найти N групп непересекающихся, связанных вершин так, чтобы:
- Суммированные веса каждой группы близки к определенному значению, но не превышают его. TargetWeight
- вес выбранных ребер для формирования этих групп минимально возможен. Один улов здесь: вес ребра может уменьшиться, если выбрать другое ребро (часть веса делится между ребрами). Один пример: ребро E1 имеет вес 20, ребро E2 имеет вес 30, у них общий вес 5. Взятие только E1 приведет к весу 20, взятие как E1, так и E2 приведет к объединенному весу 45 (общий вес взят только один раз).
N известно заранее, но разрешено быть больше, если результаты значительно улучшатся.
TargetWeight известен заранее, и нет реальной доступной метрики, когда несколько небольших групп с низкой стоимостью лучше, чем большая группа с высокой стоимостью.
В типичном случае граф имеет около 50 тыс. Узлов. График не хранится в базе данных.
Вы можете рассматривать эту проблему как алгоритм кластеризации, но общие обсуждения кластеризации могут сильно отличаться от того, что мне нужно. Я попробовал алгоритм KMeans, но нашел результат недостаточно хорошим. Прямо сейчас я использую эвристику, основанную на исследованиях, которая проверяет, насколько хороший определенный выбор влияет на будущий выбор групп. Этот подход работает, но довольно медленный.