3

令G = (V, E)是一个未加权的一般图，其中每个顶点v都有一个权重w(v)。

G中简单路径p的递增子序列是p的顶点序列，其中沿该序列的所有顶点的权重都增加。简单路径可以是闭合路径。

简单路径p的最长递增子序列 (LIS) 是具有最大顶点数的p递增子序列。

问题是，如何在G的所有简单路径中找到最长的递增子序列？

请注意，该图是无向的，因此它不是有向无环图 (DAG)。

4

1 回答 1

1

这是解决此问题的非常快速的算法。图中最长的递增子序列是图中路径的子序列，并且每条路径必须纯粹属于单个连通分量。因此，如果我们可以在连接组件上解决这个问题，我们可以通过在所有连接组件上找到最佳解决方案来解决整个图的问题。

接下来，考虑一下您正在为连通图 G 解决此问题的情况。在这种情况下，您可以通过按权重对节点进行排序，然后从权重最低的节点遍历到第二个，然后到第三个，然后到第四个，等等。如果有任何关系或重复，你可以跳过它们。换句话说，您可以通过以下方式解决此问题

  1. 按权重对所有节点进行排序，
  2. 丢弃每个权重的除一个节点以外的所有节点，以及
  3. 通过依次访问每个节点来形成一个 LIS。

这导致了一个非常快速的算法来解决整个问题。在 O(m + n) 时间内，找到所有连通分量。对于每个连接的组件，在时间 O(Sort(n)) 中使用前面的算法，其中 Sort(n) 是对 n 个元素进行排序所需的时间（如果使用堆排序，则可能是 Θ(n log n)，Θ(n + U) 用于桶排序，Θ(n lg U) 用于基数排序等）。然后，返回您找到的最长序列。

总的来说，运行时间是 O(m + n + &Sort(n))，这比我以前的方法要好得多，而且应该更容易编写代码。

我最初发布了这个答案，我会留下来，因为我认为它很有趣：

想象一下，您从图 G 中选择一条简单的路径，并查看该路径的最长递增子序列。尽管路径遍历整个图并且可能有很多中间节点，但该路径的最长递增子序列实际上只关心

  • 路径上的第一个节点也是 LIS 的一部分，以及
  • 从那时起，路径中的下一个最大值。

因此，我们可以考虑形成这样的 LIS。从图中的任何节点开始。现在，移动到图中 (1) 具有比当前节点更高的值且 (2) 可以从当前节点到达的任何节点，然后根据需要重复此过程多次。我们的目标是以一种尽可能长的递增值序列的方式这样做。

我们可以将此过程建模为在 DAG 中找到最长的路径。DAG 中的每个节点代表原始图 G 中的一个节点，并且从节点 u 到节点 v 存在一条边，如果

  • 在 G 中有一条从 u 到 v 的路径，并且
  • w(u) < w(v)。

由于第二个条件，这是一个 DAG，即使原始图不是 DAG。

所以我们可以分两步解决这个整体问题。首先，构建上述 DAG。为此：

  1. 找到原始图 G 的连通分量，并用其连通分量编号标记每个节点。时间：O(m + n)。

  2. 对于 G 中的每个节点 u，在新的 DAG D 中构造一个对应的节点 u'。时间：O(n)。

  3. 对于 G 中的每个节点 u，以及 G 中与 u 位于同一 SCC 中的每个节点 v，如果 w(u) < w(v)，则添加从 u' 到 v' 的边。时间：最坏情况下为 Θ(n 2 )，最好情况下为 Θ(n)。

  4. 找到 D 中最长的路径。这条路径对应于 G 中任何简单路径的最长递增子序列。时间：O(m + n)。

总体运行时间：最坏情况下为 Θ(n 2 )，最好情况下为 Θ(m + n)。

于 2017-09-22T19:33:42.290 回答