8

这是 Vazirani 的算法书中的一个问题

这个问题的输入是一棵树 T，边上有整数权重。权重可以是负数、零或正数。给出一个线性时间算法来找到 T 中最短的简单路径。路径的长度是路径中边的权重之和。如果没有重复的顶点，则路径是简单的。请注意，路径的端点不受约束。

提示：这与在树中寻找最大独立集的问题非常相似。

我怎样才能在线性时间内解决这个问题？

这是我的算法，但我想知道它是否是线性时间，因为它与深度优先没有什么不同：

  1. 遍历树（深度优先）
  2. 保留索引（节点）
  3. 添加值
  4. 做（1）直到树的尽头
  5. 比较总和并打印路径和总和

这个问题与这个主题相似，但没有确定的答案。

4

1 回答 1

6

这个问题几乎等同于最小和子序列问题，并且可以通过动态规划以类似的方式解决。

我们将使用 DF 搜索计算以下数组：

dw1[i] = minimum sum achievable by only using node i and its descendants.
pw1[i] = predecessor of node i in the path found for dw1[i].
dw2[i] = second minimum sum achevable by only using node i and its descendants,
         a path that is edge-disjoint relative to the path found for dw1[i].

如果你能计算出这些，min(dw1[k], dw1[k] + dw2[k])接管所有k。这是因为您的路径将采用以下基本形状之一：

  k              k
  |     or     /   \
  |           /     \
  |

所有这些都包含在我们收取的金额中。

计算 dw1

从根节点运行 DFS。在 DFS 中，跟踪当前节点及其父节点。在每个节点上，假设它的子节点是d1, d2, ... dk。然后dw1[i] = min(min{dw1[d1] + cost[i, d1], dw1[d2] + cost[i, d2], ..., dw1[dk] + cost[i, dk]}, min{cost[i, dk]})。为叶节点设置dw1[i] = 0。不要忘记pw1[i]使用选定的前任进行更新。

计算 dw2

从根节点运行 DFS。做同样的事情dw1，除了从一个节点i到它的一个子节点时k，只更新dw2[i]if pw1[i] != k。但是，您为所有孩子递归地调用该函数。在伪代码中看起来像这样：

df(node, father)
    dw2[node] = inf
    for all children k of node
        df(k, node)

        if pw1[node] != k
            dw2[node] = min(dw2[node], dw1[k] + cost[node, k], cost[node, k])
于 2011-02-12T11:14:23.027 回答