python - 从距原点给定距离的图中查找路径的所有组合

Question

我试图从一个与原点有给定距离的图中找到所有路径的组合。
事实上，魔兽世界（军团）的新扩展将把神器系统引入游戏。
这是一个你可以升级的功能，每个级别给你一个等级，你可以花一个点在一棵树的每个等级。
你可以在wowhead上找到每个工件的计算器，我将使用这个例子：http://legion.wowhead.com/artifact-calc/rogue/subtlety/
基本上，该计划的目标是：
“我给出一个等级，比如说7，它返回给我从图中得到的每一个路径组合，我必须花费7个点才能到达那里（即，7个唯一节点的列表）”。
当我看到计算器时，我认为把它转换成一个图形是可以解决的，所以我做了一个来帮助我通过：
Graph
在这个图上，我不得不从计算器上做一些调整，例如，每一个获得3个等级的特征都必须表示为3个相互连接的节点。
另外，对于解锁两种方法的特性，我必须将它们表示为4个节点，以“模拟”3个节点的需求。（但之后我们会看到这仍然是一个问题，它并没有真正解决问题）
然后，我试图找到一个很好的方法列出每一种可能性，所以我在网上做了很多研究，以找到处理我的问题的最佳方法。
我首先尝试使用广度优先搜索来解决这个问题，但是与每个节点的起点保持距离并没有多大帮助。
然后我试着用详尽的搜索。
我目前正在使用代码的一个改编版本：codereview@stackechange上的“从给定图形中查找所有路径”（不能发布超过2个链接）

def paths(graph, v, lmax):
    """Generate the maximal cycle-free paths with a given maximum length lmax in 
    graph starting at v. Graph must be a mapping from vertices to collections of
    neighbouring vertices.

    >>> g = {1: [2, 3], 2: [3, 4], 3: [1], 4: []}
    >>> sorted(paths(g, 1, 3))
    [[1, 2, 3], [1, 2, 4], [1, 3]]
    >>> sorted(paths(g, 3, 4))
    [[3, 1, 2, 4]]

    Credit to Gareth Rees from StackExchange for the original code.
    """
    path = [v]                  # path traversed so far
    seen = {v}                  # set of vertices in path
    def search():
        dead_end = True
        if len(seen) < lmax:
            for neighbour in graph[path[-1]]:
                if neighbour not in seen:
                    dead_end = False
                    seen.add(neighbour)
                    path.append(neighbour)
                    yield from search()
                    path.pop()
                    seen.remove(neighbour)
        if dead_end:
            yield list(path)
    yield from search()

然后我创建了一个函数来对结果进行排序，并只显示具有所需长度的结果。

def artifact(graph, maxrank, start):
    for i in range(1, maxrank+1):
        print("---------")
        print("Rank: " + str(i))
        print("---------")
        # Get all the Paths at "i" Rank
        RawPaths = sorted(paths(g, start, i), key=len)
        # Remove paths that doesn't satisfact our rank requirement and sort it
        ValidPaths = [sorted(j) for j in RawPaths if len(j) == i]
        # Remove duplicates
        UniquePaths = sorted([list(j) for j in set(map(tuple, ValidPaths))])
        # Display the Paths
        for j in range(len(UniquePaths)):
            PathString = "";
            for k in range(len(UniquePaths[j])):
                PathString += str(UniquePaths[j][k]) + " "
            print(PathString)
        print("")

从那里，我从图中构建了一部分节点的相邻节点（邻居）列表我不能发布超过2个链接，但是子图结束于之前链接的图的8/7/32/31节点。

g = {
  1: [2, 38],
  2: [1, 3],
  3: [2, 4],
  4: [3, 5],
  5: [4, 6],
  6: [5, 7, 8],
  7: [6],
  8: [6],
 31: [33],
 32: [33],
 33: [31, 32, 34],
 34: [33, 35],
 35: [34, 36],
 36: [35, 37],
 37: [36, 38],
 38: [1, 37]
}

然后我调用函数：

artifact(g, 8, 1)

但使用这个列表，我面临一个重大问题事实上，算法一直走到最后，但它没有做任何回溯，以达到想要的排名（即，经过一路1-38-37-36-35-34-33-31，它不会回到2-3-如果我有10分的话。
我可以通过在38，37，…中添加一个作为邻居2来求解这个子图。分支或38到2，3，…分支。
所以我的名单变成了：

g = {
  1: [2, 38],
  2: [1, 3, 38],
  3: [2, 4, 38],
  4: [3, 5, 38],
  5: [4, 6, 38],
  6: [5, 7, 8, 38],
  7: [6, 38],
  8: [6, 38],
 31: [2, 33],
 32: [2, 33],
 33: [2, 31, 32, 34],
 34: [2, 33, 35],
 35: [2, 34, 36],
 36: [2, 35, 37],
 37: [2, 36, 38],
 38: [1, 2, 37]
}

然后我就可以得到我想要的一切。
现在我试图将我的推理扩展到整个图表。但我失败的原因主要有两个：
-当我朝一个方向走的时候，用3个等级来表示特征的4个节点是有效的，但是如果我已经填满了整个分支，然后我试着回去，我计算第4个节点。（我仍然可以在artifact函数中创建一些东西来删除第4个节点，但我认为这不是处理它的好方法，应该找到一个聪明的方法来处理它。
-我用来链接前两个分支的技巧并不直接适用于整个图。例如，按照我所做的，我将在29个邻居中添加32个，因为当我从35岁开始时，从29岁就可以访问32个邻居但是，如果我来自28岁，并且没有在路径中添加27岁，那么通常从29岁就无法访问32岁。
然后我的路就失效了。
我不确定我能不能这样解决，我希望你能帮助我。而且，我觉得我的回溯搜索方式并不完美。
我还认为：
一到分支机构的尽头，我就会回到以前的分离状态，从那里开始探索。但既然节点已经被探索过了，就不要走另一条路而停在那里。
最后，我要用其他方法来处理我的问题，我不想特别用图来解决它。
也许有另一种方法可以有效地解决这个问题（比如一步一步地构建这个图，在节点被解锁的情况下，有一些列组需要花费并逐渐使用）。是的。
提前感谢你的帮助，并为我的英语错误道歉，我是法国人：）

Answer 1

IIUC，你有一个未加权的有向图G，你正在寻找G的所有子图H的集合，这些子图具有以下2个属性：
从给定的原点顶点到h中的每个顶点都有一条路径（这意味着h本身至少是弱连接的）
边的总数（或权重）正好是给定的k。
这里有一个简单的算法，你可以维护所有子图的集合，它们的总长度正好是i，在每次迭代中，把它们增长到所有子图的集合，它们的总长度正好是i+1：
从集合s中的一个子图开始，仅由原点顶点组成。
对于0到k的i：
不变量：S包含G的所有子图，这些子图与原点弱连接，并且总长度恰好为i。
设置S'={}。
对于S中的每个子图H：
对于每个边（u，v），u在v（h）中，v在v（h）外：
形成一个子图h'由h加上边（u，v）组成。
将h'添加到集合s'。（如果这个图h'已经在s中，则不要执行任何操作。这种情况会经常发生。这就是为什么最好使用一个适合于自动处理这一问题的s'集合的数据结构，例如哈希表或二进制搜索树。）
设置S=S'。
当算法终止时，S将包含满足上述要求1和2的所有子图在最坏的情况下，它需要m倍于输出中不同子图的数目，其中m是图中的边的数目注意，输出中可能有大量的子图——考虑n个顶点上的完整图，注意可能的子图比n中k个项的组合要多，后者已经很大了。