Существует график (E, V). Для каждого ребра (i, j) существует платеж P [i, j], который может быть положительным, нулевым или отрицательным. Мы делим вершины на кластеры. Каждый раз, когда две соседние вершины v1 и v2 принадлежат к разным кластерам, мы получаем платеж P [v1, v2]. Как увеличить общий платеж? Является ли эта проблема NP-трудной?Оптимальная кластеризация
Не искать кластеров, но для разрезов.
Максимальный вес разрезанных кромок обычно называют «максимальным разрезом». Более распространенной проблемой является минимальный разрез, и есть некоторые алгоритмы кластеризации, выраженные в терминах проблемы обрезания. Отрезок также связан с потоковыми сетями.
Как отмечено в комментариях, вам необходимо указать некоторые граничные условия. Например, точки должны быть разрезаны на две метки, и разрезаются только края с разными метками.
Да, такие разрезы обычно NP-hard.
Вы ищете [мульти-Cut] (http://www.cs.cmu.edu/~anupamg/adv-approx/lecture18.pdf). –
Если никаких дополнительных ограничений (например, количество приведенных кластеров не должно выполняться данным M), что мешает мне перебирать по краям и разрезать все положительные платежи? Правда, это может привести к еще непрерывному графику (без разбиения на разделы), но, поскольку проблема не налагает никаких ограничений, единственный кластер в качестве результата является приемлемым, не так ли? –
@Adrian Colomitchi Мы не можем произвольно разрезать некоторые ребра и не вырезать других. Мы можем только обрезать ребра из разных кластеров. Если мы разрезаем A-B, но не режем B-C, мы также сокращаем A-C. – user31264