algorithm - 特定类型图中的最长路径

Question

我知道对于一般图而言，最长路径问题是 NP 难题。但是，我正在考虑一种特定类型的图，它由一个循环组成，加上循环的每个顶点上的一个附加边。例如，对于长度为 7 的循环，我们有如下图：

所有边都被加权（权重是实数，可以是正数或负数）。我想在这张图上找到最大的简单路径，其中路径的大小是路径上边权重的总和。

该算法在循环的大小上应该是线性的。但任何想法都会受到赞赏。

Answer 1

这可以简化为最大子阵列问题并在线性时间内解决。

1. 断开循环（在任何节点）。
2. 将剩余图的第二个副本附加到循环断开的点（我们可以跳过最后一个节点）。
3. 将修改后的 Kadane 算法应用于生成的节点列表。
4. 如果找到的路径没有边，则在图中搜索最大权重边。如果该边具有非负权重，则报告此单边路径。如果不是，则如果不允许空路径，则无论如何报告此单边路径，或者如果允许则报告空路径。

->

必要的 Kadane 算法修改：

1. 跟踪当前路径（子数组）中的节点数。N当子数组具有或更多“循环”节点时，从尾部修剪节点。为了有效地修剪这些节点，我们需要一个可以报告其元素最小值的队列。在路径头部前进的任何地方将元素推送到此队列（如果非负，则添加叶边权重），在修剪路径尾部时弹出元素，并在当前路径重置为空路径的任何地方重置队列。此队列包含（不一定简单）路径的前缀长度，其中最小值为推进路径尾部提供了适当的位置。这样的队列可以实现为仅包含非递减值的双端队列，也可以实现为本答案中提到的一对堆栈。
2. 将路径长度重置max(0, leaf_edge_weight)为当前路径长度低于零的任何位置（而不是像原始 Kadane 算法那样将其重置为零）。
3. 当当前（非空）路径与迄今为止最佳路径进行比较时，添加非负叶边缘权重（对应于头节点）。

Answer 2

在循环中选择一个链接。最长的路径要么通过该链接，要么不通过该链接，因此让我们找出任何一种情况下的最佳答案，然后选择其中最好的一个。

如果最长路径不经过循环链接，则删除该链接以生成树。从叶子向上计算，在每个节点上，该节点下的最长路径，以及从该节点到任何后代的最长路径。在每个节点上，您可以通过查看其子节点的答案来计算答案。根源处的答案为您提供了最长的路径。

如果最长的路径确实通过您选择的链接，则它必须包含从链接一端顺时针走的部分和从链接另一端逆时针走的部分。这两个的长度加起来不超过一加上构成循环的链接数。对于 i = 1 来限制计算链路每一侧的顺时针和逆时针路径的成本并保持运行最大值。通过该链接的最长路径的长度为，对于某些 k，最长路径顺时针方向最多 k 个链接，最长路径逆时针方向最多 Nk 个链接（可能有一些类似成本的摆弄 - ve 链接成本存在）。因此，您可以找到通过您选择的链接的最长路径，成本也是 O(n)。

计算两个案例的成本 O(n) 并选择最好的给你总成本 O(n)

Answer 3

最长的路径几乎肯定在两个外部顶点之间。几乎肯定有必要覆盖循环中的所有顶点。

因此，您想使用 DFS 来绘制 O(N) 中的循环。然后计算当前循环排列的长度。加上从循环中的第一个点到它的外部的距离以及最后一个点到它的外部的距离。这为您提供了实际的路径长度，您将其与循环长度分开存储。

增加第一个点和最后一个点的索引（可以在 O(1) 中完成），删除现在从第一个点指向最后一个点的边的长度。然后再次添加外部长度。重复直到你覆盖了所有的顶点。由于您存储和更新路径长度而不是每次都实际重新计算它（这需要（O（N ^ 2）），因此可以在O（N）中完成。

这允许在 O(N) 中遍历循环。但是，它不是一个精确的算法。这需要检查您是否不应该将 first+i 和/或 last-j 用于某些 i,j 。要完全检查这一点，基本上需要 O(N^2)。

虽然，您可能会通过巧妙地确定这些边缘情况的可能位置在 O(N log N) 左右完成它。我怀疑一个精确的线性算法是可能的。