Как найти лучший способ соединить разные узлы между разными объединениями? - PullRequest
Новая
       11

Как найти лучший способ соединить разные узлы между разными объединениями?

0 голосов
/ 18 мая 2018

Описание:

Существует 1000 объединений, каждый объединение содержит x узлов (x - это случайное значение от 1 до 100).Теперь мы можем создать соединение от одного узла в объединении A к другому узлу в объединении B.

Правило таково: 

1. one node only accepts just one connection. 
2. The connection must be across different unions.

Аналогичным образом, создавайте такие соединения как можно больше.

В конце может остаться несколько узлов, которые невозможно подключить из-за отсутствия других доступных узлов в других объединениях.

Например: 

Union 1: a b c
Union 2: d e
Union 3: f g h i j

Если мы выберем следующие соединения: 

U1.a <-> U2.d
U1.b <-> U2.e
U1.c <-> U3.f

Будет оставлено h i j в объединении 3.

Но если мы используем другой тип соединения: 

U1.a <-> U3.f
U1.b <-> U3.g
U1.c <-> U3.h
U2.d <-> U3.i
U2.e <-> U3.j

Тогда не останется ни одного узла.

Итак, вопрос:

Как мы можем разработать алгоритм, чтобы попытаться найти оптимальное решение, которое сделает узлы без соединения наименьшими?

Ответы [ 2 ]

0 голосов
/ 18 мая 2018

Это эквивалентно проблеме разбиения , где каждый элемент во входном мультимножестве является длиной объединения.Кроме того, эту проблему всегда можно решить с помощью простой жадной реализации, которая выполняется за время O (n).Например, рассмотрим следующий ввод: 

Union 1: a a a
Union 2: b b b b b b b b b
Union 3: c c c c c c c c c c
Union 4: d d d d d d d d d d 
Union 5: e e

Простой жадный алгоритм создает два списка вывода.Для каждого объединения (начиная с объединения, которое имеет наибольшее количество элементов), элементы объединения добавляются в более короткий список вывода.В результате получается два списка, например: 

c c c c c c c c c c b b b b b b b b b
d d d d d d d d d d a a a e e

Следующий шаг - взять некоторые элементы из конца более длинного списка и добавить их в начало более короткого списка.В этом примере два b s перемещены: 

c c c c c c c c c c b b b b b b b 
b b d d d d d d d d d d a a a e e

Так будет ли это работать всегда?Да, единственное исключение - когда один союз содержит более половины от общего количества предметов.В этом случае элементы не перемещаются из более длинного списка.

Вот пример реализации на python: 

inputList = [['a','a','a'],
            ['b','b','b','b','b','b','b','b','b'],
            ['c','c','c','c','c','c','c','c','c','c'],
            ['d','d','d','d','d','d','d','d','d','d'],
            ['e','e']]
topCount = 0
botCount = 0
topList = []
botList = []

# sort the input in descending order based on length
inputList = sorted(inputList, key=lambda x:len(x), reverse=True)

# greedy partitioning into two output lists
for itemList in inputList:
    if topCount <= botCount:
        topList += itemList
        topCount += len(itemList)
    else:
        botList += itemList
        botCount += len(itemList)

# move some elements from the end of the longer list to the beginning of the shorter list
if topList[0] != topList[-1]:
    if topCount > botCount+1:
        excess = (topCount - botCount) // 2
        botList = topList[-excess:] + botList
        topList = topList[:-excess]
    elif botCount > topCount+1:
        excess = (botCount - topCount) // 2
        topList = botList[-excess:] + topList
        botList = botList[:-excess]

print topList
print botList

Вывод: 

['c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'b', 'b', 'b', 'b', 'b', 'b', 'b']
['b', 'b', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'a', 'a', 'a', 'e', 'e']
0 голосов
/ 18 мая 2018

Это выглядит как проблема соответствия , где ваш график: 

G=(V,E), 
V = {all nodes}, 
E={(u,v) | u and v not in same union}

Это может быть решено, например, Алгоритм цветения

...