Я читал несколько статей о алгоритмах многократного разбиения структур графов. Я особенно заинтересован в этой работе, которая предлагает алгоритм для решения проблемы многократного использования:
https://www.cv -foundation.org / OpenAccess / content_iccv_2015 / документы / Keuper_Efficient_Decomposition_of_ICCV_2015_paper.pdf
Что касается пограничных расходов, то в нем говорится:
... для любой пары
узлов, реальная стоимость (награда) для всех разложений
для которых эти узлы находятся в отдельных компонентах
Достаточно справедливо. Кроме того, в нем говорится, что решением проблемы мультисрезов является простой двоичный вектор длины, равный числу ребер в графе, в котором «1» указывает, что соответствующее ребро разделяет две вершины, принадлежащие различным компонентам графа:
для каждого ребра vw ∈ E ∪ F, y (v, w) = 1 тогда и только тогда, когда v и w
находятся в различных компонентах G.
Но тогда задача оптимизации записывается в виде:
Кажется, это не имеет смысла. Если веса ребер отображают награды для узлов, соединяющих ребра в отдельных компонентах, разве это не должно быть проблемой максимизации? И в любом случае, если все веса ребер положительны, не приведет ли это к тривиальному решению, где y является вектором из всех нулей? Приведенное выше выражение сопровождается некоторыми ограничениями в статье, но я не мог понять, как какие-либо из них препятствуют этому результату.
Более того, когда он позже пытается сгенерировать исходное решение, используя Greedy Additive Edge Contraction, он говорит:
Alg. 1 начинается с разложения на
отдельные узлы. На каждой итерации объединяется пара соседних компонентов, для которых объединение уменьшает цель
значение максимально. Если нет соединения строго уменьшает цель
значение, алгоритм завершается.
Опять же, если веса ребер являются наградами за разделение узлов, разве объединение двух узлов не уменьшит вознаграждение? И даже если я на секунду предположу, что веса ребер являются штрафами за разделение узлов, разве этот метод просто не объединит все узлы в один компонент?
Единственный способ увидеть, как это сработает, - это если вес ребер представляет собой сбалансированную комбинацию положительных и отрицательных значений, но я почти уверен, что что-то упустил, потому что это ограничение нигде не упоминается в литературе.