2

这是建立在上一个问题Solve a simple packing combination with dependencies 的基础上的，尽管无需查看该问题即可理解这一问题。

这个问题询问计算部分有序集合的线性扩展数量的最快方法。

在给定对象的任意顺序的情况下，可以将这种部分排序的列表可视化为打包配置的可行性。问题是，如果块一旦放置就不能移动，那么交给你的所有块的可能顺序是什么，以实现所示的包装配置？

在此处输入图像描述

在这个例子中，所有的块 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

我的问题是，是否有任何方法可以在不失一般性的情况下进一步优化 גלעד ברקן 的算法？如果依赖项稀缺并且列表可以进一步分解为独立的子列表，我可能会使其更快，但对于这个特定示例，情况并非如此。

4

0 回答 0