Подключите узлы, чтобы увеличить общий вес края

Ответ 1

Вы можете преобразовать это в проблему поиска идеального соответствия максимальной стоимости, которая может быть решена в полиномиальное время (например, с использованием варианта алгоритма Blossom)

Преобразование состоит в разбиении каждого node степени d на d левых узлов и d-4 правых узлов.

Для каждой пары вершин u, v в исходном графе добавьте ребро между несвязной вершиной u left node и несвязную вершину v слева node веса, эквивалентную прибыли присоединения u и v.

Затем добавьте дополнительные ребра (веса 0) между каждой парой левого и правого узлов (для одной и той же вершины).

Теперь построим максимальное совпадение веса в этом новом графе.

Дело в том, что дополнительные ребра используют все, кроме 4 левых узлов. Это означает, что каждая вершина может получать прибыль только от 4 прибыльных ребер.

Пример

Предположим, что у нас есть проблема с 7 цветными узлами. Я нарисовал раздел расширенного графика, который соответствует части для одного зеленого node и одного красного node.

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

Ответ 2

Вот формулировка линейного программирования для этой задачи: назначьте переменную для каждой пары цветов, присутствующей в таблице "прибыль" (до требуемых переменных c * (c + 1)/2, где c - количество цветов), используйте c ограничений, определяемых ограничением "4 ребра на node" и одним ограничением для каждой переменной, чтобы ограничить количество возможных ребер (за исключением случаев, когда для каждого из краев края или 5 узлов для одноцветных ребер имеется не менее 4 узлов) и максимизировать сумму переменных * условий прибыли.

Решатель LP может найти все-целочисленные переменные для этой проблемы (если повезет). Или могут быть решения с дробными переменными, см. Приведенный ниже контрпример.

Когда мы получаем решение LP (где каждая переменная представляет количество ребер для некоторой комбинации цветов), мы должны фактически добавить ребра к графу. Используйте некоторую стратегию, чтобы избежать циклов и дубликатов ребер (например, "выбрать наименее подключенный node" из узлов одного цвета).

Контрпример: 5 красных, 4 зеленых, несколько синих узлов, прибыль 100 для красно-зеленых краев, 10 для красно-красного, 1 для красно-синих. LP-решение дает 20 красно-зеленых краев (правильно), 2,5 красно-красных края (должно быть 2) и нулевые красно-синие края (должно быть 1).

Исправить. Целочисленное линейное программирование - правильный подход к этой проблеме. Для до 50 цветов нам потребуется до 1275 переменных. Это должно быть относительно простой задачей для достойного решения ILP.

Ответ 3

Это похоже на проблему 0-1 Knapsack, где максимум вычисляется, если предмет либо помещен в рюкзак, либо не помещен в рюкзак. Вот пример:

def knapsack(numItems, capacity, sizes, values):
  # if no more items left to put in knapsack or knapsack is full
  if (numItems == 0 or capacity == 0):
    return 0

  # if can't fit item into knapsack, try the next item
  if (sizes[numItems-1] > capacity):
    knapsack(numItems-1, capacity, sizes, values)

  # find the max of including or not including item in knapsack
  return max(
    values[values-1] + knapsack(numItems-1,capacity - weights[numitems-1], sizes, values),
    knapsack(numItems-1, capacity, sizes, values))

Здесь вы ищете максимум, когда node либо подключен к другому node, либо нет. Когда подключен node, значение, которое получается, зависит от цвета node. Код будет выглядеть примерно так:

def ConnectNodes(numItems, capacity, sizes, values, nodeColor):
  # if no more items left to connect or capacity is full
  if (numItems == 0 or capacity == 0):
    return 0

  # if can't fit item into knapsack, try the next item
  if (sizes[numItems-1] > capacity):
    ConnectNodes(numItems-1, capacity, sizes, values, nodeColor)

  # find the max of connecting or not connecting node
  return max(
    RulesForProfit(numItems-1, nodeColor) + ConnectNodes(numItems-1,capacity - weights[numitems-1], sizes, values, nodeColor),
    ConnectNodes(numItems-1, capacity, sizes, values, nodeColor))

Ответ 4

Думали ли вы о жадном подходе? Для всех цветов и соответствующих значений colorA- > colorB, если для каждого цветного края вы будете делать

edge_color  :  sort_in_descending_order(edge_color_To_color_Prices)
example:
    red: red->black  30
         red->white  20
         red->yellow 10
    black: black->green 15
           black->grey 10

итерации, пока не будет места для нового края (4 на node) и возьмите самое большое возможное значение края (отметьте его как посещенный, а затем он поможет вам последним) (я предполагаю вы можете связать nodeA с nodeB только один раз). Мы можем предположить, что ребро не направлено от того, что вы сказали. В каждом node вам необходимо сохранить эти выбранные значения, поэтому, когда вы повторяете следующий край, который вы уже использовали, вы должны знать о выбранных ребрах (черный node должен знать красный = черный выбор 30 красным)

red: 1st edge: red->black 30 -> stores that in black node list as 
[red,30]
     2nd edge: ...........20 ->...
     3rd edge: ...........10
     4th edge: ...........5
     ---------------------------
     5th edge: ...........4   (after update from black it will be 4th 
edge)
black: 1st edge: black->white   50  > [red,30] 
       2nd edge: .............. 40
       3rd edge: .............. 35
       4th edge: .............. 34
       ---------------------------
       5th edge  .............. 30 (this is our red->black edge)

замените на (black- > white 50) и перейдите к красному node, чтобы обновить его с помощью следующего max (потому что мы только что удалили red- > black 30 с помощью black- > white 50 - мы заменим его, только если мы достигли предела краев в черном node, следуя критерию минимального значения - мы удаляем/заменяем край наименьшего ценового диапазона из черного node)

Это должно работать

Ответ 5

Просто идея, у нее не было много времени, чтобы проверить ее.
Как начинать с взвешенного графа G = (V, E), где V - ваш набор узлов, а вес E - прибыль от вашей таблицы. Пусть O - пустое множество, которое будет нашим выходом.

Затем используйте алгоритм сопоставления (алгоритм Blossom) на G. Добавьте эти ребра в O.

Повторите алгоритм с вводом G '= (V, E\O). Снова добавьте эти ребра в O.

Повторите еще два раза. Возврат O.

Продолжительность:
Время работы алгоритма Blossom равно O (E * V ^ (1/2)) согласно википедии. Поскольку алгоритм используется в 4 раза, общее время работы также будет O (E * V ^ (1/2)).