在加权二叉树中查找最重的长度约束路径

Question

更新

我制定了一个我认为运行时间为 O(n*k) 的算法。下面是伪代码：

routine heaviestKPath( T, k )

    // create 2D matrix with n rows and k columns with each element = -∞
    // we make it size k+1 because the 0th column must be all 0s for a later 
    // function to work properly and simplicity in our algorithm
    matrix = new array[ T.getVertexCount() ][ k + 1 ] (-∞);

    // set all elements in the first column of this matrix = 0
    matrix[ n ][ 0 ] = 0;

    // fill our matrix by traversing the tree
    traverseToFillMatrix( T.root, k );

    // consider a path that would arc over a node
    globalMaxWeight = -∞;
    findArcs( T.root, k );

    return globalMaxWeight
end routine


// node = the current node; k = the path length; node.lc = node’s left child; 
// node.rc = node’s right child; node.idx = node’s index (row) in the matrix; 
// node.lc.wt/node.rc.wt = weight of the edge to left/right child;
routine traverseToFillMatrix( node, k )

   if (node == null) return;

   traverseToFillMatrix(node.lc, k ); // recurse left
   traverseToFillMatrix(node.rc, k ); // recurse right

   // in the case that a left/right child doesn’t exist, or both,
   // let’s assume the code is smart enough to handle these cases
   matrix[ node.idx ][ 1 ] = max( node.lc.wt, node.rc.wt );


   for i = 2 to k {
       // max returns the heavier of the 2 paths
       matrix[node.idx][i] = max( matrix[node.lc.idx][i-1] + node.lc.wt, 
                                  matrix[node.rc.idx][i-1] + node.rc.wt);
   }

end routine



// node = the current node, k = the path length
routine findArcs( node, k ) 

    if (node == null) return;

    nodeMax = matrix[node.idx][k];
    longPath = path[node.idx][k];

    i = 1;
    j = k-1;
    while ( i+j == k AND i < k ) {

        left = node.lc.wt + matrix[node.lc.idx][i-1];
        right = node.rc.wt + matrix[node.rc.idx][j-1];

        if ( left + right > nodeMax ) {
            nodeMax = left + right;
        }
        i++; j--;
    }

    // if this node’s max weight is larger than the global max weight, update
    if ( globalMaxWeight < nodeMax ) {
        globalMaxWeight = nodeMax;
    }

    findArcs( node.lc, k ); // recurse left
    findArcs( node.rc, k ); // recurse right

end routine

让我知道你的想法。欢迎反馈。

---

我认为已经提出了两种简单的算法，可以在加权二叉树中找到最重的长度约束路径。首先，该算法的描述如下：给定一个具有加权边和某个值k的n顶点二叉树，找到长度为k的最重路径。

对于这两种算法，我都需要对所有顶点的引用，因此我只需对树进行简单的遍历即可获得对所有顶点的引用，每个顶点都有对其左节点、右节点和父节点的引用树。

算法1 对于这个算法，我基本上计划从树中的每个节点运行 DFS，同时考虑到固定路径长度。另外，由于我正在寻找的路径有可能从左子树到根到右子树，所以我必须在每个节点考虑 3 个选择。但这将导致 O(n*3^k) 算法，我不喜欢这样。

算法2 我本质上是在考虑使用 Dijkstra 算法 的修改版本，以便考虑修复路径长度。由于我正在寻找最重的并且 Dijkstra 算法找到最轻的，因此我计划在开始遍历之前否定所有边权重。实际上...这没有意义，因为我必须在每个节点上运行 Dijkstra's，而且这似乎并不比上述算法有效得多。

所以我想我的主要问题有几个。首先，我上面描述的算法是否解决了当前的问题？我不完全确定 Dijkstra 的版本是否有效，因为 Dijkstra 的版本适用于正边缘值。

现在，我确信存在更聪明/更有效的算法......什么是更好的算法？我读过“使用脊柱分解有效解决树的长度约束最重路径问题”，但这确实很复杂，我根本不理解。是否有其他算法可以解决这个问题，可能不如脊柱分解那么有效，但更容易理解？

Answer 1

您可以使用从每个节点向下的 DFS，在 k 条边之后停止来搜索路径，但请注意，这将在每个节点上执行 2^k 工作，总共 O(n*2^k ）有效，因为从起始节点向下的每个级别，路径数量都会加倍。

正如 DasBoot 在评论中所说，在这里使用 Dijkstra 算法没有任何优势，因为它的聪明之处在于，当有多个路线可能时，选择最短（或最长）的方式到达两点之间。对于一棵树来说，总是只有一种方法。

我有一个动态规划算法，需要 O(nk) 时间。这里有一些提示：

• 如果您选择某个叶顶点作为根r，并将所有其他顶点向下引导，远离根，请注意，此有向树中的每条路径都有一个最高节点——即，最接近r的唯一节点。
• 您可以通过遍历每个节点v并计算最高节点为<的最重长度-k路径来计算整体最重长度-k路径em>v，最后取所有节点的最大值。
• 最高节点为 v 的长度-k 路径必须有一条向下延伸至一个子节点的长度-i 路径和一条长度-( ki) 路径下降到另一个。

这应该足以让你朝着正确的方向思考；如果您需要进一步的帮助，请告诉我。

Answer 2

这是我的解决方案。欢迎反馈。

让我们将二叉树视为有向图，边从父级到子级。让我们为每个顶点 v 定义两个概念：

a) 弧：这是一条有向路径，即从顶点 v 开始，路径中的所有顶点都是起始顶点 v 的子节点。

b) 子路径：这是一条包含 v 的有向或无向路径，也就是说，它可以从任何地方开始，在任何地方结束，从 v 的孩子到 v，然后到它的另一个孩子。弧集是子路径集的子集。

我们还定义了一个函数 HeaviestArc(v,j)，它给出了顶点 j 的最重弧，在左侧或右侧，长度为 j，从 v 开始。我们还定义了 LeftHeaviest(v,j)，并且RightHeaviest(v,j) 分别为长度为 j 的最重左弧和右弧。

鉴于此，我们可以根据其子节点为每个顶点 v 定义以下递归：

LeftHeaviest(v,j) = weight(LeftEdge(v)) + HeaviestArc(LeftChild(v)),j-1);
RightHeaviest(v,j) = weight(RightEdge(v)) + HeaviestArc(RightChild(v)),j-1);
HeaviestArc(v,j) = max(LeftHeaviest(v,j),RightHeaviest(v,j));

这里 j 从 1 到 k，并且 HeaviestArc(v,0)=LeftHeaviest(v,0),RightHeaviest(v,0)=全部为 0。对于叶节点，HeaviestArc(v,0) = 0，对于所有其他 j，HeaviestArc(v,j)=-inf（我需要更彻底地考虑极端情况）。

然后，包含 v 的最重子路径 HeaviestChildPath(v) 可以计算为：

HeaviestChildPath(v) = max{ for j = 0 to k LeftHeaviest(j) + RightHeaviest(k-j)}

最重路径应该是所有子路径中最重的。

算法的估计运行时间应该是 O(kn) 阶。

Answer 3

def traverse(node, running_weight, level):
  if level == 0: 
    if max_weight < running_weight:
        max_weight = running_weight
    return
  traverse(node->left,running_weight+node.weight,level-1)
  traverse(node->right,running_weight+node.weight,level-1)
  traverse(node->parent,running_weight+node.weight,level-1)


max_weight = 0
for node in tree:
  traverse(node,0,N)