如何在线性时间内找到树中最短的简单路径?

问题描述

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

这个问题的输入是一个边上具有整数权重的树 T.权重可能为负，零，或正.给出一个线性时间算法来寻找 T 中最短的简单路径. a 的长度path 是路径中边的权重之和.如果没有重复顶点，则路径是简单的.笔记路径的端点是不受约束的.

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

如何在线性时间内解决这个问题?

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

1. 遍历树(深度优先)
2. 保留索引(节点)
3. 添加值
4. 做(1)直到树结束
5. 比较总和并打印路径和总和

这个问题类似于这个主题但是没有确定的答案.

解决方案

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

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

dw1[i] = 仅使用节点 i 及其后代可实现的最小总和.pw1[i] = 为 dw1[i] 找到的路径中节点 i 的前驱.dw2[i] = 仅使用节点 i 及其后代可获得的第二个最小总和，相对于为 dw1[i] 找到的路径边缘不相交的路径.

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

 k k|或者   / |/|

所有这些都包含在我们的总和中.

计算 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] 如果 pw1[i] != k.但是，您可以为所有子项递归调用该函数.它在伪代码中看起来像这样:

df(节点，父)dw2[节点] = inf对于节点的所有子节点 kdf(k, 节点)如果 pw1[节点] != kdw2[节点] = min(dw2[节点], dw1[k] + 成本[节点, k], 成本[节点, k])

Here is a problem from Algorithms book by Vazirani

How can I solve this problem in linear time?

Here is my algorithm but I'm wonder if it is linear time since it is nothing different than depth-first:

this problem is similar this topic but there is no certain answer.

解决方案

This problem is pretty much equivalent to the minimum sum subsequence problem, and can be solved in a similar manner by dynamic programming.

We will calculate the following arrays by using DF searches:

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].

If you can calculate these, take min(dw1[k], dw1[k] + dw2[k]) over all k. This is because your path will take one of these basic shapes:

  k              k
  |     or     /
  |           /
  |

All of which are covered by the sums we're taking.

Calculating dw1

Run a DFS from the root node. In the DFS, keep track of the current node and its father. At each node, assume its children are d1, d2, ... dk. Then dw1[i] = min(min{dw1[d1] + cost[i, d1], dw1[d2] + cost[i, d2], ..., dw1[dk] + cost[i, dk]}, min{cost[i, dk]}). Set dw1[i] = 0 for leaf nodes. Don't forget to update pw1[i] with the selected predecessor.

Calculating dw2

Run a DFS from the root node. Do the same thing you did for dw1, except when going from a node i to one of its children k, only update dw2[i] if pw1[i] != k. You call the function recursively for all children however. It would look something like this in pseudocode:

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])

这篇关于如何在线性时间内找到树中最短的简单路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！