Количество способов пройти через частично упорядоченный набор - PullRequest
Новая
       14

Количество способов пройти через частично упорядоченный набор

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

Это основано на предыдущем вопросе Решите простую комбинацию упаковок с зависимостями , хотя нет необходимости проверять этот вопрос, чтобы понять этот.

Этот вопрос задает вопрос о самых быстрых способах подсчета количества линейных расширений частично упорядоченного множества.

Такой частично упорядоченный список может быть визуализирован как выполнимость конфигурации упаковки при произвольном упорядочении объектов. Чем эквивалентен вопрос: каково возможное упорядочение всех блоков, переданных вам для достижения показанной конфигурации упаковки, если блоки не могут быть перемещены после размещения?

enter image description here

В этом примере все блоки ABCDEFG должны быть установлены, зависимости для A, B, C, D: set {}, E: set {A, B}, F: set {B, C} G: set {C, D}.

Вы можете получить все возможности для завершения частично упорядоченного набора, проверив все перестановки из 7 блоков и посчитав число, которое соответствует зависимостям. Более быстрая альтернатива предоставлена ​​גלעד ברקן в предыдущем посте, который использовал структуру графа, которая прекращает дальнейший поиск в ветви, если зависимости не встречаются в уже исследованных узлах. 

nodes = {
  'A': {
    'neighbours': ['B','C','D','E','F','G'], 'dependency': set()},
  'B': {
    'neighbours': ['A','C','D','E','F','G'], 'dependency': set()},
  'C': {
    'neighbours': ['A','B','D','E','F','G'], 'dependency': set()},
  'D': {
    'neighbours': ['A','B','C','E','F','G'], 'dependency': set()},
  'E': {
    'neighbours': ['C','D','F','G'], 'dependency': set(['A','B'])},
  'F': {
    'neighbours': ['A','D','E','G'], 'dependency': set(['B','C'])},
  'G': {
    'neighbours': ['A','D','E','G'], 'dependency': set(['C','D'])},

}

def f(key, visited):
  if len(visited) + 1 == len(nodes):
    return 1

  if nodes[key]['dependency'] and not nodes[key]['dependency'].issubset(visited):
    return 0

  result = 0

  for neighbour in nodes[key]['neighbours']:
    if neighbour not in visited:
      _visited = visited.copy()
      _visited.add(key)
      result += f(neighbour, _visited)

  return result

print 2 * f('A', set()) + 2 * f('B', set()) # exploiting symmetry

У меня вопрос: есть ли способ дальнейшей оптимизации алгоритма גלג ברקן без потери общности? Я могу, вероятно, сделать это быстрее, если зависимости будут недостаточны, и список можно будет далее разбить на независимые подсписки, но это не относится к этому конкретному примеру.

...