拓扑排序加权有向无环图中最长路径搜索，但路径边数需符合最大值限制。

Question

拓扑排序加权有向无环图中最长路径搜索，但路径边数需符合最大值限制。

algorithmpath-findingtopological-sortlongest-path

4

我知道可以通过“按拓扑顺序处理顶点，并计算每个顶点的路径长度为通过任何入边获得的最小或最大长度”来线性时间找到最长/最短路径，更简洁地说，就是进行拓扑排序并找到临界路径。

我的问题是，我需要添加另一个限制，即有效路径中允许的最大边数。这会使事情变得复杂，因为对于一个节点，“通过任何入边获得的最大长度”可能涉及更多的边，这意味着稍后权重更高的节点可能不再可达，因为已经达到了最大边数。

那么解决这个问题的正确方法是什么？它仍然可以在线性时间内解决吗？

- Acorn

1

我不确定是否存在一个线性时间算法，但是如果m = |E|且k是允许的最大边数，则有一个DP需要O(mk)的时间。如果需要，让我知道是否应该将其写出来（也许你可以仅从此中理解...）。 - j_random_hacker

边缘权重允许为负数吗？为零？ - j_random_hacker

1

可能可以更快地前进...长度最多为k的路径必定是(a)长度最多为RoundUp(k/2)的路径，或者(b)由长度恰好为RoundDown(k/2)的路径和长度最多为RoundUp(k/2)的路径组成。这表明了一种分治策略，其中我们解决两个类似的问题（一个是恰好有k条边的问题，另一个是最多有k条边的问题），然后将它们组合起来。顺便说一下，如果您需要找到恰好有k条边的最大权重路径，其中k是2的幂，则可以在O(n^2 log k)的时间内完成。 - j_random_hacker

1

感谢@j_random_hacker！我已经发布了一个解决方案，是否符合您的第一条评论？我会考虑一下您的分治建议，听起来很不错！顺便说一下，权重都是正数且大于零。 - Acorn

1

转化一想，我认为我们根本不需要去烦恼比最大可能路径更短的路径：我们可以假装每个顶点都有一个无限长度（甚至只是长度为k）的0权重边路径通向它。这意味着我们现在可以安全地寻找恰好为k的最大权重路径，这有一个更简单的分治方案。当k是2的幂时，我们需要解决的不同子问题数量最少：k/2、k/4、k/8等（这些可以被记忆化并重复用于解决多个更大的问题）。 - j_random_hacker

1

当k不是2的幂时，在最坏情况下，每次我们将k除以2时，我们都会创建2个不同的子问题RoundDown(k/2)和RoundUp(k/2)。让i = RoundDown(k/2)。但幸运的是，更深层次的子子问题不会扩散：RD(i/2)，RU(i/2)，RD(i/2+1)和RU(i/2+1)最多只包含2个不同的值。因此，即使k不是2的幂，最终也只有O(log(k))个子问题，总体上应该可以在O(n^2 log k)的时间内解决问题 :) - j_random_hacker

2个回答

-1

只需运行常规算法。一旦找到具有最大边数的路径，就停止并返回您找到的解决方案。

当然，您可以使该路径变得更长，但这将使最大边数无效，因此它不会是一个有效的解决方案。

- Sorin

找到一条边数最多的路径并不意味着我已经找到了最长的路径。 - Acorn

2

反例：最大权重为10，图由两条从根节点指向的路径组成：一条路径有4条边，每条边的权重为3，另一条路径有2条边，每条边的权重为5。不仅你的算法，而且任何只考虑关键路径DP算法找到的路径子路径（即权重为3的边的路径）的问题算法都会找到最多9的权重路径，尽管图中存在一个权重为10的路径。 - j_random_hacker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Acorn · Accepted Answer

我认为我已经找到了一种解决方案，使得仍然可以使用拓扑排序。

按照正常的方式进行拓扑排序和关键路径分析，但在计算给定节点的最长路径时，不仅计算一个最长路径，而是找到从1到有效路径中最大边数的每个路径长度的最长路径，为每个这些最高分数的路径创建一个顶点。

这基本上意味着您要探索到每个节点的所有可能的边缘计数变化，这意味着最终的最高得分路径肯定是最长路径。