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

Question

我试图从一个距离原点给定的图中找到所有路径的组合。在

事实上，魔兽世界（军团）的新扩展将在游戏中引入神器系统。
这是一个你可以升级的功能，每一级给你1个等级，你可以为树上的每个等级花费1点。
您可以在WowHead上找到每个工件的计算器，我将以这个为例：http://legion.wowhead.com/artifact-calc/rogue/subtlety/

基本上，该计划的目标是：
“我给一个秩，比方说7，它返回给我从图中得到的每一个路径组合，我花了7个点才能到达那里（即，7个唯一节点的列表）”。在

当我看到计算器时，我认为它可以通过将其转换为图形来求解，因此我制作了一个计算器来帮助我通过： Graph

在图上，我不得不从计算器上做一些调整，例如，每一个有3个等级的特征必须表示为3个相互连接的节点。 另外，对于那些解锁了2种继续方式的特性，我不得不将它们表示为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()

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

^{pr2}$

从那里，我从图中构建了一部分节点的相邻节点（邻居）列表。我不能发布超过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。。。分支或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的集合，它们具有以下两个性质：

1. 从给定的原点顶点到H中的每个顶点都有一条路径（这意味着H本身至少是弱连通的）
2. 边的总数（或权重）正好是某个给定的k

有一个简单的算法，在这里你保持所有子图的总长度正好是i，并且在每次迭代中，将它们增长到总长度正好为i+1的所有子图的集合：

1. 从集合S中的一个子图开始，仅由原点顶点组成。在
2. 对于从0到k的i：
   • 不变量：S包含G的所有子图，这些子图与原点弱连接，且总长度正好为i
   • 设置S'={}。在
   • 对于S中的每个子图H：
     • 对于u在v（H）中且v在v（H）之外的每个边（u，v）：
       • 形成一个子图H'由H加上边（u，v）组成。在
       • 将H'加到集合S'上。（如果这个图形H'已经在S'中，则不执行任何操作。这种情况经常发生。这就是为什么最好使用适合于s'的集的数据结构来自动处理这一点，例如哈希表或二进制搜索树。）
   • 设S=S’。在

当算法终止时，S将包含满足上述要求1和2的所有子图。在最坏的情况下，它需要m乘以输出中不同子图的数目，其中m是图中的边数。注意输出中可能有大量的子图，考虑到n个顶点上的完整图，注意到可能的子图比n中k个项目的组合要多，后者已经很大了。在

Answer 2

如果只想走一条路径，那么可以尝试Dijkstra's Algorithm来获取从初始节点到所有其他节点的距离。然后迭代它们，返回具有所需距离的值。在

如果您想尝试分支路径，这可能会变得更加困难。我的直觉是在其他节点上运行Dijkstra，并使用一些动态编程，但我敢打赌有一种更简单的方法；我的计算机科学问题解决能力不高。在