4

考虑一个有n节点和m边的有向图。每条边都被加权。有一个开始节点s和一个结束节点e。我们希望找到从s到e具有最大节点数的路径，使得：

  1. 总距离小于某个常数d
  2. 从 s 开始，路径中的每个节点都比前一个节点更靠近节点e。（例如，当您遍历路径时，您将越来越接近目的地e。就剩余路径的边缘权重而言。）

我们可以假设图中没有循环。没有负权重。这个问题是否已经存在有效的算法？这个问题有名字吗？

4

1 回答 1

3

无论你最终做什么，从头开始做一个 BFS/DFS s，看看是否e可以达到；这只需要你 O(n+m) 所以它不会增加问题的复杂性（因为你无论如何都需要查看所有顶点和边）。0此外，在你做任何其他事情之前删除所有带有权重的边，因为这些边永远不会满足你的第二个标准。

编辑：我想出了一个算法；它是多项式的，具体取决于图表的大小，它可能仍然不够有效。请参阅下面的编辑。

现在介绍一些复杂性。这里首先要考虑的是我们实际上可以拥有多少条路径的上限，因此根据d边缘的选择和权重，我们对任何潜在算法的复杂度也有一个上限。

DAG 中可以有多少条边？答案是n(n-1)/2，这是一个紧密的界限：取n顶点，从 1 到n; 对于两个顶点i和j，将边添加i->j到图 iff i<j。这总和为n(n-1)/2，因为这样一来，对于每一对顶点，它们之间恰好有一个有向边，这意味着我们在图中的边数与在n顶点上的完整无向图中的边数一样多。

在上面描述的图中，从一个顶点到另一个顶点可以有多少条路径？答案是 2 n-2。归纳证明：

如上所述，取超过 2 个顶点的图；从顶点 1 到顶点 2有 1 = 2 0 = 2 2-2路径：(1->2)。
归纳步骤：假设有 2 n-2条路径从上面描述的顶点图编号1的顶点到编号为的顶点，增加每个顶点的数量并添加一个新顶点以及所需的边。它对现在标记为 的顶点有自己的边。此外，对于 [2;n] 中的每个，它都有 2 i-2条到该顶点的路径（它具有其他顶点到顶点的所有路径，每个路径都以 edge 为“前缀” ）。这给了我们 1 + Σ nnn1nn+1in+11->ik=2 (2 k-2 ) = 1 + Σ n-2 k=0 (2 k-2 ) = 1 + (2 n-1 - 1) = 2 n-1 = 2 (n+1)-2 .

所以我们看到有一些 DAG在它们的一些顶点对之间有 2 n-2条不同的路径；这是一个有点黯淡的前景，因为根据权重和您的选择d，您可能必须考虑所有因素。这本身并不意味着我们不能有效地选择某种形式的最优（这是你正在寻找的）。

编辑：好的，这就是我要做的：

  1. 删除所有权重为 0 的边（并且更小，但您排除了这一点），因为它们永远无法满足您的第二个标准。
  2. 对图进行拓扑排序；下面，我们只考虑图从s到e的拓扑排序部分，我们称其为整数区间[s;e]。从图中删除不严格在该区间内的所有内容，这意味着它之外的所有顶点以及入射边。在topSort 过程中，你还可以看到是否存在从s 到e 的路径，因此你会知道是否存在任何路径s-...->e。这部分的复杂度是O(n+m)。
  3. 现在实际算法：
    • 按照拓扑排序的顺序遍历 [s;e] 的顶点
    • 对于每个顶点 v，存储一个二维信息数组；让我们称它为 pre v [][] 因为它将存储有关通向它的路径上节点的前任的信息
    • 在 pre v [i][j] 中，如果 j 是该路径上当前顶点的前驱，则存储长度（以顶点计算）i 的总路径作为边权重之和的长度。例如，pre s+1 [1][s] 将具有边 s->s+1 的权重，而 pre s+1中的所有其他条目 将为 0/未定义。
    • 在计算新顶点 v 的数组时，我们所要做的就是检查它的传入边并遍历数组以获取这些边的起始顶点。例如，假设顶点 v 具有来自顶点 w 的传入边，权重为 c。考虑一下条目 pre v [i][w] 应该是什么。我们有一条边 w->v，所以我们需要将 v 中的 pre v [i][w] 设置为
      min(pre w[i-1][k] 表示所有 k，但忽略 0) + c 的条目（注意数组的下标！）；我们有效地取了一条长度为 i - 1 且通向 w 的路径的成本，并加上边 w->v 的成本。为什么是最小值？对于长度为 i - 1 的路径，顶点 w 可以有许多前驱；但是，我们希望保持在成本限制以下，每个顶点的贪心最小化将为我们做的。我们需要对 [1;sv] 中的所有 i 执行此操作。
    • 在计算顶点的数组时，不要设置会为您提供成本高于 d 的路径的条目；由于所有边都有正权重，我们只能通过每条边获得更昂贵的路径，所以忽略这些。
    • 一旦你到达 e 并完成了 pre e的计算，你就完成了这部分算法。
  4. 迭代 pre e，从 pre e [es] 开始；因为我们没有环，所以所有路径都是简单路径，因此从 s 到 e 的最长路径可以有 es 个边。找到最大的 i 使得 pre e [i] 有一个非零（意味着它被定义）条目；如果不存在，则没有符合您标准的路径。您可以使用其他顶点的数组重建任何现有路径。

现在这给了你 O(n^3) 的空间复杂度和 O(n²m) 的时间复杂度 - 数组有 O(n²) 项，我们必须迭代 O(m) 数组，每个边一个数组 -但我认为很明显，可以使用散列结构和数组以外的其他东西来优化这里对数据结构的浪费使用。或者你可以只使用一个一维数组并且只存储当前最小值而不是每次都重新计算它（你必须将路径的边权重之和与前一个顶点一起封装，因为你需要知道前一个顶点重建路径），这会将数组的大小从 n² 更改为 n，因为现在每个路径到顶点的节点数只需要一个条目，从而将算法的空间复杂度降低到 O (n²) 和 O(nm) 的时间复杂度。e，因为这些也可以安全地忽略。

于 2013-03-15T00:07:55.073 回答