Нужна помощь в понимании этой проблемы о максимизации подключения графа - PullRequest
3 голосов
/ 11 мая 2010

Мне было интересно, может ли кто-нибудь помочь мне понять эту проблему. Я подготовил небольшую диаграмму, потому что это намного проще объяснить визуально.

альтернативный текст http://img179.imageshack.us/img179/4315/pon.jpg

Проблема, которую я пытаюсь решить:

1. Построение графика зависимости Учитывая связность графа и метрики, которая определяет, насколько хорошо узел зависит от другого, упорядочите зависимости. Например, я мог бы добавить несколько правил, гласящих, что

  • узел 3 зависит от узла 4
  • узел 2 зависит от узла 3
  • узел 3 зависит от узла 5

Но поскольку последнее правило не является «ценным» (опять же на основе той же метрики), я не буду добавлять правило в свою систему.

2. Оформить заявку на заказ После того, как я построил граф зависимостей, выполните список в порядке, который максимизирует окончательное соединение. Я не уверен, действительно ли это проблема, но у меня почему-то возникает ощущение, что может существовать более одного заказа, и в этом случае требуется выбрать лучший заказ.

Прежде всего, мне интересно, правильно ли я сконструировал проблему и должен ли я знать о каких-либо угловых случаях. Во-вторых, есть ли тесно связанный алгоритм, на который я могу посмотреть? В настоящее время я думаю о чем-то вроде Набор дуги обратной связи или Секретарская проблема , но сейчас я немного запутался. Есть предложения?

PS: Я сам немного озадачен этой проблемой, поэтому, пожалуйста, не обращайте на меня внимания. Если понадобятся какие-либо разъяснения, я постараюсь обновить вопрос.

Ответы [ 3 ]

2 голосов
/ 11 мая 2010

Похоже, вы пытаетесь определить порядок запросов, отправляемых на узлы с зависимостями (или "частичным порядком" для google) между узлами.

Если вы используете Google «график зависимости частичного заказа», вы получите ссылку на здесь , которая должна дать вам достаточно информации, чтобы найти хорошее решение.

Как правило, вы хотите отсортировать узлы таким образом, чтобы узлы следовали за их зависимостями; АКА топологическая сортировка.

1 голос
/ 11 мая 2010

Если вы заранее знаете зависимости каждого узла, вы можете легко создавать слои.

Забавно, но я столкнулся с той же проблемой при организации ... компиляции различных модулей моего приложения:)

Идея проста:

def buildLayers(nodes):
  layers = []
  n = nodes[:] # copy the list
  while not len(n) == 0:
    layer = _buildRec(layers, n)

    if len(layer) == 0: raise RuntimeError('Cyclic Dependency')

    for l in layer: n.remove(l)
    layers.append(layer)
  return layers

def _buildRec(layers, nodes):
  """Build the next layer by selecting nodes whose dependencies
     already appear in `layers`
  """
  result = []
  for n in nodes:
    if n.dependencies in flatten(layers): result.append(n) # not truly python
  return result

Затем вы можете открывать слои по одному, и каждый раз вы сможете отправлять запрос на каждый из узлов этого слоя параллельно.

Если вы сохраняете набор уже выбранных узлов и зависимости также представлены в виде набора, проверка будет более эффективной. Другие реализации будут использовать распространение событий, чтобы избежать всех этих вложенных циклов ...

Обратите внимание, что в худшем случае у вас есть O (n 3 ), но у меня было только около тридцати компонентов, и ТАК не связано: p

1 голос
/ 11 мая 2010

Я немного сбит с толку вашими порядками ограничений по сравнению с графиками, которые вы изображаете: ничего не совпадает. Тем не менее, звучит так, как будто у вас есть мягкие ограничения порядка (A должен предшествовать B, но не обязательно) с затратами за нарушение ограничения. Оптимальный алгоритм планирования, который NP-hard , но я уверен, что вы могли бы получить довольно хорошее расписание, используя DFS, смещенную в сторону ребер большого веса, а затем удалив все задние ребра.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...