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

Question

UPDATE

我制定了一个我认为在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,并且这似乎不比上述算法更有效.

所以我想我的主要问题有几个.首先,我上面描述的算法能解决手头的问题吗？我不完全确定Dijkstra的版本是否会起作用,因为Dijkstra的版本意味着积极的边缘价值.

现在,我确信存在更多聪明/有效的算法......什么是更好的算法？我读过"使用脊柱分解来有效地解决树长度受限的最重路径问题",但这真的很复杂,我根本不理解它.是否有其他算法可以解决这个问题,可能不像脊柱分解那样有效但更容易理解？

Answer 1

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

让我们将二叉树视为有向图，边从父级到子级。让我们为每个顶点 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) 阶。