algorithm - 如何在未加权一般图的所有简单路径中找到最长的递增子序列？

Question

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

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

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

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

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

Answer 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²)，最好情况为 Θ(n)。

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

总运行时间:最坏情况为 Θ(n²)，最佳情况为 Θ(m + n)。